Sonderproblem mit Quicksort-Partition

Question

Heute, als ich Quicksort versuchte, anstatt das letzte Element als Pivot und Partitionierung zu nehmen, nahm ich das erste Element als Pivot, aber es produziert nicht die korrekte partitionierte Ausgabe.

int pivot = ar[0]; 
int pindex = 0; 

for(int i = 0;i < ar.size();i++) 
{ 
    if(ar[i] <= pivot) 
    { 
     swap(ar[i],ar[pindex]); 
     pindex++; 
    } 
} 
swap(ar[pindex],ar[ar.size()-1]); 

Ich konnte nicht verstehen, warum ich das immer für Partition verwenden, aber das funktioniert nicht, wenn ich als Partition erstes Element nehmen.

Aber das funktionierte auch wenn ich als Partition erste Element hat

int i, j, pivot, temp; 
pivot = ar[0]; 
i = 0; 
j = ar.size()-1; 
while(1) 
{ 
    while(ar[i] < pivot && ar[i] != pivot) 
     i++; 
    while(ar[j] > pivot && ar[j] != pivot) 
     j--; 
    if(i < j) 
    { 
     temp = ar[i]; 
     ar[i] = ar[j]; 
     ar[j] = temp; 
    } 
    else 
    { 
     break; 
    } 
} 

Was sind die Unterschiede zwischen ihnen.

Answer 1

Endlich gefunden, dass diese Methode Hoares Partitionsmethode ist, wobei die typische schnelle Sortiermethode, die wir alle verfolgen, Lomutos Partition ist.

Sehen Sie diese Wiki-Seite, sie hat alle Details https://en.wikipedia.org/wiki/Quicksort