0

По ходу изучения предмета Алгоритмы и структуры данных, знакомлюсь с разными алгоритмами сортировки, конкретно с quick sort на данном этапе, задался задачей самостоятельно его реализовать, исходя из понимания прочитанной мной концепции, основными критериями описания функции были:

  • Рекурсивное представление, посредством одной функции, параметрами которой являются указатель на начало массива и его размер.
  • Логичность представления кода (сокращение по возможности), в отличии от рабочих вариантов, которые я нашел на других сайтах.
  • Логичность представления кода (сокращение по возможности), в отличии от рабочих вариантов, которые я нашел на других сайтах.

Мой код:

template <typename T>
void quick_sort(T* unsorted, unsigned size)
{
    if (size < 2) return;
    unsigned left = 0;
    unsigned right = size - 1;
    T middle = unsorted[size >> 1];
    while (left != right)
        if (unsorted[left] > middle)
            while (left != right)
                if (unsorted[right] <= middle)
                {
                    T temp = unsorted[left];
                    unsorted[left] = unsorted[right];
                    unsorted[right] = temp;
                    break;
                }
                else right--;
        else left++;
    quick_sort(unsorted, left);
    quick_sort(unsorted + left, size - left);
}

Вот скрин результатов выполнения сортировки массива из 128 случайных значений: Консоль

Проблема в том, что он исходя из всей логики все же сортируется по возрастанию, но дает осечку примерно через каждые 10 шагов, предполагаю, что либо из-за того что при разбиении на 2 функции пропускается шаг, либо из-за не учета при проверке равных опорному элементов.
Надеюсь на вашу внимательность, если кто заметит утечку, либо подскажет, что следует изменить, жду ваших ответов..

2 ответа 2

4

Рекурсивные вызовы для левой и правой части:

quick_sort(unsorted, left + 1);
quick_sort(unsorted + left, size - left);

Складываем ваши размеры левой и правой части:

left + 1 + size - left = size + 1

Нестыковочка получается! Почему вдруг суммарный размер получился больше исходного? Если не гарантируется уменьшение размера, то не гарантируется и завершение рекурсии.

И действительно, на входе { 1, 2, 3, 6 } ваша реализация впадает в бесконечную рекурсию. Так что ваше "дает осечку примерно через каждые 10 шагов" - это вам просто повезло.

2
  • да, действительно, исправил эту неточность, но такая ошибка разбиения скорее обеспечивает только то ,что один лишний элемент сравнивается дважды разными функциями. все еще не могу обнаружить изьян в логике сравнения, есть соображения по этому поводу? 10 янв 2018 в 14:34
  • Если бы дело было только в "сравнивается дважды разными функциями", то это действительно не было бы серьезной проблемой. Но бесконечная рекурсия - это проблема. 10 янв 2018 в 16:17
0

22 25 25 25 19 26

Результат надо проверять на нескольких исходных данных и проверять автоматически. И в конце должно быть примерно:

quick_sort(unsorted, rootelpos);
quick_sort(unsorted+rootelpos+1, size - rootelpos - 1);
3
  • но ведь при таком разбиении выпадает один элемент посредине, на каждом шаге рекурсии, не понимаю в чем смысл.. получается что массив с arr[0] по arr[size-1] разбивается на arr[0] по arr[rootelpos-1] и arr[rootlepos + 1] по arr[size - 1], выпадает arr[rootlepos] 10 янв 2018 в 14:46
  • ru.wikipedia.org/wiki/… в википедии так 10 янв 2018 в 16:32
  • там по другому немного, там сразу после завершения цикла указатель left = right + 1, а у меня left = right, хм, стоп, возможно к стати в этом и проблема, элемент по средине не сортируется, сейчас гляну.. 10 янв 2018 в 16:47

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.