なぜソートするのですか?ソートアルゴリズムのパフォーマンスを向上させる方法

この記事は、公開アカウント「Reading the Core」（ID: AI_Discovery）から転載したものです。

並べ替えの用途は何でしょうか? 辞書がアルファベット順に並んでいなかったら、単語を調べるのにどれくらいの時間がかかるでしょうか? 人々が分類の概念を導入したのは、項目をすばやく検索するのに非常に役立つためです。

では、ソートを実現するにはどうすればよいでしょうか? これらのソート アルゴリズムを理解する必要があります。

[[356090]]

バブルソート

これは最も単純なソートアルゴリズムです。隣接する要素の各ペアを比較し、要素が順序どおりになっているかどうかを確認します。順序どおりになっていない場合は、すべての要素が並べ替えられるまで 2 つの要素を交換します。

 for(int i = 0 ; i <   n ; i++){
           for(int j = 0 ; j <   n -1; j++){
               (arr[j] > arr[j+1])の場合{
                   temp = arr [j];
                   arr[j] = arr[j+1];
                   arr[j+1] = 温度;
              }
           }
       }

[[356091]]

画像出典: Google

（１）パフォーマンス分析：

時間の計算量:

• 最悪の場合: O(n²) — n 個の要素を n 回ループし、n は配列の長さなので、バブルソートの時間計算量は O(n²) になります。
• 最良のケース: O(n²) — 配列がすでにソートされている場合でも、アルゴリズムは隣接するすべてのペアをチェックするため、最良のケースの時間計算量は最悪のケースと同じになります。

空間計算量: O(1)。

配列のみが入力され、追加のデータ構造は使用されないため、空間計算量は O(1) になります。

（２）改良バブルソート：

コードを見ると、上記のソートアルゴリズムでは、配列がすでにソートされている場合でも、時間の計算量は同じ、つまり O(n²) になることがわかります。

この問題を克服するために、改良されたアルゴリズムが提案されています。配列がソートされているかどうかを判断するフラグを作成し、すべての隣接するペア間でスワップが発生したかどうかを確認します。配列全体を反復処理しているときにスワップがない場合、配列は完全にソートされているため、ループを終了できます。これにより、アルゴリズムの時間計算量が大幅に削減されます。

 for(int i = 0 ; i <   n ; i++){
           ブール値isSwapped = false ;
           for(int j = 0 ; j <   n -1; j++){
              (arr[j] > arr[j+1])の場合{
                   temp = arr [j];
                   arr[j] = arr[j+1];
                   arr[j+1] = 温度;
スワップ済み= true ;
               }
           if(!isSwapped){
               壊す;
            }
          }
       }

（３）パフォーマンス分析：

時間の計算量:

• 最悪の場合: O(n²) — 上記のアルゴリズムと同じ。
• 最良のケース: O(n) - このアルゴリズムでは、配列がすでにソートされている場合はループが中断されるため、最良のケースでは時間の計算量は O(n) になります。

空間計算量: O(1)。

選択ソート

ソート アルゴリズムでは、最初の要素が最小要素であると想定し、次に配列の残りの部分をチェックして、想定された最小値よりも小さい要素があるかどうかを確認します。存在する場合は、想定される最小値と実際の最小値を入れ替え、存在しない場合は次の要素に進みます。

 for(int i = 0 ; i < arr.length ; i++) {
                     最小インデックス= i;
                     for(int j = i +1; j < arr.length ; j++) {
                        arr[j] < arr [最小インデックス]) {
最小インデックス= j ;
                        }
                     }
                     temp = arr [i];
                     arr[i] = arr[最小インデックス];
                     arr[最小インデックス] = temp;
                  }

パフォーマンス分析:

時間の計算量:

• 最悪の場合: O(n²) — 配列内の各要素について、配列の残りの部分を走査して最小値を見つけるため、時間の計算量は O(n²) になります。
• 最良のケース: O(n²) — 配列がソートされていても、アルゴリズムは配列の残りの部分で最小値を見つけるので、最良のケースの時間計算量は最悪のケースと同じです。

空間計算量: O(1)。

前のアルゴリズムと同様に、入力配列以外の追加のデータ構造は使用されない為、空間計算量は O(1) になります。

挿入ソート

このソートアルゴリズムでは、各要素について、現在の要素まで正しい順序になっているかどうかがチェックされます。最初の要素は順序が揃っているので、2 番目の要素から開始して順序が正しいかどうかを確認し、そうでない場合は要素を交換します。したがって、任意の要素において、現在の要素が前の要素より大きいかどうかを確認します。そうでない場合は、現在の要素が前の要素より大きくなるまで要素の交換を続けます。

 for(int i = 1 ; i <   n ; i++) {
           整数j = i ;
           while(j > 0&& arr[j] <   arr [j-1]) {
               temp = arr [j];
               arr[j] = arr[j-1];
               arr[j-1] = 一時;
               j--;
           }
       }

パフォーマンス分析:

時間の計算量:

• 最悪の場合: O(n²) — 最悪の場合、配列は降順でソートされます。したがって、各要素を調べて左にスワップする必要があります。
• 最良のケース: O(n) — 最良のケースでは、配列はすでにソートされています。したがって、各要素については、現在の要素のみが左側の要素と比較されます。順序が正しいため、スワッピングは発生せず、次の要素に進みます。したがって、時間の計算量は O(n) になります。

空間計算量: O(1)。

入力配列以外の追加のデータ構造は使用されないため、空間計算量は O(1) になります。

クイックソート

クイックソートはパーティションソートとも呼ばれます。このソートアルゴリズムは、分割統治の概念により、以前のアルゴリズムよりも効率的です。

まずピボットを決定し、次にピボット位置の正しいインデックスを見つけて、配列を 2 つのサブ配列に分割します。 1 つのサブ配列にはピボットよりも小さい要素が含まれ、もう 1 つのサブ配列にはピボットよりも大きい要素が含まれます。次に、配列がそれ以上分割できなくなるまで、これら 2 つのサブ配列を再帰的に呼び出します。

パブリック静的voidクイックソート(int[] arr、int low、int high) {
                    if(low > = high) 戻り値:
                    int pivotPosition =パーティション(arr、low、high);
                    クイックソート(arr,low,pivotPosition-1);
                    クイックソート(arr、ピボット位置+1、高);
                }

しかし、サブ配列をどのように分割するのでしょうか?

配列の最後の要素がピボットであると仮定して、2 つのポインターを使用して配列全体を走査します。左のポインタが指す要素はピボットより小さく、右のポインタが指す要素はピボットより大きくなければなりません。そうでない場合は、配列内の特定の位置に対応するために、左と右のポインタの要素が入れ替わり、左側の要素が小さくなり、右側の要素が大きくなります。次に、この位置にピボットを挿入します。

パブリック静的intパーティション(int[] arr、int low、int high) {
                    int pivot = arr [高];
                    int左=低、右=高-1;
                    while(左<  右） {
                       while(arr[left] < pivot ) {
                            左++;
                       }
                       (arr[右] >ピボット) {
                            右 - ;
                       }
                       if(左> = 右) {
                            壊す;
                       }
                       int temp = arr [左];
                       arr[左] = arr[右];
                       arr[右] = temp;
                    }
                    int temp = arr [左];
                    arr[左] = arr[高];
                    arr[高温] = 温度;
                    左に戻る;
                }

パフォーマンス分析:

時間の計算量:

• 最良のケース: O(nlogn) — まず、配列を 2 つのサブ配列に再帰的に分割します。時間の計算量は O(logn) です。各関数呼び出しは、時間計算量が O(n) のパーティション関数を呼び出すため、合計時間計算量は O(nlogn) になります。
• 最悪の場合: O(n²) — 配列が降順でソートされている場合、または配列内のすべての要素が同一である場合、サブ配列のバランスが非常に悪いため、時間の計算量は O(n²) に跳ね上がります。

空間計算量: O(n)。

クイックソート関数は再帰的に呼び出されるため、これらの関数呼び出しを格納するために内部スタックが使用されます。スタックには最大で n 回の呼び出しがあるため、空間計算量は O(n) です。

マージソート

マージソートは、クイックソートと同様に、分割統治の概念を使用します。マージソートの主な作業はサブ配列をマージすることですが、クイックソートの主な作業は配列をパーティション分割することです。そのため、クイックソートはパーティションソートとも呼ばれます。

次の関数は、各サブ配列に要素が 1 つだけになるまで、配列を 2 つのサブ配列に再帰的に分割します。

パブリックvoidマージ(int arr[], int l, int m, int r) {
             整数n1 = m -l+1;
             int n2 = r -m;
             int[] L =新しいint[n1];
             int[] R =新しいint[n2];
             for(int i = 0 ; i <   n1 ; i++) {
                 L[i] = arr[l+i];
             }
             for(int i = 0 ; i <   n2 ; i++) {
                 R[i] = arr[m+1+i];
             }
             int i = 0 、 j = 0 、 k = l ;
             一方で(i <   n1 && j <   n2 ) {
                 L[i] < =R[j]の場合{
                     arr[k++] =L[i++];
                 }
                 それ以外 {
                     arr[k++] =R[j++];
                 }
             }
             一方で(i <   n1 ) {
                 arr[k++] =L[i++];
             }
             一方で(j <   n2 ) {
                 arr[k++] =R[j++];
             }

これらのサブ配列を 2 つの新しい配列に格納した後、順序に従って結合され、入力配列に格納されます。これらのサブ配列がすべて結合された後、入力配列がソートされます。

パブリックvoidマージ(int arr[], int l, int m, int r) {
             整数n1 = m -l+1;
             int n2 = r -m;
             int[] L =新しいint[n1];
             int[] R =新しいint[n2];
             for(int i = 0 ; i <   n1 ; i++) {
                 L[i] = arr[l+i];
             }
             for(int i = 0 ; i <   n2 ; i++) {
                 R[i] = arr[m+1+i];
             }
             int i = 0 、 j = 0 、 k = l ;
             一方で(i <   n1 && j <   n2 ) {
                 L[i] < =R[j]の場合{
                     arr[k++] =L[i++];
                 }
                 それ以外 {
                     arr[k++] =R[j++];
                 }
             }
             一方で(i <   n1 ) {
                 arr[k++] =L[i++];
             }
             一方で(j <   n2 ) {
                 arr[k++] =R[j++];
             }
         }

パフォーマンス分析:

時間の計算量:

• 最良のケース: O(nlogn) — まず、配列を 2 つのサブ配列に再帰的に分割します。時間の計算量は O(logn) です。各関数呼び出しは、時間計算量が O(n) のパーティション関数を呼び出すため、合計時間計算量は O(nlogn) になります。
• 最悪の場合: O(nlogn) — 最悪の場合の時間計算量は最良の場合と同じです。

空間計算量: O(n)

MergeSort 関数は再帰的に呼び出されるため、これらの関数呼び出しを格納するために内部スタックが使用されます。スタックには最大で n 回の呼び出しがあるため、空間計算量は O(n) です。

画像ソース: unsplash

上記のアルゴリズムは、要素が互いに比較された後にソートされるため、比較ベースのソート アルゴリズムです。ただし、カウントソート、基数ソート、バケットソートなど、比較をベースとしないソートアルゴリズムも存在します。これらは、時間の計算量が O(n) であるため、線形ソートアルゴリズムとも呼ばれます。

各アルゴリズムにはそれぞれ長所と短所があり、どのアルゴリズムを使用するかは優先順位によって異なります。効率が問題にならない場合は、簡単に実装できるバブルソートを使用できます。または、配列がほぼソートされている場合は挿入ソートを使用します。この場合、挿入ソートの時間計算量は線形であるためです。