クイックソート

マージソートのように、クイックソートは分割と征服アルゴリズムです.それはピボットとして要素を選び、選ばれたピボットの周りの与えられた配列を分割します.さまざまな方法でピボットを選ぶクイックソートのさまざまなバージョンがあります.
常にピボットとして最初の要素を選択します.
常にピボットとして最後の要素を選択します(後述).
ピボットとしてランダムな要素を選択します.
ピボットとしてメディアンを選択します.
quicksortのキープロセスはパーティション()です.パーティションの対象は配列の配列と要素のxをピボットとし、ソートされた配列の正しい位置にxを置き、xより前のすべての小さな要素(xより小さい)を入れ、xの後にすべてのより大きい要素(xより大きい)を置く.
再帰的なQuicksort関数の擬似コード
/* low -> start index , high ->終了インデックス/
クイックソート( arr [], low , high )
{ }
を返します.
{ }
/piは分割インデックス、arr [ pi ]は現在です
適切な場所で
pi =パーティション( arr , low , high );

    quickSort(arr, low, pi - 1);  // Before pi
    quickSort(arr, pi + 1, high); // After pi
}

｝
クイックソート
パーティションアルゴリズム
パーティションを行うには多くの方法があります.論理は簡単です、我々は左端の要素から始めて、より小さい(または等しい)要素のインデックスを追跡します.それ以外の場合は、現在の要素を無視します.
/* low -> start index , high ->終了インデックス/
クイックソート( arr [], low , high )
{ }
を返します.
{ }
/piは分割インデックス、arr [ pi ]は現在です
適切な場所で
pi =パーティション( arr , low , high );

    quickSort(arr, low, pi - 1);  // Before pi
    quickSort(arr, pi + 1, high); // After pi
}

｝
パーティション()用の擬似コード
/*この関数は最後の要素をピボットとします
ソートされた位置のピボット要素
を返します.
ピボットとすべてのより大きい要素の左側に
ピボット*/
パーティション( arr [], low , high )
{ }
//ピボット(正しい位置に配置する要素)
ピボット= ARR [ハイ];

i = (low - 1)  // Index of smaller element and indicates the 
               // right position of pivot found so far

for (j = low; j <= high- 1; j++)
{
    // If current element is smaller than the pivot
    if (arr[j] < pivot)
    {
        i++;    // increment index of smaller element
        swap arr[i] and arr[j]
    }
}
swap arr[i + 1] and arr[high])
return (i + 1)

｝
パーティションの説明:
arr []={ 10 , 80 , 30 , 90 , 40 , 50 , 70 }
インデックス:0 1 2 3 4 5 6
ロー= 0 ,ハイ= 6 ,ピボット= ARR [ H ] = 70
より小さい要素のインデックスを初期化する
j = lowからhigh 1への要素の横断
j = 0 : arr [ j ] <= =ピボット、i++とswap ( arr [ i ], arr [ j ] )を行う
i = 0
ARR []={ 10 , 80 , 30 , 90 , 40 , 50 , 70 }//iとjの変更はありません
//同じです
j = 1 : arr [ j ]>ピボット以来、何もしません
//iとarr [
j = 2 : arr [ j ]<= pib , i++とswap ( arr [ i ], arr [ j ] )を行う
I = 1
ARR []={ 10 , 30 , 80 , 90 , 40 , 50 , 70 }//80と30を交換する
j = 3 : arr [ j ]>ピボットから何もしない
//iとarr [
j = 4 : arr [ j ] <= =ピボット、i++とswap ( arr [ i ], arr [ j ] )を行う
I = 2
arr []={ 10 , 30 , 40 , 90 , 80 , 50 , 70 }/80 , 40 swap
j = 5 : arr [ j ]<=ピボットから、arr [ j ]でi++とswap arr [ i ]を実行します
I = 3
ARR [] = { 10 , 30 , 40 , 50 , 80 , 90 , 70 }/90 , 50スワップ
Jが現在ハイ1に等しいので、我々はループから出ます.
最後に、ピッピングで正しい位置にピボットを置きます
ARR [ I + 1 ]とARR
ARR [] = { 10 , 30 , 40 , 50 , 70 , 90 , 80 }/80 , 70スワップ
今70は正しい場所です.すべての要素より小さい
70はそれより前であり、70より大きいすべての要素は後である
それ.
推奨:最初に解決する前に“練習”を解決してください.
実装
以下はQuicksortの実装です.
/* C++クイックソートの実装

含める
名前空間stdの使用;
//2つの要素を交換するユーティリティ関数
void swap ( int * a , int * b )
{ }
int t =\a ;
とは
* b = t ;
｝
/*この関数は最後の要素をピボットとします
ソートされた位置のピボット要素
を返します.
ピボットとすべてのより大きい要素の左側に
ピボット*/
intパーティション( int arr [], int low , int high )
{ }
intピボット= arr [ high ];/ピボット
int i = ( low - 1 );/より小さい要素のインデックスとこれまで見つけたピボットの正しい位置を示します

for (int j = low; j <= high - 1; j++)
{
    // If current element is smaller than the pivot
    if (arr[j] < pivot)
    {
        i++; // increment index of smaller element
        swap(&arr[i], &arr[j]);
    }
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);

｝
/*クイックソートを実装する主関数
arr []->ソートする配列
ロー->開始インデックス
結末インデックス;
void quicksort ( int arr [], int low , int high )
{ }
を返します.
{ }
/piは分割インデックス、arr [ p ]は現在です
適切な場所で
int pi =パーティション( arr , low , high );

    // Separately sort elements before
    // partition and after partition
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
}

｝
/*配列を出力する関数*/
void printarray ( int arr [], int size )
{ }
int I ;
( i = 0 ; I < size , i++)
<武井>
コールアウト
｝
//ドライバコード
int main ()
{ }
int arr []={ 10 , 7 , 8 , 9 , 1 , 5 }
int n = sizeof ( arr )/sizeof ( arr [ 0 ]);
クイックソート( arr , 0 , n - 1 )
ソートされた配列
printarray ( arr , n );
0を返す
｝
//このコードはRathbhupendraによって投稿されます
出力
ソート済み配列:
1 5 7 7 8 9
最良の場合:パーティションプロセスが常に中心要素をピボットとして選択したときに最も良いケースが発生します.以下は最良症例の再発である.
t ( n )= 2 T ( n/2 )+\θ( n )
上記再帰の解は\θ(nlogn)である.マスター定理のcase 2を用いて解くことができる.