前書き
配列の並べ替えは、コンピュータサイエンス分野の古典的なコース「アルゴリズムとデータ構造」で研究された最初の深刻な問題の1つです。この点で、ソートを書くタスクとそれに対応する質問は、インターンまたはジュニア開発者のポジションのインタビューでしばしば遭遇します。
問題の定式化
伝統的に、そのステートメントで問題の解決策の提示を開始する価値があります。通常、並べ替えタスクでは、整数の配列を昇順で並べ替えます。しかし実際には、これはやや単純化しすぎています。このセクションで説明するアルゴリズムを使用して、順序関係が確立されているオブジェクトの配列を順序付けることができます（つまり、2つの要素について、最初の要素が2番目の要素よりも大きい、2番目の要素が最初の要素よりも大きい、または等しい）。昇順と降順の両方で並べ替えることができます。標準の簡略化を使用します。
クイックソート
前回は、もう少し複雑なソート、つまり挿入ソートについて説明しました。今日は、はるかに複雑なアルゴリズムであるクイックソート（ホアソートとも呼ばれます）に焦点を当てます。
アルゴリズムの説明
クイックソートアルゴリズムは再帰的であるため、簡単にするために、手順では、lを含むからrを含まないまでの配列セグメントの境界を入力として受け取ります。配列全体をソートするには、パラメーターlとして0を渡し、rとしてnを渡す必要があることは明らかです。ここで、伝統的に、nは配列の長さを示します。
クイックソートアルゴリズムは、パーティション手順に基づいています。パーティションは、配列の一部の要素を選択し、配列が2つの部分に分割されるように配列の要素を再配置します。左側にはこの要素よりも小さい要素が含まれ、右側にはこの要素以上の要素が含まれます。この分離要素はピボットと呼ばれます。
パーティションの実装：
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
この場合のピボットはランダムに選択されます。このアルゴリズムはランダム化と呼ばれます。実際、ピボットはさまざまな方法で選択できます。ランダムな要素を取得するか、セクションの最初/最後の要素を取得するか、「スマート」な方法で選択します。ピボットの選択は、ソートアルゴリズムの最終的な複雑さにとって非常に重要ですが、それについては後で詳しく説明します。分割手順の複雑さはO（n）です。ここで、n = r --lはセクションの長さです。
ここで、パーティションを使用して並べ替えを実装します。パーティションの
実装：
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
極端な場合-1つの要素の配列には順序付けられるという特性があります。配列が長い場合は、パーティションを使用して、配列の2つの半分でプロシージャを再帰的に呼び出します。
配列12 2の例で書かれた並べ替えを実行すると、それが決して終了しないことに気付くでしょう。なぜそれが起こったのですか？
パーティションを作成するとき、私たちは仮定をしました-配列のすべての要素は一意でなければなりません。それ以外の場合、mの戻り値はlになり、sort（l、m）はsort（l、l）およびsort（l、m）を呼び出すため、再帰は終了しません。この問題を解決するには、配列を2つの部分（<ピボットと> =ピボット）ではなく3つの部分（<ピボット、=ピボット、>ピボット）に分割し、1番目と3番目の部分に対して再帰ソートを呼び出す必要があります。
分析
このアルゴリズムを分析することを提案します。
アルゴリズムの時間の複雑さは、次の式で表されます。T（n）= n + T（a * n）+ T（（1-a）* n）。したがって、n個の要素の配列の並べ替えを呼び出すと、ピボットによって要素が分数に分割されているため、パーティションを実行し、パラメーターa * nおよび（1-a）* nを使用してそれ自体を2回実行するのに約n回の操作が必要です。
最良の場合、a = 1/2、つまり、ピボットは領域を毎回2つの等しい部分に分割します。この場合：T（n）= n + 2 * T（n / 2）= n + 2 *（n / 2 + 2 * T（n / 4））= n + n + 4 * T（n / 4 ）= n + n + 4 *（n / 4 + 2 * T（n / 8））= n + n + n + 8 * T（n / 8）=…。引数が1に減少するまで用語が表示されるため、合計はlog（n）用語になります。その結果、T（n）= O（n * log（n））になります。
最悪の場合、a = 1 / nです。つまり、ピボットは1つの要素だけを切り取ります。配列の最初の部分には1つの要素が含まれ、2番目の部分にはn-1が含まれます。つまり、T（n）= n + T（1）+ T（n-1）= n + O（1）+ T（n-1） = n + O（1）+（n-1 + O（1）+ T（n-2））= O（n ^ 2）。四角は、式を走り書きする過程で現れる算術進行の合計の式に現れるという事実のために現れます。
平均して、理想的には、さまざまなオプションの数学的期待を考慮する必要があります。ピボットがアレイを1：9の比率で分割する場合、結果の漸近は依然としてO（n * log（n））であることを示すことができます。
O記号の下に隠されている定数が実際には非常に小さいことが判明し、実際にアルゴリズムが広く使用されるようになったため、並べ替えは高速と呼ばれます。
続きを読む
