世界で最も美しいソートアルゴリズム！

[[248668]]

早速、世界で最も「美しい」ソートアルゴリズムについてお話ししましょう。

 void stooge_sort(int arr[], int i, int j){
         arr[i] > arr[j] の場合、arr[i] と arr[j] を入れ替えます。
         (i+1 > =j) の場合、戻ります。 
  
         整数k = (j-i+1)/3;
         stooge_sort(arr, i, jk);
         stooge_sort(arr, i+k, j);
         stooge_sort(arr, i, jk);
 }

「アルゴリズム入門」の演習にある「完全ソート」は、ハワード教授やファイン教授を含む数人の教授によって提案されました。コードの実装がエレガントで、すっきりしていて、美しいことから「完全ソート」と呼ばれています。

コードは分かりにくいので、アイデアを段階的に説明します。

まず、ソートのために渡されるパラメータは、ソートする配列arr[i, j]です。

ステップ 1: 位置 i と j の要素を比較し、ソート規則に従ってそれらを置き換えるかどうかを決定します。

ナレーション: Ben Lizi、ソートのルールは小さいものから大きいものへの順だと仮定します。

順列が完了したら、ソートが完了したかどうかを判断します。i と j が隣接している場合、ソートは完了しています。

ステップ2: arr[i, j]を3つの等しい部分に分割します。

ナレーション: 要素の総数は j-i+1 です。

ステップ 3: arr の最初の 2/3 に再帰的に戻ります。

ステップ 4: arr の 2 番目の 2/3 に再帰的に戻ります。

ステップ 5: arr の最初の 2/3 に再帰的に戻ります。

並べ替えが完了しました。

すごいじゃないですか！！！

もう一度見てください、感動しましたか？

 void stooge_sort(int arr[], int i, int j){
         if (arr[i] > arr[j]) swap(arr[i], arr[j]); // 比较
         if (i+1 > =j) return; // 終了しましたか? 
  
         int k =(j-i+1)/3; // 3つの等しい部分に分割する
         stooge_sort(arr, i, jk); // 最初の 2/3 の半分の領域
         stooge_sort(arr, i+k, j); // 最後の2/3
         stooge_sort(arr, i, jk); // 最初の 2/3 の半分の領域
}

コードの見た目は良いですが、完全なソートは非常に遅いアルゴリズムなので役に立ちません。

コードから簡単にわかります:

• 要素が 1 つしかない場合、完全なソートにかかる時間も 1 です。
• n 個の要素がある場合、完全なソートは定数と 3 回の再帰によって計算され、各再帰のデータ量は (2/3)*n になります。

つまり、その時間計算量再帰式は次のようになります。

• T(1) = 1;
• T(n) = 3T(2/3n) + 1;

「すべての時間計算量の計算を解く」の再帰計算方法を使用すると、最終的に、完全ソートの時間計算量は O(n^2.7) であり、これは O(n^2) ソートよりも遅いことがわかります。

完全なソートの証明はこの記事では展開されていません。コードからは、スワップと 3 回の再帰を通じて、ソートが完了するまで、小さな要素が先頭に移動し、大きな要素が後ろに移動する傾向があることが直感的にわかります。

ナレーション: クイック ソートのプロセスは、パーティション + 2 回の再帰であり、ソートが完了するまで、小さい要素が先頭に移動し、大きい要素が最後尾に移動します。

皆さんがこの瞬間から何かを得られることを願っています。

[この記事は51CTOコラムニスト「58 Shen Jian」によるオリジナル記事です。転載については原作者までお問い合わせください。]

この著者の他の記事を読むにはここをクリックしてください