【JavaScriptでアルゴリズム】並び替え(クイックソート)

アルゴリズム

今回はクイックソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。

クイックソートとは

まずソートとはデータを並べ替えることをいい、クイックソートとは、軸となる基準値より小さなデータと大きなデータに振り分け、データを2つに分けることを再帰的に繰り返しながらソートするという方法になります。

①軸となる基準値(pivot)をデータの中から決める(ランダムでよい)

②配列の左から pivot 以上の値を、右から pivot 未満の値を探し、交換する。
 この操作を、「左」と「右」が逆転するまで続ける。

③「左」と「右」が逆転したら、データを2つに分け、それぞれに対し①②を繰り返す。



では実際に、以下のデータをクイックソートしてみます。
6,2,7,4,9,1,5,8,0,3


pivot の決め方は何でもよいので、今回は配列の最初の2つのデータ(6,2)のうち大きい方(6)に設定することにします。
,2,7,4,9,1,5,8,0,3

ではから pivot 以上の値を、から pivot 未満の値を探します。
,2,7,4,9,1,5,8,0,

そして交換します。
,2,7,4,9,1,5,8,0,

再び探していきます。
3,2,,4,9,1,5,8,

そして交換します。
3,2,,4,9,1,5,8,

再び探していきます。
3,2,0,4,,1,,8,7,

そして交換します。
3,2,0,4,,1,,8,7,

再び探していきます。
3,2,0,4,5,,8,7,


ここで「」と「」が逆転したため探索を終え、
」より前のデータ群と、「」以降のデータ群に分けます。

3,2,0,4,5,1  |  9,8,7,6


ここで注目してほしいのが、左側には pivot 未満のデータが、右側には pivot 以上のデータが
自動的に振り分けられている
ということです。

続けてそれぞれのデータ群に対し、同様の処理を繰り返していくことで昇順にソートすることができます。

実装

function quickSort(array, min, max) {
  let pivotIndex = findPivot(array, min, max);

  if (pivotIndex > -1) {
    let pivot = array[pivotIndex];

    let l = arrange(array, min, max, pivot);

    quickSort(array, min, l-1);
    quickSort(array, l, max);
  }
}

function findPivot(array, min, max) {
  let pivot = array[min];
  let k = min + 1;

  while (k <= max) {
    if (array[k] == pivot) {
      k++;
    }else{

      if (array[k] > pivot) {
        return k;
      }else{
        return min;
      }
    }
  }
  return -1;
}

function arrange(array, min, max, pivot) {
  let l = min;
  let r = max;

  while (l <= r) {
    let tmp = array[l];
    array[l] = array[r];
    array[r] = tmp;

    while (array[l] < pivot) {
      l++;
    }

    while (array[r] >= pivot) {
      r--;
    }
  }

  return l;
}

let datas= [
  6,2,7,4,9,1,5,8,0,3
];
let min = 0;
let max = datas.length-1;

quickSort(datas, min, max);
console.log(datas);//0,1,2,3,4,5,6,7,8,9と表示

解説

まず、簡単に3つの関数の役割を確認します。

関数名役割
quickSort引数の配列をクイックソートする
findPivotpivot となるデータのインデックスを返す
arrange引数の配列のデータを入れ替え、「左」のインデックスを返す

では、quickSort 関数の中身をみていきます。

まず最初に findPivot 関数で pivot のインデックスを取得しています。

let pivotIndex = findPivot(array, min, max);




いったん findPivot 関数をみてみます。

配列の最初のデータを仮に pivot と設定し、ふたつめのデータのインデックスを k と置きます。

  let pivot = array[min];
  let k = min + 1;



もし最初の2つのデータが同じ値なら、異なる値が見つかるまで探し、その後大きい方のデータのインデックスを pivot として返します。

配列にデータが1つしかない、あるいは全てのデータが同じ値の場合は-1を返します。

  while (k <= max) {
    if (array[k] == pivot) {
      k++;
    }else{

      if (array[k] > pivot) {
        return k;
      }else{
        return min;
      }
    }
  }
  return -1;



では quickSort 関数にもどります。

取得した pivot のインデックスが-1でなければ、配列から pivot を取得し arrange 関数を呼び出します。

  if (pivotIndex > -1) {
    let pivot = array[pivotIndex];

    let l = arrange(array, min, max, pivot);

    ...
  }



では arrange 関数をみてみます。

min, max をそれぞれ l ( left ) , r ( right ) に入れ、l が r より大きくなるまで交換を行い、最終的な l の値を返します。

  let l = min;
  let r = max;

  while (l <= r) {
    let tmp = array[l];
    array[l] = array[r];
    array[r] = tmp;

    while (array[l] < pivot) {
      l++;
    }

    while (array[r] >= pivot) {
      r--;
    }
  }

  return l;



では quickSort 関数にもどります。

arrange 関数で取得した l を軸に2つのデータ群に分け、それぞれに対し quickSort 関数を呼び出します。

    let l = arrange(array, min, max, pivot);

    quickSort(array, min, l-1);
    quickSort(array, l, max);



このように、quickSort 関数を再帰的に繰り返すことでソートすることができます。



ちなみに、自分自身の関数を呼び出す関数のことを、再帰関数といいます。

下の記事で解説しているので、よかったらどうぞ!





参考書

コメント

コンタクトフォーム

    タイトルとURLをコピーしました