はじめに: クイックソートは「分けて整える」アルゴリズム
前の記事では、再帰処理を見ました。再帰は、関数が自分自身を呼び出しながら、問題を小さくして解く考え方です。
今回扱うクイックソートは、この再帰と相性がよい整列アルゴリズムです。整列とは、データを小さい順、大きい順、日付順、名前順のように並べ替える処理です。
クイックソートでは、配列の中から基準となる値を1つ選びます。そして、その値より小さいものと大きいものに分けます。分けた左側と右側にも、同じ処理を繰り返します。
基本情報技術者試験では、整列アルゴリズムの手順や計算量が問われることがあります。実務でも、データ件数が増えたときの重さを見積もる力は役立ちます。
クイックソートは、基準値で配列を分けながら整列する代表的なアルゴリズムです。
ソートとは何かを確認する
ソートとは、データを決まった順序に並べ替えることです。たとえば、次の配列があるとします。
const scores = [80, 50, 90, 60];これを小さい順に並べ替えると、次のようになります。
[50, 60, 80, 90]Webアプリでも、ソートはよく登場します。商品を価格順に並べる、記事を公開日順に並べる、ユーザー一覧を名前順に並べる、といった処理です。
JavaScriptには sort() という標準メソッドがあります。普段の開発では、自分でソートアルゴリズムを書くより、標準メソッドやデータベースの並べ替え機能を使うことが多いです。
それでも、ソートの中身を学ぶ意味はあります。データ件数が増えるほど、処理時間を意識する必要が出てくるからです。
ソートは、データを決まった順序に並べ替える処理で、Webアプリでも頻繁に使われます。
クイックソートの基本: ピボットで左右に分ける
クイックソートでは、まず配列の中から基準となる値を1つ選びます。この基準値をピボットと呼びます。
たとえば、次の配列を考えます。
[5, 2, 8, 1, 3]先頭の 5 をピボットにすると、5 より小さい値は [2, 1, 3]、5 より大きい値は [8] に分けられます。
[2, 1, 3] 5 [8]この時点で、ピボットの 5 は「左側の値より大きく、右側の値より小さい」位置にあります。ただし、左側の [2, 1, 3] はまだ整列されていません。そこで、左側にも同じ処理を行います。
大きな問題を小さな問題に分けて解く考え方を分割統治と呼びます。クイックソートは、分割統治と再帰をまとめて理解しやすい題材です。
クイックソートは、ピボットを基準に配列を左右へ分け、分けた配列にも同じ処理を繰り返します。
JavaScriptでクイックソートを書いてみる
ここでは、考え方を理解しやすいように、新しい配列を作りながら整列するクイックソートを書きます。最速を目指す実装ではありませんが、ピボット、分割、再帰の流れを確認しやすい形です。
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const pivot = array[0];
const rest = array.slice(1);
const left = rest.filter((value) => value < pivot);
const right = rest.filter((value) => value >= pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
const numbers = [5, 2, 8, 1, 3];
console.log(quickSort(numbers));停止条件は、配列の長さが1以下のときです。要素が0個または1個なら、すでに整列済みと考えられます。
次に、先頭の要素をピボットとして取り出します。残りの要素を filter() で調べ、ピボットより小さい値を left、ピボット以上の値を right に分けます。
最後に、左側をクイックソートした結果、ピボット、右側をクイックソートした結果を結合します。
return [...quickSort(left), pivot, ...quickSort(right)];left と right は元の配列より小さくなるため、いつか停止条件に到達します。
クイックソートのコードでは、停止条件、ピボットの選択、左右への分割、再帰呼び出しを順番に見ると理解しやすくなります。
コードの流れを小さな配列で追う
先ほどの [5, 2, 8, 1, 3] で、処理の流れを追ってみます。
最初のピボットは 5 です。残りの要素を比べると、左側は [2, 1, 3]、右側は [8] になります。
quickSort([5, 2, 8, 1, 3])
=> quickSort([2, 1, 3]) + [5] + quickSort([8])右側の [8] は要素が1つなので、そのまま返ります。左側の [2, 1, 3] は、さらにクイックソートします。
左側では、ピボットを 2 とします。2 より小さい値は [1]、2 以上の値は [3] です。
quickSort([2, 1, 3])
=> quickSort([1]) + [2] + quickSort([3])[1] と [3] はそのまま返るため、左側の結果は [1, 2, 3] になります。最後に、左側の [1, 2, 3]、ピボットの [5]、右側の [8] を合わせると、整列済みの配列になります。
[1, 2, 3, 5, 8]小さく分けた配列の結果が戻りながら組み合わさり、最終的な整列済み配列になります。
計算量: 平均では速いが最悪の場合もある
クイックソートは、平均的には速い整列アルゴリズムとして知られています。平均的な計算量は O(n log n) です。
各段階では、要素を見ながらピボットより小さいか大きいかを分けます。この処理には、要素数に比例する時間がかかります。
一方で、ピボットによって左右がほどよく分かれれば、配列の大きさは段階ごとに小さくなります。平均的には分割の段数が log n に近くなるため、全体として O(n log n) です。
ただし、いつでも O(n log n) になるわけではありません。すでに整列済みの配列で、常に先頭をピボットにすると、片側にばかり要素が集まることがあります。
[1, 2, 3, 4, 5]この場合、ほとんど1つずつしか問題が小さくなりません。このような最悪の場合、計算量は O(n^2) になります。
今回の実装は filter() やスプレッド構文で新しい配列を作るため、メモリ効率のよい実装ではありません。実際のライブラリや処理系では、より工夫された実装が使われます。
クイックソートは平均的には O(n log n) ですが、ピボットの選び方が偏ると O(n^2) になることがあります。
試験ではどう問われるか
基本情報技術者試験でクイックソートが出る場合、細かい実装を暗記するより、処理の流れを追えることが大切です。
まずピボットを確認し、ピボットより小さい要素と大きい要素がどちらに分かれるかを見ます。そして、分けた部分に対して同じ処理が繰り返されることを追います。
再帰処理として出てくる場合は、停止条件も重要です。配列の要素数が1以下になったら、それ以上分ける必要はありません。
計算量は、平均的には O(n log n)、最悪の場合は O(n^2) です。ピボットで左右がバランスよく分かれるかどうかが処理時間に影響します。
試験では、ピボットによる分割、再帰の停止条件、平均と最悪の計算量を押さえることが大切です。
実務ではどう使われるか
実務で、自分でクイックソートを一から書く場面は多くありません。JavaScriptなら配列の sort() を使い、データベースなら ORDER BY を使うことが一般的です。
たとえば、記事一覧を公開日順に並べるなら、ブラウザ側で大量のデータを受け取ってから並べ替えるより、データベース側で必要な順序に並べて取得するほうが自然です。
それでも、クイックソートを学ぶ意味はあります。計算量を知っていると、「この並べ替えはブラウザで行ってよいのか」「サーバー側やデータベース側に任せるべきか」を考えやすくなります。
実務では標準機能を使うことが多い一方、ソートの計算量を知ると処理をどこで行うべきか判断しやすくなります。
まとめ: クイックソートは分割統治を理解する入口
クイックソートは、配列からピボットを選び、ピボットより小さい値と大きい値に分けながら整列するアルゴリズムです。分けた配列に対して同じ処理を繰り返すため、再帰処理と相性がよい題材です。
平均的な計算量は O(n log n) ですが、ピボットの選び方によっては O(n^2) になることがあります。この「速い場合もあるが、条件によって遅くなる」という感覚は、アルゴリズムを学ぶうえで大切です。
実務では、標準メソッドやデータベースの並べ替え機能を使うことが多いです。それでも、クイックソートを通じて分割統治、再帰、計算量をまとめて理解しておくと、データ処理の重さを見積もる力につながります。
クイックソートを理解すると、再帰、配列、計算量、分割統治の考え方をつなげて理解しやすくなります。
コメント