← ソート一覧にもどる

クイックソート

pivot を基準に小さい値と大きい値に分割し、再帰的に整列する分割統治法。

0 / 0
通常 比較中 交換中 確定 pivot 作業用

疑似コード

  1. quick_sort(left, right)
  2. if left >= right: return
  3. pivot = a[(left+right)/2]
  4. i = left; j = right
  5. while i <= j
  6. while a[i] < pivot: i++
  7. while a[j] > pivot: j--
  8. if i <= j
  9. swap(a[i], a[j]); i++; j--
  10. quick_sort(left, j)
  11. quick_sort(i, right)

メトリクス

配列数 n
-
比較回数
0
交換回数
0
代入回数
0
現在ステップ
0
理論計算量
O(n log n)
安定性
非安定
追加メモリ
O(log n)

クイックソートの得意・苦手

👍 得意

ランダムな配列。平均的に非常に高速。

👎 苦手

pivot の選び方が悪い場合。分割が偏ると O(n^2) に近づく。

計算量（O記法）のやさしい説明

  • n はデータの数です。
  • O(n) は、データが10倍になると処理もだいたい10倍です。
  • O(n²) は、データが10倍になると処理がだいたい100倍です。
  • O(n log n) は、O(n²) よりかなり増え方がゆるやかです。
  • O(n+k) は、データ数 n と値の範囲 k の合計。k が小さいほど速いです。
nO(n)O(n log n)O(n²)
10約10約33約100
100約100約664約10,000
1,000約1,000約9,966約1,000,000

基本情報での見分け方

▶ クイックソート：問題文に「pivot」「基準値」「左右に分割」とあればクイックソート。

問題文のキーワードソート
隣接する要素を比較して交換バブルソート
未整列部分から最小値を選ぶ選択ソート
整列済み部分の正しい位置へ挿入挿入ソート
pivot、基準値、左右に分割クイックソート
分割して併合（マージ）マージソート
出現回数、count配列計数ソート