クイックソート・ビジュアライザー
ピボットとパーティションをハイライト表示しながらクイックソートをアニメーション表示。ステップ実行、速度調整、カスタム入力、リアルタイムのカウンター、擬似コードにも対応。ブラウザ上ですぐに動かせます。
Code examples
Ready-to-copy reference implementations. Free to use in your own projects and assignments.
使い方
- 1 Playを押すと、各パーティション処理でピボットが正しい位置に収まり、配列がその周りで分割されていく様子を確認できます。
- 2 Stepを使うと、比較を1回ずつ進めながらパーティションのポインタの動きを追えます。
- 3 Custom inputの欄に好きな数値を入力し、Applyを押してください。
- 4 ハイライトされる擬似コードと、リアルタイムで更新される比較・交換回数のカウンターを見比べてみましょう。
このツールを使う理由
- ピボットを軸にした分割が、分割統治法（divide-and-conquer）による再帰処理をどう導くかがわかります。
- クイックソートが実務上もっとも高速な比較ソートとされることが多い理由を理解できます。
- ピボットの選択が悪い場合（たとえばすでにソート済みのデータなど）に、最悪計算量O(n²)に陥る様子を数値で確認できます。
- 処理はすべてブラウザ内で完結します。登録もアップロードも不要です。
よくある質問
クイックソートとは何ですか？
クイックソートは、まずピボットを1つ選び、それより小さい要素を左側に、大きい要素を右側に配置するように配列を分割し、その後両側をそれぞれ再帰的にソートするアルゴリズムです。このツールでは、最後の要素をピボットとするLomuto方式を採用しています。
クイックソートの時間計算量はどれくらいですか？
平均的にはO(n log n)ですが、ピボットが常に最小値または最大値になってしまう最悪のケースではO(n²)まで悪化します。ピボットをランダムに選ぶ、あるいは median-of-three 方式を使うことで、実務上こうした事態を避けられます。
クイックソートは安定ソート（stable）ですか？
いいえ、安定ソートではありません。パーティション処理中の交換によって要素が配列内を大きく移動するため、同じ値を持つ要素同士の順序が入れ替わることがあります。追加メモリを使うことで安定版のクイックソートを実現する派生アルゴリズムも存在します。
クイックソートはなぜこれほど広く使われているのですか？
インプレース（追加のメモリをほとんど使わない）でソートでき、キャッシュ効率が良く定数項も小さいため、最悪ケースの計算量に制約があるにもかかわらず、実際のデータではマージソートやヒープソートより高速になることが多いからです。
クイックソート・ビジュアライザー とは？
クイックソート・ビジュアライザーは、クイックソートアルゴリズムの動きをアニメーションで再現するツールです。ピボットを1つ選び、そのピボットを軸に要素を分割してから、両側をそれぞれ再帰的にソートしていきます。このツールはLomutoパーティション方式を採用しており、クイックソートが平均でO(n log n)の計算量を持つ一方、ピボットの選び方が悪いとO(n²)まで悪化しうる理由を視覚的に理解できます。
機能
ステップごとのアニメーション
各部分配列でのピボット選択、分割、再帰の様子を確認できます。
計算量
時間計算量:平均O(n log n)、最悪O(n²)。空間計算量:平均O(log n)。in-place;安定ソートではありません(not stable)。
100%プライベート
すべてブラウザ内で完結し、データはアップロードされません。
例
Input
[5, 2, 8, 1]Output
choose pivot, partition into < and ≥, recurse → [1, 2, 5, 8] (sorted)主な用途
-
1
分割の仕組みを理解する
要素が < ピボット と ≥ ピボット にどう分割されるかを確認できます。
-
2
最悪ケースの落とし穴
ソート済みの入力に対して単純なピボット選択を行うとO(n²)まで悪化する様子を確認できます。
-
3
実用上高速である理由
ランダムまたはmedian-of-threeによるピボット選択が最悪ケースをどう回避するかを確認できます。
Zerethonのクイックソートビジュアライザーは、分割統治アルゴリズムをブラウザ上でアニメーション表示します。ピボットを選び、それを基準に要素を分割し、再帰的に処理を行います。クイックソートは平均でO(n log n)で動作しますが、最悪の場合(例えば、すでにソート済みの入力に対して単純なピボット選択を行った場合)にはO(n²)まで悪化します。平均でO(log n)のスタック空間を使用し、in-place(その場)で動作し、安定ソートではありません(not stable)。適切なピボット選択(例えば median-of-three やランダム選択)により、実用上は高速に保たれます。
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
参考文献
- MIT OCW 6.006 — アルゴリズム入門(CLRS) — MIT OpenCourseWare
- VisuAlgo — ソート — VisuAlgo (NUS)
- クイックソート(C. A. R. Hoare, 1961) — Wikipedia
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。クイックソート・ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Sorting Algorithms を学ぶ →
比較
関連ツール
バブルソート ビジュアライザー
バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。
ツールを開く挿入ソート(Insertion Sort)ビジュアライザー
挿入ソートをアニメーションで可視化。ステップ実行や速度調整、カスタム入力、比較回数・書き込み回数のリアルタイム表示、疑似コード(pseudocode)表示に対応。すべてブラウザ内で完結します。
ツールを開く選択ソート(Selection Sort)ビジュアライザー
ステップ実行、速度調整、カスタム入力、比較/交換回数のライブカウンター、擬似コードを備えたSelection Sortのアニメーション。すべてブラウザ内だけで完結します。
ツールを開くマージソート ビジュアライザー
マージソートの動きをアニメーションで再現するツールです。ステップ実行、速度調整、独自のデータ入力、比較・書き込み回数のリアルタイム表示、擬似コード表示に対応。すべてブラウザ上だけで動作します。
ツールを開くZerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。