JavaScriptでサーチ・ソートアルゴリズムを学ぶ

アルゴリズムは問題の解決方法を示す手順やルールのことです。普段から意識してプログラミングしている方はどれほどいるでしょうか。
データ量が増えてくると、アルゴリズムを意識したプログラミングが必要になってきます。適切なアルゴリズムを選択することで、プログラムの実行速度が大きく変わってきます。

今回は、JavaScriptでサーチ・ソートアルゴリズムを学ぶことを目的としています。

サーチアルゴリズム

データの中から目的のデータを探すアルゴリズムです。
適切なアルゴリズムを選択することで、探索時間を短縮できます。

さまざまなサーチアルゴリズムがありますが、今回は、リニアサーチとバイナリサーチを紹介します。

リニアサーチ

線形探索法とも呼ばれます。
配列の先頭から順番に目的のデータを探します。

単純な探索方法ですが、配列の要素数が少ない場合には、適切なアルゴリズムです。

const linearSearch = (array, target) => {
  for (let i = 0; i < array.length; i++) {
    // 見つかったらその時点で探索を終了する
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
};

この方法は、配列の先頭から順番に目的のデータを探すため、データが見つかるまでに探索時間がかかります。

バイナリサーチ

二分探索法とも呼ばれます。
配列の中央の値と目的のデータを比較し、目的のデータが中央の値より大きいか小さいかで、探索範囲を半分に絞り込みます。

データ量が多い場合には、適切なアルゴリズムです。

const binarySearch = (array, target) => {
  // 探索範囲の先頭のインデックス
  let head = 0;
  // 探索範囲の末尾のインデックス
  let tail = array.length - 1;

  // 探索範囲が存在する限り繰り返す
  while (head <= tail) {
    // 探索範囲の中央のインデックス
    const mid = Math.floor((head + tail) / 2);
    // 中央の値と目的の値を比較する
    if (array[mid] === target) {
      // 中央の値と目的の値が一致したら探索を終了する
      return mid;
    }
    // 中央の値より目的の値が大きい場合は、探索範囲の先頭を中央の次の値にする
    else if (array[mid] < target) {
      head = mid + 1;
    }
    // 中央の値より目的の値が小さい場合は、探索範囲の末尾を中央の前の値にする
    else {
      tail = mid - 1;
    }
  }
  // 見つからなかった場合は-1を返す
  return -1;
};

前提条件として、二分検索はソート済みの配列に対してのみ有効です。

この方法は、配列の中央の値と目的のデータを比較し、探索範囲を半分に絞り込むため、探索時間が短縮されます。

実行結果

実際に、リニアサーチとバイナリサーチを比較してみます。
有意な差を出すため、配列の要素数を10000にして、探索対象の値を9999とします。

let array = [];
for (let i = 0; i < 10000; i++) {
  array.push(i);
}
const target = 9999;

console.time("linearSearch");
linearSearch(array, target);
console.timeEnd("linearSearch");

console.time("binarySearch");
binarySearch(array, target);
console.timeEnd("binarySearch");

実行結果は以下の通りです。
アルゴリズムの違いで、探索時間が大きく変わっているのがわかります。

	linearSearch	binarySearch
time	0.329ms	0.022ms

まとめ

	リニアサーチ	バイナリサーチ
特徴	配列の先頭から順番に目的のデータを探す	配列の中央の値と目的のデータを比較し、探索範囲を半分に絞り込む
メリット	探索範囲が小さい場合には、適切なアルゴリズム	探索範囲が大きい場合には、適切なアルゴリズム
デメリット	探索範囲が大きい場合には、探索時間がかかる	探索範囲が小さい場合には、探索時間がかかる

ソートアルゴリズム

データを並び替えるアルゴリズムです。

バブルソート

隣り合う要素を比較し、大小を入れ替えていくアルゴリズムです。
泡が上に上がっていくように、配列の要素を並び替えていきます。

const bubbleSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let j = array.length - 1; j > i; j--) {
      // 隣り合う要素を比較し、大小を入れ替える
      if (array[j] < array[j - 1]) {
        let tmp = array[j];
        array[j] = array[j - 1];
        array[j - 1] = tmp;
      }
    }
  }
  return arr;
};

この方法は、隣り合う要素を比較し、大小を入れ替えるため、要素数が多い場合には、探索時間が長くなります。

選択ソート

配列の中から最小の要素を選び、配列の先頭に移動させます。
その後、残りの要素から最小の要素を選び、配列の先頭から2番目に移動させます。
このように、配列の先頭から順番に最小の要素を選び、並び替えていきます。

const selectionSort = (array) => {
  for (let i = 0; i < arr.length - 1; i++) {
    // 最小値のインデックスを格納する変数
    let minIndex = i;
    // 最小値のインデックスを探索する
    for (let j = i + 1; j < arr.length; j++) {
      // 最小値のインデックスを更新する
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 最小値のインデックスが変わっていた場合は、要素を入れ替える
    let tmp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = tmp;
  }
  return arr;
};

この方法は、配列の先頭から順番に最小の要素を選び、並び替えるため、要素数が多い場合には、探索時間が長くなります。
ただし、交換回数が少ないため、バブルソートよりも高速に動作します。

挿入ソート

配列の先頭から順番に、要素を取り出し、適切な位置に挿入していくアルゴリズムです。

const insertionSort = (array) => {
  for (let i = 1; i < arr.length; i++) {
    // 挿入する値を一時的に保存する
    let currentVal = arr[i];
    let j = i - 1;
    // 挿入する位置を探索する
    while (j >= 0 && arr[j] > currentVal) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = currentVal;
  }
  return arr;
};

この方法は、配列の先頭から順番に要素を取り出し、適切な位置に挿入していくため、要素数が多い場合には、探索時間が長くなります。
バブルソートや選択ソートよりも高速に動作します。

クイックソート

配列の中から、基準となる要素を選び、基準よりも小さい要素を左側に、大きい要素を右側に配置します。
その後、左側と右側の配列に対して、再帰的に同じ処理を行います。

ソートアルゴリズムの中では、高速に動作するアルゴリズムです。

const quickSort = (array) => {
  // 配列の要素数が1以下の場合は、そのまま返す
  if (array.length <= 1) {
    return array;
  }

  // 基準となる要素を選ぶ(今回は配列の中心を基準とする)
  const pivot = array[Math.floor(array.length / 2)];

  // 基準となる要素を除いた、左側の配列
  const left = [];
  // 基準となる要素を除いた、右側の配列
  const right = [];
  
  // 基準となる要素を除いた配列を作成する
  for (let i = 0; i < array.length; i++) {
    if (i === Math.floor(array.length / 2)) {
      continue;
    }
    if (array[i] < pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }

  // 再帰的に処理を行い、結果を返す
  return [...quickSort(left), pivot, ...quickSort(right)];
};

実行結果

実際に、それぞれのアルゴリズムの探索時間を計測してみます。
配列の要素数は10000個とし、要素の値は0〜9999の乱数とします。

let arr = [];
for (let i = 0; i < 10000; i++) {
  arr.push(Math.floor(Math.random() * 10000));
}

console.time("bubbleSort");
bubbleSort([...arr]);
console.timeEnd("bubbleSort");

console.time("selectionSort");
selectionSort([...arr]);
console.timeEnd("selectionSort");

console.time("insertionSort");
insertionSort([...arr]);
console.timeEnd("insertionSort");

console.time("quickSort");
quickSort([...arr]);
console.timeEnd("quickSort");

実行結果は以下の通りです。

アルゴリズム	探索時間
バブルソート	65.978ms
選択ソート	41.491ms
挿入ソート	21.02ms
クイックソート	9.271ms

まとめ

	バブルソート	選択ソート	挿入ソート	クイックソート
特徴	隣り合う要素を比較し、大小を入れ替える	配列の先頭から順番に最小の要素を選び、並び替える	配列の先頭から順番に要素を取り出し、適切な位置に挿入する	配列の中から、基準となる要素を選び、基準よりも小さい要素を左側に、大きい要素を右側に配置する
メリット	簡単に実装できる	簡単に実装できる	簡単に実装できる	要素数が多い場合でも、探索時間が短い
デメリット	探索時間が長い	探索時間が長い	探索時間が長い	要素数が少ない場合には、探索時間が長い

さいごに

アルゴリズムを適切に選択することで、プログラムの実行速度が大きく変わってくることがわかりました。
大量のデータを扱う場合に限らず、普段から意識してプログラミングすることで、より良いプログラムを書くことができます。

参考

• アルゴリズムとプログラミングの図鑑 第２版