さまざまなソートアルゴリズムの概要

ソート アルゴリズムは、最も基本的で一般的に使用されるアルゴリズムです。ソート アルゴリズムは、シナリオやアプリケーションによってパフォーマンスが異なります。ソート アルゴリズムを実際に適用してその利点を最大限に活用するには、さまざまなソート アルゴリズムに精通している必要があります。今日は、さまざまなソートアルゴリズムをまとめてみましょう。

次の表は、さまざまなソートアルゴリズムの複雑さと安定性をまとめたものです。

さまざまなソートアルゴリズムの複雑さの比較.png

バブルソート

バブルソートは最も古典的なソートアルゴリズムです。これは、時間計算量が O(n^2) の比較ベースのソートアルゴリズムです。その利点は、実装が簡単で、n が小さいときにパフォーマンスが向上することです。

• アルゴリズムの原理: 隣接するデータはペアで比較され、小さい数字が前に置かれ、大きい数字が後ろに置かれます。 1 ラウンド後、最小の数字が 1 位にランク付けされ、2 ラウンド目も同じになり、すべてのデータがソートされるまでこれが続きます。

• C++ コードの実装

void bubble_sort( int arr[], int len)
 {
 ( int i = 0 ; i < len - 1 ; i++)の場合
      {
 ( int j = len - 1 ; j >= i ; j--)の場合
          {
もし(arr[j] < arr[j - 1 ])
              {
 temp = arr[j];
                  arr[j] = arr[j - 1 ];
                  arr[j - 1 ] = 一時;
              }
          }
      }
 }

選択ソート

• このアルゴリズムは、まずソートされていないシーケンス内の最小 (最大) の要素を見つけて、それをソートされたシーケンスの先頭に格納することによって機能します。次に、残りのソートされていない要素から最小 (最大) の要素を探し続け、それをソートされたシーケンスの末尾に配置します。すべての要素がソートされるまでこれを繰り返します。

• C++ コードの実装

void select_sort( int arr[], int len)
  {
 ( int i = 0 ; i < len ; i++)の場合
      {
整数インデックス = i;
 ( int j = i + 1 ; j < len ; j++)の場合
          {
 (arr[j] < arr[インデックス])の場合
                  インデックス = j;
          }
 if (インデックス != i)
          {
 temp = arr[i];
              arr[i] = arr[インデックス];
              arr[インデックス] = temp;
          }
      }
  }

挿入ソート

• アルゴリズムの原理では、データを順序付けられた部分と順序付けられていない部分の 2 つの部分に分割します。最初は、順序付けられた部分に最初の要素が含まれ、順序付けられていない要素は、すべての要素が順序付けられるまで、順序付けられた部分に順番に挿入されます。挿入ソートは、直接挿入ソート、バイナリ挿入ソート、リンクリスト挿入などに分けられます。ここでは、直接挿入ソートについてのみ説明します。これは、時間計算量がO(n^2)の安定したソートアルゴリズムです。

• C++ コードの実装

void insert_sort( int arr[], int len)
  {
 ( int i = 1 ; i < len ; i++ )の場合
      {
整数j = i - 1 ;
整数k = arr[i];
 (j > - 1 && k < arr[j] )の場合
          {
              arr[j + 1 ] = arr[j];
              j --;
          }
          arr[j + 1 ] = k;
      }
  }

クイックソート

• アルゴリズムの原理 クイックソートは、実際には非常に効率的なソートアルゴリズムです。安定したソートアルゴリズムではありません。平均時間計算量は O(nlogn) で、最悪の場合の計算量は O(n^2) です。その基本的な考え方は、ソート パスを通じて、ソートするデータが 2 つの独立した部分に分割され、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなり、その後、この方法に従って 2 つの部分のデータが別々にすばやくソートされるというものです。ソート プロセス全体を再帰的に実行して、データ全体を順序付けられたシーケンスに変換できます。

• C++ コードの実装

void quick_sort( int arr[], int左, int右)
 {
 （左 < 右）の場合
  {
 int i = 左、j = 右、ターゲット = arr[左];
一方(i < j)
      {
 ( i < j && arr[j] > ターゲット)
              j--;
もし(i < j)
              arr[i++] = arr[j]; 
 
 (i < j && arr[i] < ターゲット)の場合
              私は++;
もし(i < j)
              arr[j] = arr[i];
      }
      arr[i] = ターゲット;
      quick_sort(arr, 左, i - 1 );
      quick_sort(arr, i + 1 , 右);
  }
 }

マージソート

• アルゴリズムの原理 マージソートの具体的な動作原理は次のとおりです (シーケンスに合計 n 個の要素があると仮定)。

  • シーケンス内の隣接する 2 つの数字を結合して floor(n/2) シーケンスを形成します。ソート後、各シーケンスには 2 つの要素が含まれます。
  • 上記のシーケンスを再度結合して、それぞれ4つの要素を含むfloor(n/4)シーケンスを形成します。

  • すべての要素がソートされるまで手順 2 を繰り返します。

    マージソートは、時間計算量が O(nlogn) の安定したソートアルゴリズムです。リンクリストを使用すると、空間計算量は O(1) に達する可能性があります。ただし、配列を使用してデータを保存する場合、マージ処理中にマージされたデータを保存するための一時的なスペースが必要になるため、空間計算量は O(n) になります。

• C++ コードの実装

void merge( int arr[], int temp_arr[], int start_index, int mid_index, int end_index)
 {
 int i = 開始インデックス、j = 中間インデックス + 1 ;
整数k = 0 ;
 (i < 中間インデックス + 1 && j < 終了インデックス + 1 )の間
     {
もし(arr[i] > arr[j])
             temp_arr[k++] = arr[j++];
それ以外 
             temp_arr[k++] = arr[i++];
     }
 (i < mid_index + 1 )の間
     {
         temp_arr[k++] = arr[i++];
     }
 (j < 終了インデックス + 1 )の間
         temp_arr[k++] = arr[j++]; 
 
 (i = 0 、j = 開始インデックス、j < 終了インデックス + 1 、i++、j++)の場合
         arr[j] = temp_arr[i];
 } 
 
 void merge_sort( int arr[], int temp_arr[], int start_index, int end_index)
 {
 （開始インデックス<終了インデックス）
     {
 int mid_index = (start_index + end_index) / 2 ;
         merge_sort(arr、temp_arr、開始インデックス、中間インデックス);
         merge_sort(arr、temp_arr、mid_index + 1 、end_index);
         マージ(arr、temp_arr、開始インデックス、中間インデックス、終了インデックス);
     }
 }

ヒープソート

バイナリヒープ

バイナリ ヒープは、2 つのプロパティを満たす完全なバイナリ ツリーまたはほぼ完全なバイナリ ツリーです。

• 親ノードのキー値は常に​​子ノードのキー値以上（以下）である
• 各ノードの左サブツリーと右サブツリーはバイナリヒープである

親ノードのキー値が常に子ノードのキー値以上である場合、それはランダム ヒープです。親ノードのキー値が常に子ノードのキー値以下の場合に、最小ヒープが作成されます。一般的に、バイナリ ツリーは単にヒープと呼ばれます。

ヒープストレージ

通常、ヒープの格納には配列が使用され、i ノードの親ノードの添え字は (i – 1) / 2 になります。左と右の子ノードの添字はそれぞれ 2*i+1 と 2*i+2 です。たとえば、0 番目のノードの左と右の子ノードの添え字はそれぞれ 1 と 2 です。ストレージ構造を図に示します。

ヒープ構造.png

ヒープソートの原理

ヒープソートの時間計算量はO(nlogn)である。

• アルゴリズムの原理（***ヒープを例に挙げる）

  • まず、初期データR[1..n]を***ヒープに構築します。これは、初期の順序付けされていない領域です。
  • 次に、レコードR[1]（つまりヒープの先頭）を順序付けされていない領域の最後のレコードR[n]と交換し、新しい順序付けされていない領域R[1..n-1]と順序付けされた領域R[n]を取得し、R[1..n-1].keys≤R[n].keyを満たします。
  • スワップ後の新しいルートR[1]はヒープ特性に違反する可能性があるため、現在の順序付けられていない領域R[1..n-1]をヒープに調整する必要があります。
  • 順序付けられていない領域に要素が 1 つだけになるまで、手順 2 と 3 を繰り返します。

• C++ コードの実装

/**
 * 配列 arr から大きなルートヒープを構築します
 * @param arr 調整する配列
 * @param i 調整する配列要素の添え字
 * @param len 配列の長さ
 */  
 void heap_adjust( int arr[], int i, int len)
 {
整数子;
整数温度; 
 
 ( ; 2 * i + 1 < len; i = 子)
    {
        child = 2 * i + 1 ; // 子ノードの位置 = 2 * 親ノードの位置 + 1  
 // 子ノードの中でキー値が大きいノードを取得します 
 (子 < 長さ - 1 && arr[子 + 1 ] > arr[子])の場合
            子++;
 // 大きい子ノードが親ノードより大きい場合は、大きい子ノードを上に移動し、親ノードを置き換えます 
もし(arr[i] < arr[child])
        {
            temp = arr[i];
            arr[i] = arr[子];
            arr[子] = temp;
        }
それ以外 
壊す;
    }
 } 
 
 /**
 * ヒープソートアルゴリズム
 */  
 void heap_sort( int arr[], int len)
 {
整数i;
 // 最後の要素がシーケンスの最後の要素になるようにシーケンスの前半を調整します 
 ( int i = len / 2 - 1 ; i >= 0 ; i--)の場合
    {
        heap_adjust(arr, i, len);
    } 
 
 (i = len - 1 ; i > 0 ; i--)の場合
    {
 // 最初の要素と最後の要素を入れ替えて、現在のシーケンスの最後の要素が最初の要素になるようにします 
 temp = arr[ 0 ];
        arr[ 0 ] = arr[i];
        arr[i] = 一時;
 // ヒープの範囲を縮小し続け、各調整後に最初の要素が現在のシーケンスの最大値であることを確認します。  
        ヒープ調整(arr, 0 , i);
    }
 }