JavaScriptで学ぶアルゴリズム③［ソートアルゴリズム⑶］-クイックソート

外資系企業でソフトウェアエンジニアをしております、タロイモと言います。今日もよろしくお願いします。

今回まで、O(n)とO(1)、O(log n)、O(n^2)、O(n log n)アルゴリズムの紹介をしてきました。

今回はO(n log n)のソートアルゴリズムの中でクイックソートを紹介します。

O(n log n)

以下の図を見て分かるとおり、O(n log n)はアルゴリズムとしてはあまり優れていません。

ただソートアルゴリズムはO(n^2)とO(n log n)しかないため、順番に並んでないバラバラなデータのときは、このO(n log n)アルゴリズムが最速になります。

クイックソート

実質、ソートアルゴリズムで最速なのがクイックソートです。

クイックソートは、数列から基準となる数字をランダムに1つ選びます。

そして、その基準となる数より大きい数、小さい数でグループに分けます。

さらにそのグループの中で、基準となる数字をランダムに1つ選び、基準となる数より大きい数、小さい数でグループに分けていき、順番を小さい順に並び替えていきます。

では、イラストで見ていきましょう。

以下のような数列があった場合、

ランダムに基準となる数を選びます。
今回は3が基準となる数になります。

次に、残りの数字を基準となる数と比べます。
例えば、2は、2<3なので、小さいグループに置きます。

1も小さいグループに入れ、7は、3<7なので大きいグループに入れます。

このようにグループ分けすると、以下のような数列になると思います。

次に小さいグループで基準の数を選び並び替えていきます。

1を基準の数とすると、2は、1<2なので大きいグループに置きます。

続いて、大きいグループでも同じように、基準の数を選び、グループ分けします。
6を基準にすると、

以下のように分けることができます。

今回は、運よく小さい順に並び替えることができたので、
ここでソートは終了ですが、これでも並び替えできない場合は、
さらにグループで基準を作り並び替えていく必要があります。

クイックソートをJavaScriptで表すと、以下のようになります。

let array = [2, 1, 7, 8, 3, 9, 4, 6, 5];

//クイックソート関数
function quick_sort(startId, endId) {
 //minからmaxの範囲からrandomな数を選ぶ関数
 function getRandomArbitrary(min, max) {
   return Math.floor(Math.random() * (max - min) + min);
 }
 let randomInt = getRandomArbitrary(startId, endId);
 //ピボットをランダムな数に指定
 let pivot = array[randomInt];
 //引数を左端、右端として変数にいれる
 let left = startId;
 let right = endId;

 //ピポットより小さい値を左側へ、大きい値を右側へ分割する
 while (true) {
   //leftの値がpivotより小さければleftを一つ右へ移動する
   while (array[left] < pivot) {
     left++;
   }
   //rightの値がpivotより小さければrightを一つ左へ移動する
   while (pivot < array[right]) {
     right--;
   }
   //leftとrightの値が同じだったら、そこでグループ分けの処理を止める。
   //rightとrightの値が同じになっていない場合、つまりグループが左右逆になっている場合、leftとrightを交換
   //交換後にleftを後ろへ、rightを前へ一つ移動する
   if (right <= left) {
     break;
   } else {
     let tmp = array[left];
     array[left] = array[right];
     array[right] = tmp;
     left++;
     right--;
   }
 }

 //左側に分割できるデータがある場合、quick_sort関数を呼び出す。
 if (startId < left - 1) {
   quick_sort(startId, left - 1);
 }
 //右側に分割できるデータがある場合、quick_sort関数を呼び出す。
 if (right + 1 < endId) {
   quick_sort(right + 1, endId);
 }
}

quick_sort(0, array.length - 1);
console.log(array); //[1, 2, 3, 4, 5, 6, 7, 8, 9]

次回は、ヒープソートを紹介いたします。

今回もご精読ありがとうございました。