Что я делаю не так с этой функцией, она не заканчивается - PullRequest
Новая
       18

Что я делаю не так с этой функцией, она не заканчивается

0 голосов
/ 07 декабря 2018

это функция, которую я видел несколько месяцев назад, я пытался ее воспроизвести, но мне кажется, что я что-то упустил, потому что программа не заканчивается. 

void quick_sort(int *array, int len) {
     for (int i = 0; i < len - 1; i++) {
         if (array[i] > array[i + 1]) {
             int temp = array[i];
             array[i] = array[i + 1];
             array[i + 1] = temp;
          }
      }
      quick_sort(array, len);
 }

что я здесь не так делаю?Кто-нибудь может помочь?

Ответы [ 2 ]

0 голосов
/ 07 декабря 2018

С одной стороны, эта функция не имеет правильного названия: это абсолютно ничего , как быстрая сортировка.Это похоже на внутренний цикл алгоритма сортировки пузырьков, а мертвая раздача - это восходящее сравнение и потенциальные перестановки смежных элементов

При этом сделать эту процедуру сортировки рекурсивной,просто вставьте то, что в противном случае было бы внешним циклом традиционной пузырьковой сортировки, в стек рекурсивной активации.Чтобы понять это, рассмотрим простую оптимизированную для обнаружения свопов пузырьковую сортировку: 

void bubblesort(int arr[], size_t len)
{
    while (len-- > 0) // THIS LOOP
    {
        for (size_t i=0; i<len; ++i)
        {
            if (arr[i] > arr[i+1])
            {
                int tmp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = tmp;
            }
        }
    }
}

Вы можете видеть выше, что внешний цикл - это то, что мы хотим сохранить в стеке.Так как мы можем это сделать?Ну, во-первых, нам нужно условие, которое останавливает рекурсию, и внутренний цикл.Затем мы можем просто выполнить рекурс с длиной на один элемент меньше текущей длины: 

void bubblesort(int arr[], size_t len)
{
    if (len-- < 2) // base case to exit on trivial sequence
        return;

    for (size_t i=0; i<len; ++i)
    {
        if (arr[i] > arr[i+1])
        {
            int tmp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = tmp;
        }
    }

    // recurse with one fewer element.
    bubblesort(arr, len);
}

Вот и все.Это также пример учебника с хвостовой рекурсией, который мы можем реализовать с помощью итеративного цикла (очевидно, именно с этого мы и начали).

Итак, в общем, выотсутствовали случай выхода и сокращение длины, которое в конечном итоге достигло этого случая выхода.Обращаясь к обоим из них, функция должна «работать» (термин используется свободно, поскольку никто никогда не будет сортировать нетривиальные данные с помощью такой функции).

0 голосов
/ 07 декабря 2018

Вы должны дать exit condition, иначе он будет работать вечно.
В вашем коде нет условий выхода, и поэтому он работает бесконечно.
Вы продолжаете звонить quick_sort(array, len);, но вспомните сценарий, в котором вам нужно прекратить звонить quick_sort(array, len);, и поставить условие для него (это будет ваше условие выхода), чтобы вы могли прекратить его бесконечный цикл.

...