テクノロジ
クイックソートとは
読み方：クイックソート
ひとことで言うと：ピボットを基準に小さい群と大きい群へ分割し、再帰的に整列する方法。
意味をわかりやすく解説
クイックソートは、基準値（ピボット）を選び、それより小さい要素群と大きい要素群へ分割し、それぞれを再帰的に整列する分割統治型の整列法です。
平均計算量はO(n log n)ですが、毎回極端に偏った分割になると最悪O(n²)になります。ピボットの選び方が性能に影響します。
具体例
[3,7,2,5,8]で5をピボットにすると、5より小さい[3,2]と大きい[7,8]へ分け、それぞれを整列します。
似た用語との違い
覚え方
ピボットを境に小・大へ分けて再帰。
基本情報技術者試験の試験ポイント
平均O(n log n)、最悪O(n²)、ピボット選択と分割の偏りを押さえます。
CHECK QUESTION
すでに整列済みの配列で毎回端の要素をピボットにすると、クイックソートが遅くなりやすいのはなぜですか。
答えを見る
分割が1対n-1のように極端に偏り、再帰の深さが大きくなって最悪O(n²)になり得るからです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。