EN
JP
KRクイックソートとは？JavaScriptで高速ソートアルゴリズムを実装する方法を解説
クイックソートは、実用的な高速ソートアルゴリズムとしてよく知られている手法です。配列の中から基準となる値を選び、その値より小さい要素と大きい要素に分け、それぞれを再帰的にソートすることで全体を並び替えます。平均的な時間計算量はO(n log n)であり、データが適切に分割される場合には非常に効率よく動作します。バブルソート、選択ソート、挿入ソートのような基本ソートと比べると考え方は少し発展的ですが、分割統治法や再帰の理解を深めるうえで非常に重要なアルゴリズムです。
一方で、クイックソートには注意点もあります。基準値であるピボットの選び方が悪いと、配列が極端に偏って分割され、最悪ケースではO(n^2)になる可能性があります。そのため、クイックソートを学ぶときは、単にコードを暗記するのではなく、ピボットとは何か、どのように左右の配列へ分けるのか、なぜ再帰で処理できるのか、どのようなデータで遅くなりやすいのかを理解することが大切です。本記事では、クイックソートの基本的な仕組み、JavaScriptでの実装方法、ピボット選択、分割処理、計算量、マージソートとの違い、学習時のポイントまで分かりやすく解説します。
1. クイックソートとは？
クイックソートとは、配列からピボットと呼ばれる基準値を選び、そのピボットより小さい要素と大きい要素に分割して並び替えるソートアルゴリズムです。たとえば、ある値を基準にして、基準より小さい値を左側、基準より大きい値を右側に集めます。その後、左側の配列と右側の配列に対して同じ処理を再帰的に行います。最終的に、左側のソート済み配列、ピボット、右側のソート済み配列を結合することで、全体が整列された配列になります。
クイックソートも、マージソートと同じく分割統治法の考え方を使います。ただし、マージソートが配列を単純に中央で分割するのに対し、クイックソートはピボットを基準に値の大小で分割する点が異なります。この違いにより、クイックソートは平均的に高速に動作しやすい一方で、ピボットの選び方によって性能が大きく変わります。JavaScriptでクイックソートを実装すると、配列の分割、再帰、比較条件、結合処理をまとめて学ぶことができます。
1.1 ピボットとは？
ピボットとは、配列を分割するための基準値です。たとえば、配列[5, 3, 8, 1]でピボットを5にした場合、5より小さい値は[3, 1]、5より大きい値は[8]に分けられます。その後、左側の[3, 1]をさらにクイックソートで並び替え、右側の[8]は1要素なのでそのまま扱います。最後に、左側のソート結果、ピボット、右側のソート結果を結合すれば、[1, 3, 5, 8]のような整列済み配列になります。
ピボットの選び方は、クイックソートの性能に大きく影響します。毎回ピボットによって配列がほぼ半分ずつに分かれれば、効率よく処理できます。しかし、ピボットが常に最小値や最大値になってしまうと、片方の配列にほとんどの要素が残り、分割の効果が弱くなります。学習用の実装では先頭や末尾の要素をピボットにしても構いませんが、性能を意識する場合は、中央の値やランダムな値を使うなど、分割が偏りにくい工夫を考える必要があります。
1.2 クイックソートの特徴
クイックソートの特徴は、平均的に高速で、比較的短いコードでも実装しやすいことです。平均時間計算量はO(n log n)であり、データがバランスよく分割される場合には、大きな配列でも効率よく並び替えられます。基本ソートのようにすべての要素を何度も単純に比較するのではなく、ピボットを基準にして問題を小さく分けていくため、処理の効率が高くなります。このため、クイックソートは高速ソートの代表例として多くの教材で扱われています。
ただし、クイックソートは常に安定した性能を保証するわけではありません。ピボットの選び方が悪いと、最悪ケースでO(n^2)になる可能性があります。また、基本的なクイックソートは安定ソートではありません。安定ソートとは、同じ値を持つ要素の元の順序を維持するソートのことです。数値配列だけなら気にならないこともありますが、オブジェクト配列で同じスコアや同じ日付を持つ要素を扱う場合には、安定性が重要になることがあります。
1.3 マージソートとの違い
マージソートとクイックソートは、どちらも分割統治法を使う高速ソートアルゴリズムです。しかし、分割の仕方が異なります。マージソートは配列を中央で単純に半分へ分け、分割された配列をそれぞれソートしたあと、整列済み配列としてマージします。一方、クイックソートはピボットを選び、その値より小さい要素と大きい要素に分けます。つまり、マージソートは位置で分け、クイックソートは値の大小で分けると考えると分かりやすいです。
性能面でも違いがあります。マージソートは最悪ケースでもO(n log n)で動作し、安定ソートとして実装しやすい一方で、追加配列を使うためメモリ使用量が増えやすいです。クイックソートは平均的には非常に高速ですが、ピボット選択が悪いと最悪ケースでO(n^2)になります。また、インプレース実装を工夫すればメモリ使用量を抑えられますが、コードは複雑になります。両者の違いを比較すると、高速ソートにも複数の設計思想があることを理解できます。
2. クイックソートの動作手順
クイックソートの処理は、大きく分けて、ピボットを選ぶ、ピボットより小さい要素と大きい要素に分ける、左右の配列を再帰的にソートする、最後に結合する、という流れです。処理の考え方自体は比較的シンプルですが、再帰によって同じ操作が何度も繰り返されるため、最初は少し複雑に感じるかもしれません。まずは小さな配列で、どの値がピボットになり、どの値が左側と右側に入るのかを確認すると理解しやすくなります。
たとえば、[5, 3, 8, 1]で5をピボットにすると、5より小さい値は[3, 1]、5より大きい値は[8]になります。次に、左側の[3, 1]に対して同じ処理を行います。3をピボットにすれば、3より小さい値は[1]、大きい値は空になります。これらを結合すると[1, 3]になり、さらに最初のピボット5と右側の[8]を結合することで、[1, 3, 5, 8]になります。このように、クイックソートは小さな分割と結合を繰り返して全体を整列させます。
2.1 ピボットを選択する
クイックソートでは、最初にピボットを選択します。最も簡単な実装では、配列の先頭要素や末尾要素をピボットにします。たとえば、numbers[0]をピボットにする方法はコードが短く、学習用として分かりやすいです。しかし、すでに整列済みの配列や逆順の配列に対して先頭や末尾をピボットにすると、分割が極端に偏る可能性があります。その場合、毎回片方の配列にほとんどの要素が残り、処理効率が悪化します。
性能を意識する場合は、中央の値をピボットにしたり、ランダムに選んだ値をピボットにしたりする方法があります。また、先頭・中央・末尾の3つから中央値を選ぶ方法もあります。学習段階では、まず先頭要素をピボットにする単純な実装で仕組みを理解し、その後でピボット選択を変えて動きの違いを確認するとよいでしょう。ピボット選択は、クイックソートの性能を左右する重要なポイントです。
2.2 左右の配列に分割する
ピボットを選んだら、配列の残りの要素をピボットより小さい要素と大きい要素に分けます。昇順に並べる場合、ピボットより小さい値は左側の配列に入れ、ピボットより大きい値は右側の配列に入れます。基本的な実装では、ピボットと等しい値を右側に入れることもありますが、重複値が多い場合は、等しい値だけを別の配列にまとめる3分割方式を使うと分かりやすくなります。
この分割処理は、クイックソートの中心です。分割がバランスよく行われれば、左右の配列のサイズが近くなり、効率的に処理できます。一方で、分割が偏ると、再帰の深さが増えて処理が重くなります。JavaScriptで学習用に実装する場合は、left、right、必要に応じてequalという配列を用意し、for文で要素を振り分けると理解しやすいです。分割の結果を確認しながら学ぶことで、クイックソートの動きがつかみやすくなります。
2.3 再帰的にソートする
左右の配列に分割したら、それぞれに対して同じクイックソート処理を再帰的に行います。左側の配列も、またピボットを選び、小さい要素と大きい要素に分けます。右側の配列も同様です。この処理を繰り返していくと、最終的には配列の長さが1以下になります。1要素の配列はすでに整列済みであり、空配列も並び替える必要がありません。そのため、配列の長さが1以下になったらそのまま返すことが再帰の終了条件になります。
再帰処理を理解するには、関数が自分自身を呼び出していることだけを見るのではなく、「問題を小さくしている」と考えると分かりやすいです。クイックソートでは、元の配列をピボットで左右に分けることで、より小さな配列のソート問題に変えています。その小さな問題を解いた結果を結合することで、元の大きな問題も解決できます。再帰の終了条件と、分割によって問題が小さくなっていることを確認するのが重要です。
3. JavaScriptでクイックソートを実装する
JavaScriptでクイックソートを実装する場合、学習用としては新しい配列を作る非破壊的な実装が分かりやすいです。元の配列を直接変更せず、ピボットより小さい要素をleft、大きい要素をrightに振り分け、最後にquickSort(left)、ピボット、quickSort(right)を結合します。この方法はコードの流れが読みやすく、再帰や分割の考え方を理解しやすいという利点があります。
ただし、この非破壊的な実装は、配列を何度も新しく作るため、メモリ効率はあまり良くありません。実務レベルでは、配列内の要素をその場で入れ替えるインプレース実装もありますが、初心者にとってはコードが複雑になりやすいです。まずは分かりやすい非破壊的実装でクイックソートの仕組みを理解し、その後で必要に応じてインプレース実装やピボット選択の工夫を学ぶとよいでしょう。
3.1 基本実装
以下は、数値配列を昇順に並べるクイックソートの基本実装です。このコードでは、配列の長さが1以下ならそのまま返します。これが再帰の終了条件です。次に、配列の先頭要素をピボットとして選び、残りの要素を順番に確認します。ピボットより小さい値はleftへ、ピボット以上の値はrightへ追加します。最後に、左側を再帰的にソートした結果、ピボット、右側を再帰的にソートした結果を結合して返します。
この実装は、クイックソートの基本的な流れを理解するには非常に分かりやすいです。leftにはピボットより小さい値、rightにはピボット以上の値が入るため、結合後の配列はピボットを境に小さい値と大きい値が分かれます。そして、左右の配列も同じ処理でソートされるため、最終的に全体が整列されます。ただし、先頭をピボットにしているため、整列済み配列では分割が偏る可能性がある点に注意しましょう。
function quickSort(numbers) { if (numbers.length <= 1) { return numbers; } const pivot = numbers[0]; const left = []; const right = []; for (let i = 1; i < numbers.length; i++) { if (numbers[i] < pivot) { left.push(numbers[i]); } else { right.push(numbers[i]); } } return [...quickSort(left), pivot, ...quickSort(right)];}console.log(quickSort([5, 3, 8, 1])); // [1, 3, 5, 8]
3.2 中央の値をピボットにする
先頭要素をピボットにする実装は分かりやすいですが、すでに整列済みの配列や逆順の配列では分割が偏りやすいです。そこで、中央の値をピボットにする方法があります。Math.floor(numbers.length / 2)で中央のインデックスを求め、その位置の値をピボットとして使います。中央を選ぶことで、先頭や末尾を選ぶよりも偏りを避けやすくなる場合があります。ただし、常に最適な分割になるわけではありません。
中央ピボットの実装では、ピボットより小さい値をleft、大きい値をright、等しい値をequalに分けると、重複値が多い配列でも処理の意図が分かりやすくなります。equalを用意することで、ピボットと同じ値を何度も左右に振り分ける必要がなくなり、重複値をまとめて扱えます。この3分割方式は、クイックソートの発展的な考え方を学ぶうえでも役立ちます。
function quickSort(numbers) { if (numbers.length <= 1) { return numbers; } const pivotIndex = Math.floor(numbers.length / 2); const pivot = numbers[pivotIndex]; const left = []; const equal = []; const right = []; for (const number of numbers) { if (number < pivot) { left.push(number); } else if (number > pivot) { right.push(number); } else { equal.push(number); } } return [...quickSort(left), ...equal, ...quickSort(right)];}
3.3 降順にする方法
クイックソートで降順に並べたい場合は、比較条件や結合順を変えます。昇順では、ピボットより小さい値を左側、大きい値を右側に置きます。降順では、大きい値を前に置きたいので、ピボットより大きい値を左側、小さい値を右側に置きます。つまり、分割条件を逆にするだけで、同じクイックソートの構造を使って降順ソートを実装できます。
降順ソートは、スコアの高い順、売上金額の大きい順、人気数の多い順、ランキング表示などでよく使われます。クイックソートの降順実装を試すことで、比較条件がアルゴリズム全体の並び順にどのように影響するのかを理解できます。JavaScript標準のsort()でも、昇順ならa - b、降順ならb - aを使うように、ソートでは比較条件の設計が非常に重要です。
function quickSortDesc(numbers) { if (numbers.length <= 1) { return numbers; } const pivot = numbers[0]; const left = []; const right = []; for (let i = 1; i < numbers.length; i++) { if (numbers[i] > pivot) { left.push(numbers[i]); } else { right.push(numbers[i]); } } return [...quickSortDesc(left), pivot, ...quickSortDesc(right)];}
4. クイックソートの計算量
クイックソートの平均時間計算量はO(n log n)です。これは、ピボットによって配列がある程度バランスよく分割される場合、再帰の深さがlog n程度になり、各階層で要素を分割するために全体としてn程度の処理が行われるからです。分割がうまくいけば、データ量が増えても比較的効率よく並び替えられます。このため、クイックソートは高速ソートの代表的なアルゴリズムとして扱われます。
しかし、クイックソートは最悪ケースでO(n^2)になる可能性があります。これは、ピボットが毎回最小値または最大値になり、片方の配列にほとんどの要素が残ってしまう場合です。このような偏った分割が続くと、問題があまり小さくならず、基本ソートに近い重い処理になってしまいます。クイックソートを理解するうえでは、平均ケースの速さだけでなく、最悪ケースが起こる理由も押さえておくことが重要です。
4.1 平均ケース
平均ケースでは、ピボットによって配列がある程度バランスよく分割されます。たとえば、毎回おおよそ半分ずつに分けられるなら、再帰の深さはlog n程度になります。そして、それぞれの階層で全要素を一度ずつ確認して左右に分けるため、全体としてO(n log n)の処理になります。これはマージソートと同じ水準の時間計算量であり、大きなデータに対しても比較的効率よく動作しやすいです。
クイックソートが実用的な高速ソートとして知られているのは、この平均ケースでの性能が高いためです。特に、ピボット選択がうまくいき、分割が偏りにくい場合には、非常に良い性能を発揮します。ただし、JavaScriptで学習用に実装する非破壊的なクイックソートでは、新しい配列を何度も作るため、実際の実行速度やメモリ使用量は標準sort()に劣ることがあります。学習では計算量の考え方を重視し、実務では標準メソッドを基本に考えるとよいでしょう。
4.2 最悪ケース
クイックソートの最悪ケースは、ピボットが毎回最小値または最大値になってしまう場合です。たとえば、すでに昇順に整列された配列に対して、常に先頭要素をピボットにすると、ピボットより小さい要素は存在せず、右側にほとんどの要素が残ります。このような分割が繰り返されると、配列はほとんど小さくならず、再帰の深さがnに近くなります。その結果、時間計算量はO(n^2)になります。
この最悪ケースを避けるためには、ピボット選択を工夫することが重要です。中央の値を選ぶ、ランダムに選ぶ、先頭・中央・末尾の中央値を選ぶなどの方法があります。もちろん、どの方法でも完全に最悪ケースを避けられるとは限りませんが、偏った分割が続く可能性を減らせます。クイックソートを学ぶときは、同じ実装をランダムな配列、整列済み配列、逆順配列で試して、分割の偏りが性能に与える影響を確認すると理解が深まります。
4.3 空間計算量
学習用の非破壊的なクイックソートでは、leftやrightのような新しい配列を作るため、追加メモリを使います。再帰の各段階で配列を分割し、新しい配列を作成するため、実装は分かりやすい一方で、メモリ効率はあまり良くありません。小さな配列や学習用のサンプルでは問題になりにくいですが、大量データを扱う場合には注意が必要です。
一方、クイックソートはインプレースに実装することもできます。インプレース実装では、元の配列内で要素を入れ替えることで追加メモリを抑えます。ただし、コードは複雑になり、初心者には理解しにくくなる場合があります。最初は非破壊的な実装でクイックソートの流れを理解し、その後でインプレース実装を学ぶと段階的に理解しやすくなります。空間計算量を考えることは、時間計算量だけでは見えないアルゴリズムの特徴を理解するうえで重要です。
5. クイックソートを学ぶポイント
クイックソートを学ぶときは、ピボット、分割、再帰の3つを意識することが大切です。ピボットは配列を分ける基準であり、分割はピボットより小さい要素と大きい要素を整理する処理です。そして、再帰は分割された左右の配列に対して同じ処理を繰り返す仕組みです。この3つの関係が分かると、クイックソート全体の流れを理解しやすくなります。
また、マージソートとの違いを比較しながら学ぶと、分割統治法にも複数のアプローチがあることが分かります。マージソートは位置で半分に分け、最後にマージ処理で整列します。クイックソートはピボットを基準に値の大小で分け、左右を再帰的に整列します。どちらも高速ソートですが、計算量の安定性、メモリ使用量、安定ソートかどうかなどに違いがあります。比較しながら学ぶことで、ソートアルゴリズム全体への理解が深まります。
5.1 小さな配列で試す
クイックソートを初めて学ぶときは、[3, 1, 2]や[5, 3, 8, 1]のような小さな配列で試すのがおすすめです。要素数が少ない配列であれば、どの値がピボットになり、どの値が左側や右側に入るのかを簡単に確認できます。いきなり大きな配列を使うと、再帰の流れや分割の状態が追いにくくなるため、まずは短い配列で基本動作を理解しましょう。
小さな配列で試すと、クイックソートが「ピボットを中心に小さい値と大きい値を分ける」アルゴリズムであることが分かりやすくなります。紙に配列を書き、ピボットを丸で囲み、左側と右側に分ける流れを手で追うと理解が深まります。JavaScriptコードにconsole.log({ pivot, left, right })のような出力を一時的に入れて確認するのも有効です。処理の途中経過を見ることで、再帰の動きが具体的に見えるようになります。
5.2 ピボット選択を変えてみる
クイックソートを理解するには、ピボットの選び方を変えて試してみることが効果的です。先頭、末尾、中央、ランダムなど、異なる方法でピボットを選ぶと、左右の分割のされ方が変わります。特に、すでに整列済みの配列に対して先頭をピボットにした場合と、中央をピボットにした場合を比較すると、分割の偏りが分かりやすくなります。これにより、ピボット選択が性能に影響する理由を実感できます。
ピボット選択を変える実験は、アルゴリズムを暗記ではなく理解するために役立ちます。同じクイックソートでも、データの状態やピボットの選び方によって、再帰の深さや処理回数が変わります。これは、実務でアルゴリズムを選ぶときにも重要な考え方です。単に平均計算量だけを見るのではなく、入力データの性質や最悪ケースを考慮することが大切です。
5.3 実務では標準sortを使う
クイックソートは学習目的で実装する価値が高いアルゴリズムですが、実務ではJavaScript標準のArray.prototype.sort()を使うのが基本です。標準sort()はJavaScriptエンジン側で最適化されており、通常の一覧表示やデータ処理では十分な性能を発揮します。また、コードが短く、他の開発者にも意図が伝わりやすいため、保守性の面でも有利です。自作クイックソートを実務コードに入れる必要は、ほとんどありません。
ただし、クイックソートを学ぶことは、標準sort()を使ううえでも役立ちます。比較関数の重要性、データ量が増えたときの計算量、最悪ケースの考え方、再帰による問題分割などを理解できるからです。実務では標準メソッドを使い、学習ではクイックソートを実装してアルゴリズムの仕組みを理解するという使い分けが現実的です。クイックソートの知識は、性能感覚やアルゴリズム設計の基礎を身につけるために活用できます。
おわりに
クイックソートは、ピボットを基準に配列を分割し、再帰的に並び替える高速ソートアルゴリズムです。平均時間計算量はO(n log n)であり、分割がバランスよく行われる場合には効率的に動作します。ピボット、分割、再帰という3つの要素を理解すると、クイックソートの全体像がつかみやすくなります。
一方で、ピボット選択が悪いと最悪ケースでO(n^2)になる可能性があります。また、基本的な実装では安定ソートではなく、非破壊的な学習用実装では追加メモリも使います。JavaScriptでは実務で標準のsort()を使う場面が多いですが、クイックソートを学ぶことで、分割統治法、再帰、計算量、ソートアルゴリズム設計への理解を深めることができます。
