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) условие также не требуется.