C++ - Probleme Quicksort Implementierung

Question

so bei Rekursion Ich bin neu und ich habe versucht, einige Algorithmen zu implementieren, so wie quicksort unten, aber es scheint nicht so gut zu funktionieren ... Ich denke, das Problem ist, in der Partition, aber ich bin mir nicht sicher, was das Problem ...

#include <iostream> 

using namespace std; 

const int MAX = 100; 

typedef int matrix[MAX]; 

struct Taula{ 
    matrix m; 
    int n; 
}; 
void wwap(Taula &t, int n, int i, int posPivot) 
{ 
    int aux = t.m[posPivot]; 
    t.m[posPivot] = t.m[i]; 
    t.m[i] = aux; 
} 
void partition(Taula &t, int n, int left, int right, int &posPivot) 
{ 
    int pivot = t.m[right]; 
    posPivot = left; 
    for (int i = left; i < right-1; i++){ 
     if (t.m[i] < pivot){ 
      swap(t,n,i,posPivot); 
      posPivot = posPivot+1; 
     } 
    } 
    swap(t,n,posPivot,right); 
} 
void quicksort(Taula &t, int n, int left, int right) 
{ 
    int k; 
    if (left < right){ 
     particio(t,t.n,left,right,k); 
     quicksort(t,t.n,left,k-1); 
     quicksort(t,t.n,k+1,right); 
    } 
} 

int main() 
{ 
    Taula t; 
    t.n = 0; 

    cout << "INTEGER SEQUENCE ENDED WITH -2:" << endl; 
    int x; cin >> x; 

    while (x != -2){ 
     t.m[t.n] = x; 
     t.n++; 
     cin >> x; 
    } 
    cout << t.n << " ELEMENTS" << endl; 
    quicksort(t,t.n,0,t.n); 
    cout << "SORT:" << endl; 
    for (int i = 0; i < t.n; i++) cout << t.m[i] << endl; 
    return 0; 
} 

Dies wäre ein Ausgabebeispiel sein könnte: Ihre Hilfe

INTEGER SEQUENCE ENDED WITH -2: 
45 
-4 
-9 
-3 
13 
64 
789 
-645 
78 
-62 
12 
35 
-14 
6 
0 
21 
-5 
454 
-2 
18 ELEMENTS 
SORT: 
-645 
-14 
-9 
-62 
-5 
-3 
-4 
0 
12 
6 
13 
35 
45 
64 
78 
789 
21 
4254617 

Process returned 0 (0x0) execution time : 31.583 s 
Press any key to continue. 

schätzen!

Answer 1

Sie verwenden den Lomuto-Partitionsansatz. Richtige Weg, es zu tun:

for (int i = left; i <= right-1; i++){ 
     if (t.m[i] <= pivot){ 
      swap(t,n,i,posPivot); 
      posPivot = posPivot+1; 
     } 

Das zweite Problem - Haupt Aufruf sollte sein:

quicksort(t,t.n,0,t.n - 1); 

Answer 2

Sie haben von links zu gehen, bis Sie etwas größere Zahl als Pivot finden und als von rechts nach links, bis Sie eine niedrigere Zahl finden ... (diese zwei Schleifen machen den quicksort extrem schnell ...) dies zu betrachten Code ...

https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort

Sie müssen diese beiden Zeilen:

while Array[L2] < PivotValue do // scan left partition 
    L2 := L2 + 1; 
while Array[R2] > PivotValue do // scan right partition 
    R2 := R2 - 1; 

so hier ist Ihr Problem:

for (int i = left; i < right-1; i++){ 
    if (t.m[i] < pivot){ 
     swap(t,n,i,posPivot); 
     posPivot = posPivot+1; 
    } 
}