👏

アルゴリズム入門【クイックソートもあるよ】

2021/10/19に公開

4件

アルゴリズム

メモ

idea

今回はアルゴリズムについて解説していこうと思います。

そもそも、アルゴリズムとはなんなのかということから、具体的な定番アルゴリズムについても解説していきます。

アルゴリズムとは

まずは、アルゴリズムとは何なのかということについて解説していきます。

アルゴリズムとは、一言で言うと
「問題解決までの正しい手順が漏れなく表現したもの」
になります。

例えば、料理のレシピがあります。

レシピは料理の完成という問題解決までの手順が漏れなく表現されたものです。

なので、レシピ通りに作ればある程度美味しい料理が作れます。

それと同じように、アルゴリズムをプログラミング言語で書いたものがプログラムになります。

良いアルゴリズムとは

次にどんなアルゴリズムが優れいてると言えるのでしょうか。

基本的に良いアルゴリズムとは次の4つの要素で判断することができます。

1.分かりやすい
文字通り、流れを把握しやすいかどうか
2.高速
処理速度が速いかどうか
3.効率が良い
メモリなどの資源効率が良いかどうか
4.再利用しやすい
文字通り、他の場所でも再利用しやすいか

なので、複数のアルゴリズムから良し悪しを判断したい時はこの4つについて考えればOKです。

定番アルゴリズム

今までアルゴリズムについて基本的なことを解説していきます。

さらに、どんなアルゴリズムがあるのかということを紹介していきます。

この基本的なアルゴリズムを抑えることがまずは大事なので、一緒に学んでいきましょう。

アルゴリズムの種類

アルゴリズムは主に4つに分類できます。

それは、

探索
整列
数値計算
文字列探索
です。

探索とは、対象のデータを探すことになります。

整列とは、要はソートのことです。

数値計算とは、対象のデータを得るための計算です。

そして、文字列探索とは文字列の探索になります。

今回は、これらの４種類のそれぞれの定番アルゴリズム数個ずつ紹介していきます。

探索

今回は、
線形探索法（リニアサーチ）
二分探索法（バイナリサーチ）
を解説します。

計算量はオーダー記法というもので表すと、
O(n)、O(log2n)となります。

意味わからないかもですが、バイナリサーチの方が高速ということだけ覚えておけばOKです。

線形探索法

線形探索法は「先頭から順番に探す値が見つかるまで探す方法」になります。

値をひとつひとつ調べていくので、データが大量になると時間がかかってしまう。

ただ、処理はめっちゃ単純なのでわかりやすいです。

手順としては、
1 先頭から末尾まで順番に値を調べる。
2 「調べた値」と「探す値」が同じならサーチ終了。
という流れです。


//検索する配列データ
const targetArr = [1, 3, 10, 2, 8];

//検索する値
const searchValue = 2;

//「調べた値」と「探す値」が一致したとき、indexを保存する変数。
//初期値はエラー(-1)に設定
let index = -1;

//繰り返し処理
for (let i = 0; i < targetArr.length; i++) {
  //条件分岐 「調べた値」と「探す値」が一致したとにきにindexを保存して処理終了
  if (targetArr[i] === searchValue) {
    index = i;
    break;
  }
}
//検索結果を表示する。(-1の場合は値がなかった)
console.log(targetArr[index]);

二分探索法

二分探索法は、「調べる範囲を半分に絞りながら探す方法」になります。

データがばらばらに並んでいると規則性がないので、あらかじめデータを順番に並べておく必要があります。

手順としては、
1 調べる範囲の左端と右端を決める
2 真ん中の位置を求める
(真ん中の値が「探す値」と一致したら処理終了)
3 真ん中の値が「探す値」より小さければ左端を移動する
(左側にはもっと小さい値しかないので、調べる必要がない)
4 真ん中の値が「探す値」より大きければ右端を移動する
(右側にはもっと大きい値しかないので、調べる必要がない)
5 調べる左端と右端の間にデータがある間は1~4の処理を繰り返す


//検索するソート済みの配列データ
const targetArr = [1, 2, 4, 5, 10];

//探す値
const searchValue = 1;

//
//「調べた値」と「探す値」が一致したとき、indexを保存する変数。
//初期値はエラー(-1)に設定
let index = -1;

//調べる左端を表す添字(index)
let left = 0;

//調べる右端を表す添字(index)
let right = targetArr.length - 1;

//左端と右端にデータがある間は処理を繰り返す
while (left <= right) {
  //左右の真ん中を表す添字(index)
  let middle = Math.floor((left + right) / 2);

  //真ん中の値と探す値を比較する
  if (targetArr[middle] === searchValue) {
    //一致した場合、変数に入れて処理終了
    index = middle;
    break;
  } else if (targetArr[middle] < searchValue) {
    //探す値より小さい場合、左側にはもっと小さい値しかないので左端の値を真ん中の値の右に移動する
    left = middle + 1;
  } else {
    //探す値より大きい場合、右側にはもっと大きい値しかないので右端の値を真ん中の値の左に移動する
    right = middle - 1;
  }
}

//検索結果を表示する。(-1の場合は値がなかった)
console.log(targetArr[index]);

整列

次に整列について見ていきます。

今回は
選択ソート
バブルソート
クイックソート
について解説します。

計算量は、前者2つがO(n2乗)、O(nlogn)となります。

選択ソート

選択ソートとは、小さいものを探して先頭から交換して入れいてく方法になります。

手順としては、
1 最小値を見つけて、「最小値を入れる変数」に暫定的にいれる
2 「最小値の位置を入れる変数」も用意して暫定的にいれる
3 比較を繰り返して上記の変数を更新していく
4 繰り返しが終わったら先頭の値と最小値の値を交換する
5 残った部分にも同じように繰り返していく
という感じになります。

要は、最小値を毎回見つけて埋めていくという方法になります。


//ソート前の配列データ
const targetArr = [1, 3, 10, 2, 8];

//「最小値を入れる位置」を先頭から順番に選択していくfor文
for (let i = 0; i < targetArr.length - 1; i++) {
  //最小値を探すアルゴリズム
  //先頭の値を暫定の最小値として初期設定する
  let min = targetArr[i];
  //先頭の位置を保存する
  let k = i;

  //隣の位置から最後まで、最小値との比較を繰り返す
  for (let j = i + 1; j < targetArr.length; j++) {
    //比較して最小値を更新するif文
    if (min > targetArr[j]) {
      min = targetArr[j];
      k = j;
    }
  }
  //交換するアルゴリズム
  //「先頭の値」と「最小値の値」を交換する
  let tmp = targetArr[i];
  targetArr[i] = targetArr[k];
  targetArr[k] = tmp;
}
  //ソートの値を表示
  console.log(targetArr);

バブルソート

バブルソートとは、隣り合うもの同士を右から比べて位置を交換していく方法になります。

データが大量になると時間がかかってしまうという欠点があります。

手順としては、
1 末尾の二つの値を比べる。後ろの値が小さい場合、前の値と交換する。
2 前方に向かって繰り返す
3 添字(index)0まで繰り返すと、「最も小さい値」が先頭になる
4 残りの値にも同じように処理を繰り返す
5 最後まで処理が終わると昇順に並んでいる
になります。

要は、隣同士を比較し続けてソートしていく方法ということです。


//ソート前の配列データ
const targetArr = [1, 3, 10, 2, 8];

//調べる範囲の開始位置を１つずつ後ろへ移動するfor文
for (let i = 0; i < targetArr.length; i++) {
  //後ろから前に向かって小さい値を浮かび上がらせるfor文
  for (let j = targetArr.length - 1; j > i; j--) {
    //隣りあう２つの値を比べて、後ろが小さければ交換する
    if (targetArr[j] < targetArr[j - 1]) {
      let tmp = targetArr[j];
      targetArr[j] = targetArr[j - 1];
      targetArr[j - 1] = tmp;
    }
  }
}
//ソート後の配列の表示
console.log(targetArr);

クックソート

クイックソートとは、基準を決めて大小をグループ化していく方法になります。

クイックソートはその名にクイックとあるように処理速度のそこそこ速いコードです。

手順としては、
1 再帰のための関数を作成する。引数にソートの開始位置と終了位置を設定する。
2 開始位置と終了位置からピボットを決めて、「交換する必要のある値だけを交換」して大小のグループに分割します。
3 分割したグループに対してさらに大小のグループに分けるように再帰的に処理を繰り返します。
4 分割できなくなるまで処理を繰り返しを行えばソート完了
になります。


//クイックソート関数
function quickSort(startID, endID) {
  //範囲の間にある値をピポットに設定する
  const pivot = targetArr[Math.floor((startID + endID) / 2)];
  //引数を左端、右端として変数にいれる
  let left = startID;
  let right = endID;

  //ピポットより小さい値を左側へ、大きい値を右側へ分割する
  while (true) {
    //leftの値がpivotより小さければleftを一つ右へ移動する
    while (targetArr[left] < pivot) {
      left++;
    }
    //rightの値がpivotより小さければrightを一つ左へ移動する
    while (pivot < targetArr[right]) {
      right--;
    }
    //leftとrightの値がぶつかったら、そこでグループ分けの処理を止める。
    if (right <= left) {
      break;
    }

    //rightとrightの値がぶつかっていない場合、leftとrightを交換
    //交換後にleftを後ろへ、rightを前へ一つ移動する
    const tmp = targetArr[left];
    targetArr[left] = targetArr[right];
    targetArr[right] = tmp;
    left++;
    right--;
  }

  //左側に分割できるデータがある場合、quickSort関数を呼び出して再帰的に処理を繰り返す。
  if (startID < left - 1) {
    quickSort(startID, left - 1);
  }
  //右側に分割できるデータがある場合、quickSort関数を呼び出して再帰的に処理を繰り返す。
  if (right + 1 < endID) {
    quickSort(right + 1, endID);
  }
}

//未整列の配列
const targetArr = [3, 7, 2, 4, 6, 1, 9, 8, 5];
//先頭から末尾までソートする
quickSort(0, targetArr.length - 1);

//結果の表示
console.log(targetArr);

数値計算

次に数値計算について解説していきます。

今回紹介するのは、
エラトステネスのふるい
になります。

エラトステネスのふるい

エラトステネスのふるいは、素数を見つけるための数値計算になります。

・探索範囲（2〜N）の全整数を用意する。
・Nの平方根以下の素数の倍数をその全整数から取り除いていく。
・残った数を出力する。


function getPrime() {
  let primes = [];
  let i, j;
  const num = 1000;

  for (i = 2; i <= num; i++) primes[i] = true;

  for (i = 2; i <= Math.sqrt(num); i++) {
    if (primes[i] === true) {
      for (j = i * 2; j <= num; j += i) primes[j] = false;
    }
  }

  for (i = 2; i <= num; i++) {
    if (primes[i] === true) {
      console.log(i);
    }
  }
}

getPrime();