【アルゴリズム】JavaScriptでソート問題を解く

#はじめに
Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回はソート問題(バブルソート、選択ソート、マージソート)をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

#バブルソート
配列をバブルソートでソートしてください。
＊バブルソートは、隣り合うふたつの要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。

##解答
配列の先頭から末尾に向かって隣り合う要素を比較し、前の要素が後ろの要素よりも大きければ交換するような処理を考えます。
これを実現するために二重ループを用います。
要素の交換のために、arr[j+1]の値を一度lesserという変数に格納しています。

index.js

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const lesser = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = lesser;
      }
    }
  }

  return arr;
}

#選択ソート
配列を選択ソートでソートしてください。
＊選択ソートは、線形探索で取得した最小値と左端の値との交換(ソート)を繰り返す整列アルゴリズムです。

##解答
バブルソートと同様に二重ループを用います。
最小値のインデックスをindexOfMinとして、線形探索で更新していきます。
その後に得られた最小値arr[indexOfMin]をarr[i]に設定します。
これらの処理を配列の末尾まで繰り返します。

index.js

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexOfMin = i;
    
    // 最小値のインデックス(indexOfMin)を更新
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexOfMin]) {
        indexOfMin = j;
      }
    }

    // 最小値をarr[i]に設定
    if (indexOfMin !== i) {
      let lesser = arr[indexOfMin];
      arr[indexOfMin] = arr[i];
      arr[i] = lesser;
    }
  }

  return arr;
}

#マージソート
配列をマージソートでソートしてください。
＊マージソートは配列を半分ずつ分割していき、小さい順に並べ替えてマージしていく整列アルゴリズムです。

##解答
配列を分割するまでの処理をmergeSort()、並び替えてマージする処理をmerge()に分けます。

The Coding Interview Bootcamp

mergeSort()では配列の中心centerを算出してleftとrightに分割します。
merge(mergeSort(left), mergeSort(right))を返し、arr.length === 1になるまで再帰呼び出しを行います。

merge()では分割した配列left rightを引数にとり、それぞれの配列の先頭から順番に比較していきます。
比較して小さい方の値からresultsに格納していき、これをleft rightのどちらかが空になるまで繰り返していきます。
最終的にソートされた結果を[...results, ...left, ...right]として返します。

このように、mergeSort()とmerge()を使うことでマージソートを行うことができます。

index.js

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }

  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const results = [];

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }

  return [...results, ...left, ...right];
}

#参考資料
https://www.udemy.com/share/101WNkCEEZd11VRno=/