Усовершенствование быстрой сортировки

Question

Быстрое алгоритм сортировки имеет плохое поведение, когда есть много копий элементов. (Я имею в виду, что у нас есть повторяющиеся данные). Как его можно улучшить, чтобы эта проблема была решена.

int partition (int low,int high) 
{ 
int j=low,i=low+1; 
int PivotItem=arr[low]; 
    for(int i=0,j=0;i<n;i++) 
{ 
    if(arr[i]==PivotItem) 
    subarray[j]=arr[i]; 
} 
for(i=low+1;i<=high;i++) 
{ 
    if(arr[i]<PivotItem) 
    { 
     j++; 
     swap(arr[i],arr[j]); 
    } 
} 
swap(arr[low],arr[j]); 
int PivotPoint=j; 
return PivotPoint; 
} 
void quick_sort(int low,int high) 
{ 
if(low==high) 
    return ; 
int PivotPoint=partition(low,high); 
quick_sort(low,PivotPoint-1); 
quick_sort(PivotPoint+1,high); 
} 

Answer 1

Я предполагаю, что вы имели в виду тот факт, что быстрая сортировка сравнивает элементы на основе <= (или <, а затем результат симметричен к следующему объяснению) компаратора, и если мы посмотрим на случай, когда все элементы являются то же самое, что и с осью x, вы получаете худшую сложность худшего сортирования, так как вы разбиваете массив на две очень не четные части, один из которых имеет размер n-1, а другой пуст.

---

Быстрое исправление для решения этой проблемы будет использовать быстрой сортировки только < и > - разбить данные на две подрешетки, и вместо особой оси, удерживая массив, который содержит все элементы, равные оси поворота, затем рекурсия на элементах, которые строго больше, чем точка поворота, и элементы, которые строго меньше, чем точка поворота, и объединяют три массива.

Иллюстрация:

legend: X=pivot, S = smaller than pivot, L = larger than pivot 
array = |SLLLSLXLSLXSSLLXLLLSSXSSLLLSSXSSLLLXSSL| 
Choose pivot - X 
Create L array of only strictly smaller elements: |SSSSSSSSSSSSSSS| 
Create R array of only strictly larger elements: |LLLLLLLLLLLLLLLLLL| 
Create "pivot array" |XXXXXX| 

Now, recurse on L, recurse on R, and combine: 
|SSSSSSSSSSSSSSS XXXXXX LLLLLLLLLLLLLLLLLL| 

Answer 2

Существует специальная модификация QuickSort известна как dutch flag sort algorithm. Он использует трехсторонний раздел для предметов меньших, равных и больших, чем значение элемента поворота.