はじめに
こんにちは、インプルの山形です。今回も前回の投稿に引き続きJavaScriptでアルゴリズムを実装していきたいと思います。
前回は選択ソートを実装してみました。こちらの記事で内容を見れますので、興味のある方はこちらも参照してみてください。(参照URL: https://ramble.impl.co.jp/4027/）
今回はクイックソートを実装します！まずはクイックソートとは何か、ここから確認していきます！
クイックソートとは
以下IT用語辞典 e-wordより引用
クイックソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムで、最も高速な手法の一つ。1960年に英コンピュータ科学者アントニー・ホーア（Charles Antony Richard Hoare）氏が考案した
https://e-words.jp/w/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88.html
クイックソートは整列アルゴリズムの一つで、最も高速な手法の一つということがわかりました。具体的な手順を下記の引用から深ぼってみてみましょう。
以下、Wikipediaより引用。
クイックソートは以下の手順で行われる。
1. ピボットの選択：適当な値（ピボット（英語版）という）を境界値として選択する
2. 配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
3. 再帰：分割された区間に対し、再びピボットの選択と分割を行う
4. ソート終了：分割区間が整列済みなら再帰を打ち切る
https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
こちらを具体的な例を交えて、解説していきます。例えば、[3,5,2,1,4]という配列をクイックソートを使用して、整列させることを考えます。
手順1
まずこの配列からソートの基準となる適当な値を選択します。今回は「3」を選択してみましょう。これをピボットと言います。
手順2
次に手順1で選択したピボット基準に「5,2,1,4」を分割してみます。ピボットは今回3です。3未満のグループとそれ以外のグループに分割します。3未満のグループ「2,1」、それ以外のグループ「5,4」に分けることができそうです。そしてピボット未満のグループを先頭に集めます。この時点で配列の並びは[2,1,3,5,4]となりそうです。
手順3
分割されたグループで再帰的に手順1~手順3を繰り返します。今回で言うと、一度目のソートで分割できた、「2,1」のグループと、「5,4」のグループで手順1~3を繰り返すと言うことです
手順4
分割区間が整列済みなら、再帰をストップします。「2,1」のグループを例にとると、「２」をピボットとして選択するなら、「1,2」の整列ができた時点で終了ということになります。
言葉だけの説明だとイメージしづらく難しく見えます。今度はこれをJavaScriptの実装を通してみてみましょう。
クイックソートをJavaScriptで実装する
const quickSort = (array) => {
if(array.length <= 1){
return array;
}
const pivot = array[0]; // - ①
const lessThenPivot = quickSort(array.filter(value => pivot > value)); // - ②-a
const moreThenPivot = quickSort(array.filter(value => pivot < value)); // - ②-b
return [...lessThenPivot, pivot, ...moreThenPivot];
}
const testCase = [9,65,32,24,6,1];
const result = quickSort(testCase);
console.log(result); // [ 1, 6, 9, 24, 32, 65 ]
今回は配列の添字「０」つまり「９」をピボットとしました。そうすると、filterの処理(②）で「6,1」(②-a)、「65,32,24」(②-b)というグループ分けができます。
②-a例にとると、こちらではpivotが[ 6 ] lessTenPivotが [ 1 ] moreThenPivot[ ] (空)になります。lessThenPivotとmoreThenPivotは配列の要素数が1以下になるので、If(array.length <=1)の処理の中に入り、上記のような結果が返ってきます。そして最後のreturnで②-aの処理が終了します。この時点で、[ 1, 6 ]の並びになります。
同様に②-bでも再帰関数が実行され、pivotが[ 65 ] lessThenPivotが [ 32, 24 ] moreThenPivotが[ ](空)となり、この場合、lessThenPivotの要素数が1以上なのでもう一度再起の処理が走ります。そして[24, 32] の結果を返し処理が終了します。これで、②-bが結果として、 [24,32,65]を返却することになります。
全ての再起が終了した時点で、pivot [ 9 ], lessThenPivot [ 1, 6 ], moreThenPivot [ 24, 32, 65 ]となり、結果として[ 1, 6, 9, 24, 32, 65 ]が呼び出し元に返却されることになります。
スプレット演算子で配列の中身を展開して、呼び出し元に返却するので結果的にfilterを実行した後でも一重の配列になるといいう仕組みです。JavaScriptではconcat関数を使用しても同じことができますね。
終わりに
いかがでしたでしょうか？今回も前回に引き続きアルゴリズムをJavaScriptで学習してみました。
複雑な問題を小さな問題に分けて、最後にそれを足し集めるような手順を分割統治法と呼んだりします。プログラミングで実装する上で大切な考え方ですね。今回のクイックソートも分割統治法の一種です。非常に勉強になりました！
今後も定期的にJavaScritpを通してアルゴリズムの実装を記事にしていきたいと思います！
ご覧いただきありがとうございました！
参考
e-word https://ewords.jp/w/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88.html
Wikipedia https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88