QuickSort、参照渡し、再帰

Question

私は奇妙なクイックソートを解決しようとしています。私は配列を分割し、2つの他の配列を作成します：左の配列と右の配列（ピボットなし）と私はそれらを分割します。私のコードは次のとおりです：

#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; 
} 

コードは完全ではありませんが、ここでは実行する必要があります。

エラー（標準エラー出力）と呼ば中止：

ソリューション：malloc.c：2372：sysmalloc：アサーション（old_top ==（（（mbinptr）（（（char型*）私はこのエラーを持っています& & old_size == 0）|| &（（av） - >ビン[（（1）-1）* 2]）） - __builtin_offsetof（struct malloc_chunk、fd））） （（2 *（sizeof（size_t））） - ））&〜（（2 *（sizeof（size_t））） （size_tの））） - 1）））& &（（old_top） - >サイズ&は0x1）& &（（unsigned long型）old_end & pagemask）== 0）」私はそれがあるためだと思う

をfailed.`私は再帰的にベクトルvec1とベクトルvec2の参照を取る関数quickSortを呼び出しています。そして、関数vec1とvec2に再びベクトルを作成します...しかし、私は全くわかりません!!

ような長い質問には再び申し訳ありません

が、それを書くのは簡単ではありません...あなたの答えを事前に

感謝!!!!

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]; 

は明らかにvec2.size()未満arr.size()です。 vec2は簡単にだけ、この問題を修正するにはサイズ2

を持っているarr.size()が10で、かつbが2であれば、その後、ある時点であなたはvec2[3] = arr[3]が、vec2を設定しようとバウンドの外に出ると、おそらくvec1

たとえばことができます、あなたはarr

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

と同じになるようにvec1とvec2のサイズを設定したいこれは、同じサイズの配列を作成し、ZERに値を初期化o。また、aとbがゼロより大きいことを確認してください。アルゴリズムがどのようにqsortに関連しているかわかりません。作業コードについては、以下の例を参照してください。

は便宜上、たとえば、mainにいくつかのランダムな配列を宣言することができます

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

あなたがデータにあなたがアルゴリズムをテストするたびに入る2分を費やす必要はありませんこの方法です。また、あなたは同じコード、たとえば

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

それとも単にstd::swapを使うの繰り返しを避けるためにスワップ機能を書くことができます。qsort例：

#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; 
}