Quick Sort Programm funktioniert nicht mehr

Question

Ich habe versucht, die schnelle Sortierung - 2 Herausforderung auf hackerrank zu lösen. Es hieß, dass wir die Partition immer wieder aufrufen mussten, bis das gesamte Array sortiert war. Mein Programm funktioniert für einige Testfälle, aber für einige stürzt es ab, "Quick Sort - 2.exe funktioniert nicht mehr". Ich konnte den Grund nicht finden, warum es passiert. Das erste Element des Arrays/Sub-Arrays sollte jedes Mal als Pivot-Element genommen werden.

#include <iostream> 
#include <conio.h> 

using namespace std; 

void swap(int arr[], int a, int b) 
{ 
    int c = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = c; 
} 

void qsort(int arr[], int m, int n) //m - lower limit, n - upper limit 
{ 
    if (n - m == 1) 
    { 
     return; 
    } 

    int p = arr[m], i, j, t;   //p - pivot element, t - temporary 
    //partition 
    for (int i = m+1; i < n; i++) 
    { 
     j = i; 
     if (arr[j] < p) 
     { 
      t = arr[j]; 
      while (arr[j] != p) 
      { 
       arr[j] = arr[j-1]; 
       j--; 
      } 
      arr[j] = t;    //pivot is at j and j+1 
     } 
    } 
    //check if sorted 
    int f = 1; 
    while (arr[f] > arr[f-1]) 
    { 
     if (f == n-1) 
     { 
      f = -1; 
      break; 
     } 
     f++; 
    } 
    if (f == -1) 
    { 
     cout << "Sub Array Sorted\n"; 
    } 
    else 
    { 
     if (p == arr[m])    //pivot is the smallest in sub array 
     { 
      qsort(arr, m+1, n);  //sort right sub array 
     } 
     else 
     { 
      qsort(arr, m, j+1);  //sort left sub array 
      qsort(arr, j+1, n);  //sort right sub array 
     } 
    } 
} 

int main() 
{ 
    int n; 
    cin >> n; 

    int arr[n]; 
    for (int i = 0; i < n; i++) 
    { 
     cin >> arr[i]; 
    } 

    qsort(arr, 0, n); 

    for (int i = 0; i < n; i++) 
    { 
     cout << arr[i] << " "; 
    } 

    return 0; 
} 

Answer 1

Sie haben ein Index außerhalb des Bereichs Problem.

Dies gibt Ihnen keine Lösung, aber es kann Ihnen helfen, den Grund zu finden, warum Ihr Programm fehlschlägt.

Ich habe Ihr Programm so modifiziert, dass es eine vector von int statt einer rohen Array von int verwendet, und wenn Sie dieses Programm ausführen erhalten Sie einen Index Ausnahme außerhalb des zulässigen Bereichs.

Die Sequenz 4 3 7 1 6 4, die das Problem auslöst, ist fest codiert, sodass Sie sie nicht jedes Mal eingeben müssen.

#include <iostream> 
#include <vector> 

using namespace std; 

void swap(vector<int> & arr, int a, int b) 
{ 
    int c = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = c; 
} 

void qsort(vector<int> & arr, int m, int n) //m - lower limit, n - upper limit 
{ 
    if (n - m == 1) 
    { 
    return; 
    } 

    int p = arr[m], j, t;   //p - pivot element, t - temporary 
            //partition 
    for (int i = m + 1; i < n; i++) 
    { 
    j = i; 
    if (arr[j] < p) 
    { 
     t = arr[j]; 
     while (arr[j] != p) 
     { 
     arr[j] = arr[j - 1]; 
     j--; 
     } 
     arr[j] = t;    //pivot is at j and j+1 
    } 
    } 
    //check if sorted 
    int f = 1; 
    while (arr[f] > arr[f - 1]) 
    { 
    if (f == n - 1) 
    { 
     f = -1; 
     break; 
    } 
    f++; 
    } 
    if (f == -1) 
    { 
    cout << "Sub Array Sorted\n"; 
    } 
    else 
    { 
    if (p == arr[m])    //pivot is the smallest in sub array 
    { 
     qsort(arr, m + 1, n);  //sort right sub array 
    } 
    else 
    { 
     qsort(arr, m, j + 1);  //sort left sub array 
     qsort(arr, j + 1, n);  //sort right sub array 
    } 
    } 
} 

int main() 
{ 
    vector<int> arr = { 4,3,7,1,6,4 }; 

    qsort(arr, 0, arr.size()); 

    for (unsigned int i = 0; i < arr.size(); i++) 
    { 
    cout << arr[i] << " "; 
    } 

    return 0; 
} 

Answer 2

Zunächst einmal, was Sie gemacht haben, ist nicht schnell sortieren, aber einige Kombination von division-ans-conquer Partitionierung und Einfügen sortieren.

Kanonische Quicksort geht von unteren (p) und oberen (q) Grenzen des Arrays, überspringende Elemente arr [p] m jeweils. Dann tauscht es arr [p] mit arr [q], inkrementiert/dekrementiert und prüft, ob p> = q. Spülen und wiederholen bis p> = q. Dann rufen Sie Unterpartitionen auf. Auf diese Weise hält p oder q die Schwenkposition und die Unterfälle sind offensichtlich.

Aber Sie tun es anders: Sie fügen Elemente von der rechten Seite des Subarrays auf der linken Seite. Solches kann O (N^2) -Zeitkomplexität für eine Iteration erzeugen. Betrachten wir zum Beispiel 1,0,1,0,1,0,1,0,1,0,1,0, ... Sequenz. Dies kann die Worst-Case-Komplexität gegenüber O (N^2) erhöhen.

Aus Zeitkomplexität ... Das Problem in Ihrer Funktion liegt in Annahme, dass j Schwenkstelle in Unteraufrufen gilt:

qsort(arr, m, j+1);  //sort left sub array 
qsort(arr, j+1, n);  //sort right sub array 

Eigentlich j wird immer wieder gleich i in Ihrem Haupt-for-Schleife . Wenn das letzte Element gleich oder größer als pivot ist, haben Sie am Ende j = n-1, Sie rufen qsort (arr, n, n) auf und die erste Zeilenüberprüfung wird übergeben (sic!), Weil nn! = 1.

dies zu beheben Sie zwei Dinge tun sollten:

arr[j] = t;    //pivot is at j and j+1 

:

1) finden Drehpunkt direkt nach rearrange: nach dieser Zeile

for (int i = m; i < n; i++) 
    if (p == arr[i]) 
    { 
     j = i; 
     break; 
    } 

oder es in verschiedenen Variable initialisieren, update und aktualisieren rekursive Aufrufe neue Variable verwenden anstelle von j

2) eine kugelsicheren Prüfung am Anfang Ihrer Funktion machen:

if (n - m <= 1) 

letztere genug sein wird, einiges Ergebnis zu bekommen, aber es wird viel weniger effektiver als Ihre derzeitige Idee, im schlimmsten Fall bis zu O (N^3) fallen.