Почему мой алгоритм quicksort не работает для повторяющихся элементов?

Question

Я реализовал алгоритм quicksort в C для сортировки элементов массива. Он работает во всех случаях, кроме случаев, когда массив имеет два или более одинаковых элемента. Я пытался ее исправить и отлаживал, но, похоже, мне не удается заставить его работать, когда повторяются элементы.

Буду признателен за любую помощь в том, как я могу изменить свой код для работы с повторяющимися элементами.

#include <stdio.h> 
#include <stdlib.h> 

//Random Array Length 
#define L 10 
#define MAX 100 

void smarter_sort(int[],int,int); 
void swap(int[],int,int); 
int choose_piv(int[],int,int); 

int main(){ 

    int i, a[L]; 

    //Generate an array of random numbers 
    for(i=0; i<L; i++) 
     a[i]= rand() % (MAX+1); 

    //Unsorted Array 
    printf("\nUnsorted array: "); 
    for(i=0; i<L; i++) 
      printf("%d ", a[i]); 

    //Sorted Array 
    smarter_sort(a,0,L-1); 
    printf("\nSorted array: "); 
      for(i=0; i<L; i++) 
       printf("%d ", a[i]); 
    return 0; 
} 

//Recursively defined quicksort (Pseudo-code listing 1.9) 
void smarter_sort(int a[], int l, int r){ 
    if(r > l){ 
     int piv = choose_piv(a, l, r); 
     smarter_sort(a, l, piv-1); 
     smarter_sort(a, piv+1, r); 
    } 
} 

//Swap Elements 
void swap(int a[], int i, int j){ 
    int t=a[i]; 
    a[i]=a[j]; 
    a[j]=t; 
} 

//Choosing the pivot (pseudo-code listing 1.10) 
int choose_piv(int a[], int l, int r){ 
    //defining pointers and pivot 
    int pL = l, pR = r; 
    int piv = l; 

    while (pL < pR){ 
     //finding the first left element greater than piv 
     while(a[pL] < a[piv]) 
      pL++; 

     //finding the first right element greater than piv 
     while(a[pR] > a[piv]) 
      pR--; 

     //swapping if the pointers do not overlap 
     if(pL < pR) 
      swap(a, pL, pR); 

     if(a[pL]==a[piv]||a[pR]==a[piv]){ 
      pL++; 
      pR--; 
     } 
    } 
    //swapping and returning the rightmost pointer as the pivot 
    swap(a, piv, pR); 
    return pR; 
} 

Answer 1

Это ваш код изменен для того, чтобы работать должным образом, даже с массивом, содержащим равные элементы:

#include <stdio.h> 
#include <stdlib.h> 

//Random Array Length 
#define L 10 
#define MAX 100 

void smarter_sort(int[],int,int); 
void swap(int[],int,int); 


int main(){ 

    int i, a[L]; 

    //Generate an array of random numbers 
    for(i=0; i<L; i++) 
     a[i]= rand() % (MAX+1); 

    //Unsorted Array 
    printf("\nUnsorted array: "); 
    for(i=0; i<L; i++) 
     printf("%d ", a[i]); 

    //Sorted Array 
    smarter_sort(a,0,L-1); 
    printf("\nSorted array: "); 
     for(i=0; i<L; i++) 
      printf("%d ", a[i]); 
    return 0; 
} 

//Recursively defined quicksort (Pseudo-code listing 1.9) 
void smarter_sort(int arr[], int left, int right) { 
     int i = left, j = right; 
     int pivot = arr[(left + right)/2]; 


     while (i <= j) { 
      while (arr[i] <pivot) 
       i++; 
      while (arr[j]>pivot) 
       j--; 
      if (i <= j) { 
       swap(arr,i,j); 
       i++; 
       j--; 
      } 
    }; 


    if (left < j) 
      smarter_sort(arr, left, j); 
    if (i < right) 
      smarter_sort(arr, i, right); 
} 


//Swap Elements 
void swap(int a[], int i, int j){ 
    int t=a[i]; 
    a[i]=a[j]; 
    a[j]=t; 
}