Быстрая сортировка бесконечного цикла, если есть повторяющиеся значения

У меня есть программа быстрой сортировки, которая отлично работает, пока я не попытаюсь отсортировать массив с повторяющимся числом. Программа застревает в бесконечном цикле. Я считаю, что это происходит в блоке кода While(lower < upper).

void quickSort(int array[], int size){
  if(size < 2) return;

  int pivot, lower, upper, temp;

  //Set the indeces for the first and last elements                                 
  lower = 0;
  upper = size - 1;

  //Select pivot element randomly                                                   
  pivot = array[rand() % (size)];                                                                                                     

  while(lower < upper){
    //Lower must be a number < than pivot and upper a number >= pivot               
    while(array[lower] < pivot){
      lower++;
    }
    while(array[upper] > pivot){
      upper--;
    }

    //Swap upper and lower                                                          
    temp = array[lower];
    array[lower] = array[upper];
    array[upper] = temp;
  }

  //Repeat the past actions on the two partitions of the array recursively          
  quickSort(array, lower);
  quickSort(&array[lower+1], size-lower-1);
}

c++ quicksort
person Kalmar    schedule 03.12.2013    source источник
comment
Ты прав. При беглом просмотре вашего кода может случиться так, что ни нижний не увеличивается, ни верхний не уменьшается, что приводит к inf. петля. (найти такой случай несложно т.е. все числа сортировать все равно)   -  person gregory561    schedule 03.12.2013
comment
Что происходит, когда есть несколько экземпляров опорного значения? Две самые внутренние петли while никогда не приведут к встрече lower и upper. Один должен быть < pivot, а другой >= pivot.   -  person Joe Z    schedule 03.12.2013
comment
Ваш комментарий об отношениях между верхним/нижним и стержнем не согласуется с кодом, поэтому один из них, вероятно, неверен.   -  person molbdnilo    schedule 03.12.2013
comment
@JoeZ Я пробовал это, но в итоге получил ошибку сегментации.   -  person Kalmar    schedule 03.12.2013
comment
Вам также может понадобиться проверить верхний ›= нижний в этом цикле while.   -  person Joe Z    schedule 03.12.2013
comment
Какой наименьший найденный вами массив вызывает эту ошибку? Что произошло, когда вы выполнили сортировку этого массива в отладчике? Что должно было произойти?   -  person Useless    schedule 03.12.2013

Ответы (1)


arrow_upward
7
arrow_downward

РЕДАКТИРОВАТЬ: добавлен код.

Из Википедии псевдокод для быстрой сортировки на месте выглядит следующим образом:
(Не говорю, что им следует слепо доверять)

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

Итак, вы видите, что он очень похож на ваш алгоритм с небольшими изменениями.

while(lower <= upper){

Также вам нужно поменять местами только если lower <= upper, а затем обновить индексы.

И ваш код отличается рекурсивными вызовами:

quicksort(array from first index to right) {array[0] to array[upper]}
quicksort(array from left to last index) {array[lower] to array[size-1]}

Это потому, что теперь, когда он вышел из цикла while, верхний меньше нижнего.

Полный рабочий код:

#include <iostream>
#include <cstdlib>
using namespace std;

void quickSort(int array[], int size){
  if(size < 2) return;

  int pivot, lower, upper, temp;

  //Set the indeces for the first and last elements                                 
  lower = 0;
  upper = size - 1;

  //Select pivot element randomly                                                   
  pivot = array[rand() % (size)];                                                                                                     

  while(lower <= upper){
    //Lower must be a number < than pivot and upper a number >= pivot               
    while(array[lower] < pivot){
      lower++;
    }
    while(array[upper] > pivot){
      upper--;
    }

    //Swap upper and lower                                                          
    if ( lower <= upper ) {
        temp = array[lower];
        array[lower] = array[upper];
        array[upper] = temp;
        lower++;
        upper--;
    }
  }

  //Repeat the past actions on the two partitions of the array recursively          
  quickSort(array, upper+1);
  quickSort(&array[lower], size-lower);
}

int main() {
    // your code goes here
    int myArray[] = { 10, 9, 8, 7, 7, 7, 7, 3, 2, 1};
    quickSort( myArray, 10 );
    for ( int i = 0; i < 10; i++ )
        cout << myArray[i] << " ";
    return 0;
}

Выход:

1 2 3 7 7 7 7 8 9 10
person Abhishek Bansal    schedule 03.12.2013