C++ - Быстрая сортировка - Пользовательская реализация не работает

Question

Мой код:

void quickSort(int array[], int last)
{
    int middle = last / 2;
    int i = 0, j = last;
    while(i <= j)
    {
        while(array[i] < array[middle])
            i++;
        while(array[j] > array[middle])
            j--;

        if(i <= j)
        {
            swap(array[i], array[j]);
            i++;
            j--;
        }
    }

    if(j > 0)
        quickSort(array, j);
    if(last > i)
        quickSort(array + i, last - i);
}

int main()
{
    int a[] = {10,9,8,7,6,100,5,4,3,2,1};
    quickSort(a, 10);
    return 0;
}

После завершения я вижу следующие значения в памяти:

{1, 6, 7, 8, 9, 10, 2, 3, 4, 5, 100}

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

В чем дело?

Answer 1

Вы должны хранить свой стержень во время каждой итерации. То, как вы сейчас это написали, может быть видоизменено по мере прохождения массива. На вашей первой итерации 100 выбирается как точка поворота, затем меняется местами с помощью j, а затем 1 становится точкой поворота. Это, вероятно, происходит во всех ваших итерациях.

Answer 2

Вы можете использовать эту функцию, если хотите:

void quicksort(int x[],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

вызвать эту функцию, как это

int main(){
  int a[] = {10,9,8,7,6,100,5,4,3,2,1};

  quicksort(a,0,10);

  printf("Sorted elements: ");
  for(i=0;i<11;i++)
    printf(" %d",a[i]);

  return 0;
}

Answer 3

    void qsort(int arr[], int fst, int last)
    {
        int i, j, pivot, tmp;
        if (fst<last)
        {
            pivot = fst;
            i = fst;
            j = last;
            while (i<j)
            {
                while (arr[i] <= arr[pivot] && i<last)
                    i++;
                while (arr[j]>arr[pivot])
                    j--;
                if (i<j)
                {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            tmp = arr[pivot];
            arr[pivot] = arr[j];
            arr[j] = tmp;
            qsort(arr, fst, j - 1);
            qsort(arr, j + 1, last);
        }
    }

Ниже приведены проблемы в вашем коде -

если ( i <= j) условие, вы увеличиваете i и уменьшаете j, что не требуется, и если ( j < 0) условие не требуется, и если (last > i) условие также не требуется.