メニュー

例を使用したC ++でのクイックソート

quick sort c with examples

問題を排除するために楽器を試してください

イラスト付きのC ++でのクイックソート。

クイックソートは、「ピボット」と呼ばれる特定の要素を選択し、ピボットよりも小さい要素がリストの左側にあるこのピボットs0に基づいて、配列またはリストを2つの部分に分割する広く使用されている並べ替えアルゴリズムです。ピボットよりも大きいのはリストの右側です。

したがって、リストは2つのサブリストに分割されます。同じサイズの場合、サブリストは必要ない場合があります。次に、クイックソートはそれ自体を再帰的に呼び出して、これら2つのサブリストをソートします。

=> ここで完璧なC ++トレーニングガイドをチェックしてください。

クイックソート

学習内容：

前書き

クイックソートは、大きな配列やリストでも効率的かつ高速に動作します。

このチュートリアルでは、クイックソートアルゴリズムのプログラミング例とともに、クイックソートの動作について詳しく説明します。

ピボット値として、最初、最後、中間の値、または任意のランダムな値を選択できます。一般的な考え方は、最終的にピボット値は、配列内の他の要素を左また​​は右に移動することにより、配列内の適切な位置に配置されるというものです。

一般的なアルゴリズム

クイックソートの一般的なアルゴリズムを以下に示します。

quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low

ここで、クイックソート手法の擬似コードを見てみましょう。

クイックソートの擬似コード

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low

パーティショニングアルゴリズムの動作は、例を使用して以下に説明されています。

パーティショニングアルゴリズムの動作

この図では、最後の要素をピボットとして使用しています。配列に単一の要素が含まれるまで、配列がピボット要素の周りで連続的に分割されていることがわかります。

次に、概念をよりよく理解するために、クイックソートの図を以下に示します。

図

クイックソートアルゴリズムの図を見てみましょう。最後の要素をピボットとして持つ次の配列について考えてみます。また、最初の要素には低のラベルが付けられ、最後の要素には高のラベルが付けられます。

クイックソートアルゴリズムの図

ユーザーに尋ねるヘルプデスクの質問

図から、配列の両端でポインターを上下に移動していることがわかります。ローがピボットよりも大きい要素を指し、ハイがピボットよりも小さい要素を指す場合は常に、これらの要素の位置を交換し、ローポインターとハイポインターをそれぞれの方向に進めます。

これは、ローポインタとハイポインタが互いに交差するまで行われます。それらが互いに交差すると、ピボット要素が適切な位置に配置され、配列が2つに分割されます。次に、これらのサブ配列は両方とも、クイックソートを再帰的に使用して個別にソートされます。

C ++の例

以下に示すのは、C ++でのクイックソートアルゴリズムの実装です。

#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout<

出力：

入力配列

12 23 3 43 51 35 19 45

クイックソートでソートされた配列

JavaでのWebサービスインタビューの質問

3 12 19 23 35 43 45 51

ここでは、配列をパーティション分割し、クイックソートを再帰的に呼び出してパーティションをソートするために使用されるルーチン、基本的なクイックソート関数、および配列の内容を表示してそれに応じて2つの要素を交換するユーティリティ関数がいくつかあります。

まず、入力配列を使用してクイックソート関数を呼び出します。クイックソート関数内で、パーティション関数を呼び出します。パーティション関数では、最後の要素を配列のピボット要素として使用します。ピボットが決定されると、配列は2つの部分に分割され、クイックソート関数が呼び出されて、両方のサブ配列が個別にソートされます。

クイックソート関数が戻ると、配列は、ピボット要素が正しい位置にあり、ピボットよりも小さい要素がピボットの左側にあり、ピボットよりも大きい要素がピボットの右側にあるように並べ替えられます。

次に、Javaでクイックソートアルゴリズムを実装します。

Javaの例

// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j

出力：

入力配列

12 23 3 43 51 35 19 45

クイックソートでソートした後の配列

3 12 19 23 35 43 45 51

Java実装でも、C ++実装で使用したのと同じロジックを使用しました。配列の最後の要素をピボットとして使用し、ピボット要素を適切な位置に配置するために配列に対してクイックソートを実行しました。

クイックソートアルゴリズムの複雑さの分析

クイックソートが配列をソートするのにかかる時間は、入力配列とパーティションの戦略または方法によって異なります。

kがピボットより少ない要素の数であり、nが要素の総数である場合、クイックソートにかかる一般的な時間は次のように表すことができます。

T（n）= T（k）+ T（n-k-1）+ O（n）

ここで、T（k）とT（n-k-1）は再帰呼び出しにかかる時間であり、O（n）はパーティション呼び出しにかかる時間です。

クイックソートのために、この時間計算量を詳細に分析しましょう。

＃1）最悪の場合 ：クイックソート手法の最悪のケースは、ほとんどの場合、配列内の最低または最高の要素をピボットとして選択した場合に発生します。 （上の図では、ピボットとして最も高い要素を選択しています）。このような状況では、ソートされる配列がすでに昇順または降順でソートされている場合に最悪のケースが発生します。

したがって、合計所要時間の上記の式は次のように変化します。

T（n）= T（0）+ T（n-1）+ O（n） に解決します オン二）

＃2）ベストケース： クイックソートの最良のケースは、選択されたピボット要素が配列の中央にある場合に常に発生します。

したがって、最良の場合の再発は次のとおりです。

最高評価のyoutubeからmp3へのコンバーター

T（n）= 2T（n / 2）+ O（n）= O（nlogn）

＃3）平均的なケース： クイックソートの平均的なケースを分析するには、すべての配列順列を考慮してから、これらの順列のそれぞれにかかる時間を計算する必要があります。一言で言えば、クイックソートの平均時間もO（nlogn）になります。

クイックソート手法のさまざまな複雑さを以下に示します。

最悪の場合の時間計算量O（n 2）
安定同じ値の2つの要素が同じ順序で配置されないため、安定していません。安定–同じ値を持つ2つの要素が、並べ替えられた出力に同じ順序で表示されます。
ベストケースの時間計算量O（n * log n）
平均時間計算量O（n * log n）
スペースの複雑さO（n * log n）

ピボット要素（中央、最初、最後）の選択を変更するだけで、さまざまな方法でクイックソートを実装できますが、クイックソートで最悪のケースが発生することはめったにありません。

3ウェイクイックソート

元のクイックソート手法では、通常、ピボット要素を選択してから、このピボットの周りで配列をサブ配列に分割し、1つのサブ配列がピボットよりも小さい要素で構成され、もう1つがピボットよりも大きい要素で構成されるようにします。

しかし、ピボット要素を選択し、配列内にピボットに等しい要素が複数ある場合はどうなるでしょうか。

例えば、 次の配列{5,76,23,65,4,4,5,4,1,1,2,2,2,2}について考えてみます。この配列で単純なクイックソートを実行し、ピボット要素として4を選択すると、要素4の1つのオカレンスのみが修正され、残りは他の要素と一緒に分割されます。

代わりに、3ウェイクイックソートを使用する場合、配列(l…r)を次のように3つのサブ配列に分割します。

  1. Array (l…i) –ここで、iはピボットであり、この配列にはピボットよりも小さい要素が含まれています。
  2. Array (i + 1…j-1) –ピボットに等しい要素が含まれています。
  3. Array (j…r) –ピボットより大きい要素が含まれています。

したがって、配列に複数の冗長要素がある場合は、3ウェイクイックソートを使用できます。

ランダム化されたクイックソート

クイックソート手法は、乱数を使用してピボット要素を選択する場合、ランダム化クイックソート手法と呼ばれます。ランダム化されたクイックソートでは、「中央ピボット」と呼ばれ、各辺が少なくとも1/4の要素を持つように配列を分割します。

ランダム化されたクイックソートの擬似コードを以下に示します。

// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedure

上記の「randomQuickSort」のコードでは、ステップ2で中央ピボットを選択します。ステップ2では、選択した要素が中央のピボットになる確率は1/2です。したがって、ステップ2のループは2回実行されると予想されます。したがって、ランダム化されたクイックソートのステップ2の時間計算量はO（n）です。

ループを使用して中央ピボットを選択することは、ランダム化されたクイックソートを実装するための理想的な方法ではありません。代わりに、要素をランダムに選択して中央ピボットと呼ぶか、配列要素を再シャッフルすることができます。ランダム化されたクイックソートアルゴリズムで予想される最悪の場合の時間計算量はO（nlogn）です。

クイックソートとマージソート

このセクションでは、クイックソートとマージソートの主な違いについて説明します。

比較パラメータクイックソートマージソート
パーティショニング配列はピボット要素を中心に分割されており、必ずしも2つに分割されているとは限りません。任意の比率で分割できます。配列は2つの半分（n / 2）に分割されます。
最悪の場合の複雑さO（n 2）–最悪の場合、多くの比較が必要です。O（nlogn）–平均的な場合と同じ
データセットの使用法より大きなデータセットではうまく機能しません。サイズに関係なく、すべてのデータセットで適切に機能します。
追加スペースインプレース–追加のスペースは必要ありません。所定の位置にない–補助アレイを格納するために追加のスペースが必要です。
ソート方法内部–データはメインメモリでソートされます。外部–データ配列を格納するために外部メモリを使用します。
効率小さいサイズのリストの場合、より高速で効率的です。大きなリストの場合は高速かつ効率的です。
配列/リンクリストアレイに適しています。リンクリストに適しています。

結論

名前自体が示すように、クイックソートは、他のどのソートアルゴリズムよりもリストをすばやくソートするアルゴリズムです。マージソートと同様に、クイックソートも分割統治戦略を採用しています。

すでに見てきたように、クイックソートを使用して、ピボット要素を使用してリストをサブ配列に分割します。次に、これらのサブ配列は個別にソートされます。アルゴリズムの最後に、配列全体が完全にソートされます。

クイックソートはより高速で、データ構造のソートに効率的に機能します。クイックソートは一般的なソートアルゴリズムであり、マージソートアルゴリズムよりも好まれる場合もあります。

次のチュートリアルでは、シェルソートについて詳しく説明します。

=> ここで簡単なC ++トレーニングシリーズに注意してください。

推奨読書

^