QuickSort, Pass-by-Referenz, Rekursion

Question

Ich versuche, eine Art von seltsamen QuickSort zu lösen. Ich partitioniere das Array und ich erstelle 2 andere Arrays: das linke Array und das rechte Array (ohne den Pivot) und ich partitioniere sie und so weiter. Mein Code ist dies:

#include <bits/stdc++.h> 

using namespace std; 

int partition(vector<int>& ar) { 
    int pivot=ar[0]; 
    int store=0; 
    for(int i=0;i<ar.size();i++) 
    { 
     if(ar[i]<pivot) 
     { 
      store++; 
      int temp=ar[store]; 
      ar[store]=ar[i]; 
      ar[i]=temp; 
     } 
    } 
    for(int i=0;i<store;i++){ 
     int temp=ar[i]; 
     ar[i]=ar[i+1]; 
     ar[i+1]=temp; 
    } 
    for(int i=ar.size()-2;i>store;i--){ 
     int temp=ar[i+1]; 
     ar[i+1]=ar[i]; 
     ar[i]=temp; 
    } 
    return store; } 

void quickSort(vector <int>& arr) { 
    if(arr.size()<=1) 
    { 
     return; 
    } 
    int a=partition(arr); 
    vector <int> vec1(a); 
    int b=arr.size()-a-1; 
    vector <int> vec2(b); 
    for(int i=0;i<a;i++) 
    { 
     vec1[i]=arr[i]; 
    } 
    for(int i=a+1;i<arr.size();i++) 
    { 
     vec2[i]=arr[i]; 
    } 
    if(vec1.size()<2 && vec2.size()<2) 
    { 
     for(int i=0;i<arr.size();i++) 
     { 
      cout<<arr[i]<<" "; 
     } 
     cout<<endl; 
     return; 
    } 
    else{ 
     quickSort(vec1); 
     quickSort(vec2); 

    } 
} 

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

    vector <int> arr(n); 
    for(int i = 0; i < (int)n; ++i) { 
     cin >> arr[i]; 
    } 
    quickSort(arr); 
    for(int i =0; i <arr.size(); i++) 
    { 
     cout<<arr[i]<<" "; 
    } 

    return 0; 
} 

Der Code wird überhaupt nicht fertig, aber hier sollte es laufen, während es nicht der Fall ist. Ich habe diesen Fehler:

Abort Called

Fehler (stderr):

Lösung: malloc.c: 2372: SysMalloc: Assertion (old_top == (((mbinptr) (((char *) & ((av) -> Bins [((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) & & old_size == 0) || ((vorzeichenlos lang) (old_size)> = (vorzeichenlos lang) (((__ builtin_offsetof (struct malloc_chunk, fd_nextsize)) + ((2 * (sizeof (size_t))) - 1)) & ~ ((2 * (sizeof (size_t))) - 1))) & & ((old_top) -> Größe & 0x1) & & ((unsigned long) old_end & pagemask) == 0)‘failed.`

ich denke, es liegt daran, Ich rufe rekursiv die Funktion quickSort auf, die die Referenz von Vektor vec1 und Vektor vec2 nimmt, und dann erstelle ich in der Funktion wieder Vektor vec1 und vec2 ... Aber ich bin überhaupt nicht sicher !!

Leider wieder für eine so lange Frage, aber es ist es nicht einfach zu schreiben ...

Vielen Dank im Voraus für Ihre Antworten !!!!

Answer 1

if (arr.size() <= 1) 
    return; 

int a = partition(arr); 
vector<int> vec1(a); 
for (int i = 0; i<a; i++) 
    vec1[i] = arr[i]; 

int b = arr.size() - a - 1; 
vector<int> vec2(b); 
for (int i = a + 1; i<(int)arr.size(); i++) 
    vec2[i] = arr[i]; 

Klar vec2.size() weniger als arr.size(). vec2 kann leicht gebundener gehen, und möglicherweise vec1

Zum Beispiel, wenn arr.size() ist 10, und b ist 2, dann an einem Punkt, den Sie versuchen vec2[3] = arr[3] zu setzen, sondern vec2 hat nur eine Größe 2.

dies zu beheben Sie möchten eine Größe von vec1 und vec2 setzen die gleichen wie arr

vector<int> vec1(arr.size(), 0); 
vector<int> vec2(arr.size(), 0); 

Dies schafft Array von gleicher Größe zu sein, und initialisiert die Werte zihr O. Stellen Sie außerdem sicher, dass a und b größer als Null sind. Ich sehe nicht, wie sich der Algorithmus auf qsort bezieht. Siehe das folgende Beispiel für den Arbeitscode.

vector<int> arr{ 7,3,6,1,4,8,9,2 }; 

Auf diese Weise müssen bis 2 Minuten nicht verbringen Daten jedes Mal eingeben, die Sie den Algorithmus testen:

Der Einfachheit halber können Sie einige zufällige Anordnung in main, Beispiel erklären. Sie können auch eine Swap-Funktion zu vermeiden, schreiben Sie den gleichen Code zu wiederholen, zB

void myswap(int &a, int &b) 
{ 
    int temp = a; 
    a = b; 
    b = temp; 
} 

Oder einfach std::swap verwenden.qsort Beispiel:

#include <iostream> 
#include <vector> 

using std::cout; 

int qsort_partition(std::vector<int> &arr, const int left, const int right) 
{ 
    const int mid = left + (right - left)/2; 
    const int pivot = arr[mid]; 

    std::swap(arr[mid], arr[left]); 
    int i = left + 1; 
    int j = right; 
    while (i <= j) 
    { 
     while (i <= j && arr[i] <= pivot) 
      i++; 

     while (i <= j && arr[j] > pivot) 
      j--; 

     if (i < j) 
      std::swap(arr[i], arr[j]); 
    } 
    std::swap(arr[i - 1], arr[left]); 
    return i - 1; 
} 

void qsort(std::vector<int> &arr, const int left, const int right) 
{ 
    if (left >= right) return; 
    int partition = qsort_partition(arr, left, right); 
    qsort(arr, left, partition - 1); 
    qsort(arr, partition + 1, right); 
} 

void my_qsort(std::vector<int> &arr) 
{ 
    qsort(arr, 0, arr.size() - 1); 
} 

int main() 
{ 
    std::vector<int> arr{ 7,3,6,1,4,8,9,2 }; 
    my_qsort(arr); 
    return 0; 
}