比較
交換
分割

  • 分割中の部分
  • ピボット
  • 比較中
  • 交換済み
  • 確定

クイックソートの詳細

クイックソート

クイックソートはピボットを選び、それより小さい値をすべて前に、それ以外の値を後ろに移してから、両側を同じ方法で並べ替えます。分割のたびに、ピボットは最終位置に収まります。ピボットの選び方を選び、好きな速度で再生するか比較を1回ずつ進めて、整列済みのリストで悪いピボットを選ぶとクイックソートが遅くなる理由を確かめましょう。 「再生」で並べ替えを見るか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。タイルには比較回数、交換回数、分割回数が表示されます。棒の数や初期の並びを選ぶか、数値を自分で入力できます。ピボットの選び方も選べます。ボードを選択中は、矢印キーで1ステップ移動、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 棒の数と初期の並びを選びます:ランダム、ほぼ整列済み、逆順、重複が多い。数値を自分で入力することもできます。
  2. 「再生」を押すか、「ステップ」と「戻る」で比較を1回ずつ進めます。ステップスライダーをドラッグすると、並べ替えの好きな位置に移動できます。
  3. ピボットの選び方を選びます:最後の値、中央の値、ランダムな値、3値の中央値。整列済みのリストでそれぞれ試してみましょう。

クイックソートのしくみ

並べ替える部分から値を1つ選んでピボットとし、末尾に移します。残りの値を左から右へ調べ、ピボットより小さいものは先頭から伸びていく左側の部分に交換します。次に、ピボットを左側の部分の直後に交換します。その前の値はすべてピボットより小さく、後ろには小さい値がないので、ピボットは最終位置にあります。前の部分と後ろの部分も同じ方法で並べ替え、すべての部分が値1つになるまで続けます。

ピボットが重要な理由

ピボットが真ん中近くに来ると、分割のたびに問題が半分になり、比較回数は n log n のペースで増えます。ランダムな40個の値では約190回です。ピボットが最小値や最大値だと、片側が空になり、もう片側に残りすべてが入ります。最後の値をピボットにすると、整列済みや逆順のリストでは毎回これが起こり、比較は n(n − 1)/2 回、40個なら780回になります。ランダムなピボットや、最初・中央・最後の値の中央値を使えば、実際にはこれを避けられます。

よくある質問

クイックソートはどう動きますか?

ピボットを選び、小さい値がピボットの前、残りが後ろに来るようにリストを分割してから、両側をクイックソートで並べ替えます。分割のたびに、ピボットは最終位置に確定します。

整列済みのリストでクイックソートが遅いのはなぜですか?

最初か最後の値をピボットにすると、整列済みのリストでは必ず最小値か最大値がピボットになります。すると分割の片側が空になり、1回の分割で値が1つしか減らないため、比較は n(n − 1)/2 回になります。ランダムなピボットや3値の中央値を使えば、実際にはこれを解消できます。

クイックソートはマージソートより速いですか?

実際には多くの場合そうです。その場で並べ替え、バッファが不要で、内側のループもとても単純です。平均の比較回数はマージソートよりやや多く、最悪の場合は n² ですが、マージソートは常に n log n です。introsort などのライブラリのソートはクイックソートで始め、分割が偏りすぎるとヒープソートに切り替えます。

クイックソートは安定ですか?

いいえ。分割では値を遠くまで交換するので、等しい値の順序が変わることがあります。

入力した数値はどこかに送信されますか?

いいえ。並べ替えはブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ