Проблема с моей реализацией быстрой сортировки

Question

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

РЕДАКТИРОВАТЬ Проблема У меня, кажется, застревает в функции быстрой сортировки, и программа просто зависает. Когда я попытался отладить его с помощью printf, исходный массив, похоже, был изменен с неожиданными числами (не из исходного списка), такими как 0.

void quicksort(int a[], const int start, const int end)
{
   if( (end - start + 1 ) < 2)
      return;

   int pivot = a[rand()%(end - start)];

   //Two pointers
   int L = start;
   int R = end;

   while(L < R)
   {
      while(a[L] < pivot)
         L++;
      while(a[R] > pivot)
         R--;
      if(L < R)
         swap(a,L,R);      
   }
   quicksort(a, start, L-1);
   quicksort(a, L+1, end );
}

void swap(int a[], const int pos1, const int pos2)
{
   a[pos1] ^= a[pos2];
   a[pos2] ^= a[pos1];
   a[pos1] ^= a[pos2];
}

int main()
{
   int array[20] = {0};
   int size = sizeof(array)/sizeof(array[0]);//index range = size - 1

   int i = 0;
   printf("Original: ");
   for (i; i < size; i++)
   {
      array[i] = rand()%100+ 1;
      printf("%d ", array[i]);
   }
   printf("\n");

   quicksort(array,0,size-1);

   int j = 0;
   printf("Sorted: ");
   for(j; j < size; j++)
      printf("%d ", array[j]);
   printf("\n");
}

Дополнительный вопрос: Что касается рекурсивного вызова быстрой сортировки, будут ли указатель влево и вправо всегда указывать в направлении оси в конце каждого раздела? Если это так, правильно ли вызывать быструю сортировку от начала до L-1 и L + 1 до конца?

Кроме того, требуется ли if (L

Answer 1

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

int pivot = a[rand()%(end - start)];

Обратите внимание, что это всегда выбирает пивот в диапазоне [0, конец - начало) вместо [начало, конец).Я думаю, что вы хотите иметь что-то вроде

int pivot = a[rand()%(end - start) + start];

, чтобы вы выбрали точку поворота в нужном диапазоне.

Другая ошибка в этом циклическом коде:

while(L < R)
{
   while(a[L] < pivot)
      L++;
   while(a[R] > pivot)
      R--;
    if(L < R)
      swap(a,L,R);      
}

Предположим, что L < R, но a[L], a[R] и pivot имеют одно и то же значение.Это может произойти, например, если вы быстро сортировали диапазон, содержащий повторяющиеся элементы.Это также происходит, когда вы используете rand со стандартной реализацией Linux rand (я пробовал это на своей машине, и 27 дублировалось дважды).Если это так, то вы никогда не перемещаете L или R, потому что условия в циклах всегда оцениваются как ложные.Вам потребуется обновить логику для разделения элементов, когда возможны дубликаты, так как в противном случае вы попадете в бесконечный цикл.

Надеюсь, это поможет!

Answer 2

После оператора While R должно быть меньше L, попробуйте это:

quicksort(a, start, R);
quicksort(a, L, end ); 

А утверждение if(L < R) не обязательно.