クイックソートをC++で作りたいのですが・・・

質問

題の通り、C++でクイックソートを作りたいのですが、以下のコードではセグメンテーションエラーで動きませんでした。partition関数があやしいと思い、色々と試してみたのですが、やはりできなかったので、質問させていただくことにしました。
結果としては、print関数で昇順に表示出来ればいいのですが・・・。
以下のコードのどこをどう変えれば良いのか、ご指摘の方、何卒よろしくお願い致します。
#include <iostream>
#include <vector>
using namespace std;

class Array {
private:
vector<int> array;
public:
void insert( int value ){ array.push_back( value ); }
int getSize( ){ return (int)array.size( ); }
void quick_sort( ){ quick_sort( 0, (int)array.size( ) - 1 ); }
void quick_sort( int left, int right );
int partition( int left, int right );
void swap(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;}
void print( );
};

// クイックソートにより配列の添字 left ～ right の部分を整列する関数
void Array::quick_sort( int left, int right ) {

if ( left >= right ) {
return;
}

int v = partition( left, right );

quick_sort( left, v - 1 );
quick_sort( v + 1, right );
}

//この関数を考える
// 配列の添字 left ～ right の部分を，pivot の値より小さい要素と，大きい要素に分割し pivot の位置を返す関数
int Array::partition( int left, int right ) {

int i=left; //左からの処理位置
int j=right; //右からの処理位置
int pivot=array[(int)(left+right)/2]; //基準
int tmp=0;

while(true){
while(array[i]<pivot){i++;}
while(array[j]>pivot){j--;}
if(i>=j){return i;}
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
i++;
j++;
}
}

// 配列の内容を表示する関数
void Array::print( ) {
for ( int i = 0; i < (int)array.size( ); i++ ) {
cout << array[i] << " ";
}
cout << endl;
}

int main( ) {

Array a1;

a1.insert( 56 );
a1.insert( 34 );
a1.insert( 57 );
a1.insert( 64 );
a1.insert( 3 );
a1.insert( 87 );
a1.insert( 85 );
a1.insert( 37 );
a1.insert( 21 );
a1.insert( 4 );
a1.insert( 68 );
a1.insert( 62 );
a1.insert( 42 );
a1.insert( 55 );
a1.insert( 63 );
a1.insert( 95 );
a1.insert( 7 );
a1.insert( 32 );
a1.insert( 78 );
a1.insert( 11 );

cout << "要素数: " << a1.getSize( ) << endl;
cout << "ソート前: ";
a1.print( );

a1.quick_sort( ); // ここで，ソートを行う関数を呼び出す

cout << "ソート後: ";
a1.print( );

return 0;
}

回答No.1

akayoroshi · ベストアンサー

添え字の範囲の検査が必要です．作り変えてみました．
// 配列の添字 left ～ right の部分を，pivot の値より小さい要素と，大きい要素に分割し pivot の位置を返す関数
int Array::partition(int left, int right) {
int ipivot = left + (right - left) / 2;
int pivot = array[ipivot]; //基準
Array::swap(&array[left], &array[ipivot]); //基準値を先頭に退避する

int j = right; //右からの処理位置
int i = left + 1; //左からの処理位置

while (true){
while (array[j]>pivot){ j--; }
while (i <= j && array[i] < pivot){ i++; }
if (i >= j) break;
this->swap(&array[i], &array[j]);
i++;
j--;
}
this->swap(&array[left], &array[j]); //基準値をPartition位置に戻す
return j;
}

お礼

見づらいコードだったにも関わらず、丁寧に解読、ご返答してくださり、本当に有難うございました。
解答してくださった関数を、自分なりに解読して理解しようと思います。