QuickSort アルゴリズムを理解する: 分割して征服する

コンピューター サイエンスの世界では、QuickSort は最も効率的で広く使用されている並べ替えアルゴリズムの 1 つとして際立っています。大規模なデータセットのソートにおける驚くべき速度は、その「分割統治」戦略によるものです。 QuickSort がどのように機能するかを見てみましょう!

クイックソートとは何ですか?

QuickSort は、「分割統治」手法を採用した並べ替えアルゴリズムです。ピボットと呼ばれる要素を選択し、リストを 2 つの部分配列に分割します。1 つはピボットよりも小さい要素を含み、もう 1 つはピボットよりも大きい要素を含みます。このプロセスは、リストが完全にソートされるまで、これらの部分配列に対して再帰的に繰り返されます。

ピボットの選択は異なる場合があります。簡単な方法は、リストの最初の要素を選択することです。 ただし、シナリオによっては、他の戦略の方が効果的である場合もあります。

クイックソートの手順

1.再帰停止基準

リストの要素が 0 または 1 の場合、リストはすでにソートされており、アルゴリズムは終了します。

// Verifica se a lista tem 0 ou 1 elemento (já ordenada)
if (integerList.isEmpty() || integerList.size() == 1) {
    return integerList;
}

2.リストのパーティショニング:

次のステップでは、ピボットを選択し、リストを 2 つの部分配列に分割します。1 つは小さい要素を含み、もう 1 つはピボットより大きい要素を含みます。 これを行う方法の例を参照してください:

int pivo = integerList.get(0); // Escolhendo o primeiro elemento como pivô
List<Integer> menores = new ArrayList<>();
List<Integer> maiores = new ArrayList<>();
for (int i = 1; i < integerList.size(); i++) {
   if (integerList.get(i) < pivo) {
      menores.add(integerList.get(i));
   } else {
      maiores.add(integerList.get(i));
   }
}

注: 比較は i=1 から開始され、ピボットがマイナーの部分配列に含まれないことに注意してください。

3.再帰:

再帰が登場します!このアルゴリズムは、それ自体を最小サブ配列と最大サブ配列と呼び、ソートが完了するまでこのプロセスを繰り返します。結果の組み合わせを以下に示します。

List<Integer> sorted = new ArrayList<>(quickSort(menores));
sorted.add(pivo);
sorted.addAll(quickSort(maiores));
return sorted;

アルゴリズムの複雑さ

QuickSort の時間計算量は漸近 O(n log n) であり、特に計算量が O(n²) のバブル ソートなどのアルゴリズムと比較して高い効率を示します。

注: この説明は、Aditya Bhargava の書籍「Understanding Algorithms」の第 4 章に基づいて翻案したものです。 ここでは取り上げていないニュアンスがある可能性があることに注意してください。より詳細な調査のために追加の情報源を参照することをお勧めします。

結論

QuickSort は、再帰を使用してリストを効率的に並べ替える堅牢なアルゴリズムです。その主な特性は、他の並べ替えアルゴリズムと比較して、特に長いリストでの実行速度です。より完全に理解するには、「Understanding Algorithms」という書籍を読むことをお勧めします。

プロジェクトで QuickSort を使用したことがありますか?コメントであなたの経験を共有してください!

以上がQuickSort アルゴリズムを理解する: 分割して征服するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。