introduction sorting techniques c
デフォルトゲートウェイは利用できません
C ++でのさまざまなソート手法のリスト。
並べ替えは、データを特定の順序で並べ替えるために実装される手法です。並べ替えは、使用するデータが特定の順序になっていることを確認して、データの山から必要な情報を簡単に取得できるようにするために必要です。
データが空でソートされていない場合、特定の情報が必要な場合は、データを取得するために毎回1つずつ検索する必要があります。
=> Easy C ++トレーニングシリーズをお読みください。
したがって、情報の取得やデータに対して実行されるその他の操作を簡単かつ効率的に実行できるように、データを特定の順序で配置しておくことを常にお勧めします。
データはレコードの形で保存されます。各レコードは、1つ以上のフィールドで構成されています。各レコードに特定のフィールドの一意の値がある場合、それをキーフィールドと呼びます。 例えば、 クラスでは、ロール番号は一意のフィールドまたはキーフィールドにすることができます。
特定のキーフィールドでデータを並べ替えてから、昇順/昇順または降順/降順で並べ替えることができます。
同様に、電話辞書では、すべてのレコードは人の名前、住所、電話番号で構成されます。この場合、電話番号は一意のフィールドまたはキーフィールドです。この電話フィールドで辞書のデータを並べ替えることができます。または、データを数値またはアルファベット順に並べ替えることもできます。
別の補助メモリを必要とせずにメインメモリ自体でソートされるようにデータを調整できる場合、それを次のように呼び出します。 内部ソート 。
一方、ソート中に中間データを格納するための補助メモリが必要な場合は、この手法を次のように呼び出します。 外部ソーティング 。
このチュートリアルでは、C ++でのさまざまな並べ替え手法について詳しく学習します。
学習内容：
C ++でのソート手法
C ++は、以下に示すさまざまなソート手法をサポートしています。
バブルソート
バブルソートは、すべての要素を隣接する要素と比較し、順序が正しくない場合は要素を交換する最も簡単な手法です。このようにして、すべての反復（パスと呼ばれる）の終わりに、最も重い要素がリストの最後にバブルアップされます。
以下に、バブルソートの例を示します。
ソートする配列：
上で見たように、それは小さな配列であり、ほとんどソートされているため、数回のパスで完全にソートされた配列を取得することができました。
C ++でバブルソート手法を実装しましょう。
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < 出力：
入力リスト…
10 2 0 43 12
ソートされた要素リスト…
0 2 10 12 43
出力からわかるように、バブルソート手法では、パスごとに最も重い要素が配列の最後までバブルされ、それによって配列が完全にソートされます。
選択ソート
リスト内で最小の要素を見つけて適切な場所に配置する手法は、シンプルでありながら実装が簡単です。各パスで、次に小さい要素が選択され、適切な位置に配置されます。
前の例と同じ配列を使用し、選択ソートを実行してこの配列をソートします。
上の図に示すように、N個の要素について、N-1パスを使用して配列を完全に並べ替えます。すべてのパスの終わりに、配列内の最小の要素が、ソートされた配列内の適切な位置に配置されます。
次に、C ++を使用して選択ソートを実装しましょう。
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< 出力：
ソートする要素の入力リスト
12 45 8 15 33
要素のソートされたリストは
8 12 15 33 45
選択ソートでは、パスごとに、配列内の最小の要素が適切な位置に配置されます。したがって、並べ替えプロセスの最後に、完全に並べ替えられた配列を取得します。
挿入ソート
挿入ソートは、リストの2番目の要素から開始する手法です。 2番目の要素を前の要素と比較します（1st）要素を配置し、適切な場所に配置します。次のパスでは、要素ごとに、それを前のすべての要素と比較し、その要素を適切な場所に挿入します。
上記の3つの並べ替え手法は、シンプルで実装が簡単です。これらの手法は、リストサイズが小さい場合にうまく機能します。リストのサイズが大きくなると、これらの手法ではそれを効率的に実行できなくなります。
次の図を理解することで、テクニックが明確になります。
ソートされる配列は次のとおりです。
ここで、パスごとに、現在の要素を以前のすべての要素と比較します。したがって、最初のパスでは、2番目の要素から始めます。
したがって、N個の要素を含む配列を完全にソートするには、N個のパスが必要です。
C ++を使用して挿入ソート手法を実装しましょう。
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < 出力：
入力リストは
12 4 3 1 15
ソートされたリストは
1 3 4 12 15
上記の出力は、挿入ソートを使用して完全にソートされた配列を示しています。
クイックソート
クイックソートは、データの並べ替えに使用できる最も効率的なアルゴリズムです。この手法では、問題をいくつかのサブ問題に分割し、これらのサブ問題を個別に解決した後、完全にソートされたリストにマージする「分割統治」戦略を使用します。
クイックソートでは、最初にピボット要素の周りにリストを分割し、次にピボット要素に従って他の要素を適切な位置に配置します。
上の図に示すように、クイックソート手法では、ピボットよりも小さい要素がすべて左側にあり、ピボットよりも大きい要素のどれが右側にあるように、ピボット要素の周りに配列を分割します。次に、これら2つの配列を個別に取得して並べ替え、結合または征服して、結果の並べ替えられた配列を取得します。
クイックソートの鍵は、ピボット要素の選択です。配列の最初、最後、または中央の要素にすることができます。ピボット要素を選択した後の最初のステップは、配列を適切に分割できるように、ピボットを正しい位置に配置することです。
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 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
クイックソートでソートされた配列
3 12 23 43 51
上記のクイックソートの実装では、配列の最後の要素であるピボット要素の周りに入力配列を分割するために使用される分割ルーチンがあります。次に、クイックソートルーチンを再帰的に呼び出して、図に示すようにサブ配列を個別にソートします。
マージソート
これは、「分割統治」戦略を使用するもう1つの手法です。この手法では、最初にリストを均等に分割します。次に、これらのリストに対して個別にマージソート手法を実行して、両方のリストがソートされるようにします。最後に、両方のリストをマージして、完全にソートされたリストを取得します。
マージソートとクイックソートは、他のほとんどのソート手法よりも高速です。リストのサイズが大きくなっても、パフォーマンスは損なわれません。
マージソート手法の図を見てみましょう。
上の図では、マージソート手法により、元の配列がサブ配列に繰り返し分割され、各サブ配列に要素が1つだけになることがわかります。これが完了すると、サブ配列は個別に並べ替えられ、マージされて完全に並べ替えられた配列になります。
次に、C ++言語を使用してマージソートを実装しましょう。
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< 出力：
ソートする要素の数を入力してください：5
並べ替える要素を5つ入力してください：1021 47 3 59
ソートされた配列
3 10 21 47 59
シェルソート
シェルソートは、挿入ソート手法の拡張です。挿入ソートでは、次の要素のみを処理しますが、シェルソートでは、親リストから小さなリストを作成するための増分またはギャップを提供します。サブリストの要素は連続している必要はなく、通常は「gap_value」離れています。
シェルソートは挿入ソートよりも高速に実行され、挿入ソートよりも少ない移動で済みます。
のギャップを提供すると、3つの要素が離れている各要素を持つ次のサブリストが作成されます。
次に、これら3つのサブリストを並べ替えます。
ソートされたサブ配列をマージした後に取得した上記の配列は、ほぼソートされています。これで、この配列に対して挿入ソートを実行して、配列全体をソートできます。
したがって、適切な増分を使用して配列をサブリストに分割し、それらをマージすると、ほぼソートされたリストが得られることがわかります。このリストの挿入ソート手法を実行でき、配列は元の挿入ソートよりも少ない移動でソートされます。
以下に示すのは、C ++でのシェルソートの実装です。
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i 出力：
ソートする配列：
45 23 53 43 18
シェルソート後の配列：
18 23 43 45 53
したがって、シェルソートは挿入ソートよりも大幅に改善されており、配列をソートするための手順の半分もかかりません。
ヒープソート
ヒープソートは、ヒープデータ構造（最小ヒープまたは最大ヒープ）を使用してリストを並べ替える手法です。まず、ソートされていないリストからヒープを作成し、そのヒープを使用して配列をソートします。
ヒープソートは効率的ですが、マージソートほど速くはありません。
上の図に示すように、最初に、並べ替える配列要素から最大ヒープを作成します。次に、ヒープをトラバースして、最後の要素と最初の要素を交換します。この時点で、最後の要素はすでにソートされています。次に、残りの要素から最大ヒープを再度構築します。
再びヒープをトラバースし、最初と最後の要素を交換して、最後の要素をソート済みリストに追加します。このプロセスは、ソートされたリストの最初の要素となる要素がヒープに1つだけ残るまで続けられます。
C ++を使用してヒープソートを実装しましょう。
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i 出力：
入力配列
4 17 3 12 9
ソートされた配列
3 4 9 12 17
これまで、すべての主要な並べ替え手法について、図を使用して簡単に説明してきました。これらの各テクニックについては、以降のチュートリアルで、各テクニックを理解するためのさまざまな例とともに詳しく学習します。
結論
データを適切な順序で並べ替えるには、並べ替えが必要です。ソートされておらず、空っぽでない場合、アクセスに時間がかかる可能性があり、プログラム全体のパフォーマンスに影響を与える可能性があります。したがって、アクセス、検索、操作などのデータに関連する操作については、データを並べ替える必要があります。
プログラミングには多くのソート手法が採用されています。各手法は、使用しているデータ構造、またはアルゴリズムがデータを並べ替えるのにかかる時間、またはアルゴリズムがデータを並べ替えるのにかかるメモリ空間に応じて使用できます。使用している手法は、並べ替えるデータ構造によっても異なります。
並べ替え手法を使用すると、データ構造を特定の順序で並べ替え、要素を昇順または降順で並べ替えることができます。バブルソート、選択ソート、挿入ソート、クイックソート、シェルソート、マージソート、ヒープソートなどのソート手法を見てきました。バブルソートと選択ソートは、よりシンプルで実装が簡単です。
以降のチュートリアルでは、上記の各並べ替え手法について詳しく説明します。
=> 無料のC ++コースについては、ここをクリックしてください。
推奨読書
