JavaScriptでソートの仕組みを真似して書いてみた

初めに

今回は自分に出す宿題の振り返りです。文系出身で数学が苦手ですが、プログラミングの勉強にはアルゴリズムと向き合わないといけないと思い、自分なりにソートへの理解を深めて、JSを使って書いてみました。
アルゴリズムの勉強は、こちらの視覚化したソート VisuAlgo を使いました。
ソート以外いろんなアルゴリズムもとてもわかりやすく視覚化されています。ご興味のある方ぜひ！
Quick Sort と Random Quick Sortはうまく書けず今後の課題にしています。

Bubble Sort

function bubble(arr) {
  // let bigger number always stay on right side
  // if arr[n] > arr[n+1], arr[n] <=> arr[n+1]
  // if arr[n] < arr[n+1], arr[n => n+1], arr[n+1 => n+1+1]
  let temp = 0
  for (let i = 0; i < arr.length; i++) {
    temp = 0
    for (let j = temp + 1; j < arr.length - i; j++) {
      // console.log('temp:', temp, 'j:', j)
      if (arr[temp] > arr[j]) {
        [arr[temp], arr[j]] = [arr[j], arr[temp]]
        temp++
        // console.log('temp>j: ', arr)
      } else {
        temp++
        // console.log('temp<j: ', arr)
      }
    }
  }
  return arr
}

console.log(bubble([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]))
// console.log(bubble([3, 44, 38, 5, 47, 15, 36, 26, 27, 2]))

/*
note: two numbers compare and change each other, 
if they weren't changed, it means we find the biggest number currently.
After all the loop is iterated, we can put the number on the right side and ignore it.
note: renew the next loop's array index
*/

バブルソートは、自分を基準として右側にある数字と比べて、右より小さければそのまま、大きければ右と位置交換する。それなら二重ループとif条件判断を行って、ES6のdestructuring assignment（分割代入）の書き方を使って交換させる。
最初は簡単にできたけれど、でもこれじゃ二重ループで暴力的に処理させるだけですし、排除できる要素はないかな？そう思って何度もバブルのパワポを一個ずつ眺めていました。
最初は一番大きい数字が一番右側に、そして二番大きいのはその左に置き比較の動作もなく...なるほど、毎回の走査では今一番大きい数字が生き残り一番右側に行ったので、比較する必要もなくなった！
毎回の走査は length -1 の感覚でしたので、ループの長さは毎回 -i にしました。

tempを宣言しなくてもこのソートarr[j], arr[j+1]でも行けます。これを書く前に別の練習問題で位置交換のコードも書いたことがあって、二重ループで暴力アルゴリズムのやつでした。いつも自分の右側にあるものと比べるのがロジックにあってるんですが、最後の要素はなにと比べる？undefinedです。存在しないはずの値をアクセスしてしまうので変なエラーが出てくるかもしれない。それ以来前の要素と比較するように書いています。

Selection Sort

function selection(arr) {
  // find the smallest number, put in the left side
  for (let i = 0; i < arr.length; i++) {
    let temp = arr[i]
    let index = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < temp) {
        temp = arr[j]
        index = j
        // console.log(arr)
      }
    }
    [arr[i], arr[index]] = [arr[index], arr[i]]
  }
  return arr
}

console.log(selection([5, 50, 23, 41, 30, 46, 39, 35, 11, 41, 20, 9, 38]))
// console.log(selection([5, 50, 23, 41, 30, 46, 39]))

セレクションは、バブルの逆バージョンみたい一番小さい数字を見つけ出し、一番左側に置いていく仕組みでした。ここはtempにいまの要素、indexでi⇒j、見つかった一番小さい数字のインデックスを保管する。index = 0 はだめでしょうか？ループの中に変数で一時的に値を保管するとき、よくデフォルト値として0、-Infinity、Infinityなどに入れていますが、今の要素が一番小さい数字である可能性があるから i にしておきました。

Insertion Sort

function insertion(arr) {
  for (let i = 1; i < arr.length; i++) {
    let index = -Infinity
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > arr[i]) {
        index = j
      }
    }
    if (index !== -Infinity) {
      // console.log(i, arr, arr[i])
      arr.splice(index, 0, arr[i])
      // console.log(i, arr, arr[i])
      arr.splice(i + 1, 1)
    }
  }
  return arr
}

console.log(insertion([35, 42, 35, 41, 9, 20, 42, 21, 8, 31, 12, 44, 23, 26, 16]))
// console.log(insertion([35, 42, 35, 41, 9]))

インサーションも外側のインデックスを 1 から、内側はiまで全ての要素を -1 で左に向かって一個ずつ比べていく感じでした。indexが -Infinity ではない場合、下のsplice()メソッドに入れて、deleteCountというパラメータが 0 にするとき、要素を指定インデックスに挿入することとなります。JSにはinsertメソッドがない、代わりにsplice()でよく使われます。（splice()は元の配列を変えるメソッド）
splice()の挿入は元の要素を切り取って新しい場所に移すのではなく、元の要素が残ったまま配列の長さが変わりますので、ループが永遠に終わらない、またアルゴリズムの要求とも合わないので、もう一回splice()で元要素のインデックス+1を取り除く（↑の挿入ですでに配列のインデックスが変わった）。

Array.prototype.splice() - JavaScript | MDN

Merge Sort

function merge(arr) {
  let mid = arr.length / 2

  let frontToMid = sort(cutArr(arr, 0, mid))
  let midToBack = sort(cutArr(arr, mid, arr.length))
  // console.log(sort(cutArr(arr, 0, mid)))

  let result = []
  for (let i = 0; i < arr.length; i++) {
    if (frontToMid[0] < midToBack[0]) {
      result.push(frontToMid[0])
      frontToMid.shift()
    } else if (frontToMid[0] === midToBack[0]) {
      result.push(frontToMid[0], midToBack[0])
      frontToMid.shift()
      midToBack.shift()
      i++
    } else {
      result.push(midToBack[0])
      midToBack.shift()
    }
  }
  return result
}

console.log(merge([11, 20, 13, 47, 18, 18, 48, 16, 1, 27]))
console.log(merge([11, 20, 13, 47, 21, 18, 48, 16, 1, 27]))


function cutArr(arr, start, end) {
  let result = []
  for (let i = start; i < end; i++) {
    result.push(arr[i])
  }
  return result
}

function sort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 1; j < arr.length; j++) {
      if (arr[j] < arr[j - 1]) {
        arr.splice(j - 1, 0, arr[j])
        arr.splice(j + 1, 1)
      }
    }
  }
  return arr
}

マージのとき苦戦していました。この書き方はパワポの動作と少し違います。マージはBisection method（二分法）で数字のグループを作っていく（length >= 2）、小⇒大のようにグループ内要素の比べが終わったら、隣接グループと、互いに今のインデックスの数字と比べて、小さいほうを新しい配列に入れるようにしている。
例えば、Aグループarr[0]は10、Bグループarr[0]は、Aグループのほうが小さいので新しい配列に入れる。次はAグループarr[1]とBグループarr[0]...のように比べていきます。パワポでの動きを見ればすぐわかると思いますが、今の自分にとって実作結構難しいです。
最初はパワポのようにグループ化したいと思って再帰のやり方で二次元配列を作るつもりですが、要素を走査するため二重ループが必要になって（ここはmap()など考えない前提として）、新しい配列に入れるということは、新しい配列を挿入して古い配列を削除する工夫も必要だし、そしてもう一度二次元配列を作らなきゃいけなくなって、また二重ループにするしかない、全員と比べる必要はないかもしれませんが、配列の長さに従い複雑さが変わってしまう理由もあるので、やっぱりマージ法での要素比較の扱い方を今回の目標にして元の配列を一回だけ折半して書いてみました。

// 自分の中でマージパワポの動き
[11, 20, 13, 47, 18, 18, 48, 16, 1, 27]
[[11, 20], [13, 47], [18, 18], [48, 16], [1, 27]]
[[11, 20], [13, 47], [18, 18], [48, 16], [1, 27]]
[[11, 13, 20, 47], [18, 18], [48, 16], [1, 27]]
[[11, 13, 20, 47], [18, 18], [16, 48], [1, 27]]
[[11, 13, 20, 47], [16, 18, 18, 48], [1, 27]]
...
/* 
二次元配列の準備からグループ内の比べ、新しい配列を返しと古い要素の削除等々、
それに長さが変わってしまうので気を付けないといけないところいっぱいある。
もっといい方法あるはず、今の自分はまだうまく解決できません。
*/

Counting Sort

function counting(arr) {
  let counter = []
  for (let i = 1; i <= arr.length; i++) {
    counter[i] = 0
  }
  // console.log(counter)

  for (let i = 0; i < arr.length; i++) {
    counter[arr[i]]++
  }
  // console.log(counter)

  let result = []
  for (let i = 1; i < counter.length; i++) {
    if (counter[i] > 0) {
      for (let j = 0; j < counter[i]; j++) {
        result.push(i)
      }
    }
  }
  return result
}

console.log(counting([2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4]))

カウンティングはマージのあとで書いたものです。ある意味で救われました。
arrで 1 から、一番大きい数字までの長さの配列作っておいて、デフォルト値は全て0。forで要素を走査し、要素を配列のインデックスとして++（出現したことをカウントする）、最後は配列の要素が 0 じゃないとき、そのインデックスをresultにpush、ループ回数は要素自身です。

今振り返ると自分の書き方の欠点を気づきました。最初はまず一回走査して一番小さい数字と大きい数字を取り出すべきだった...。

  let head = Infinity
  let length = -Infinity

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < head) {
      head = arr[i]
    }
    if (arr[i] > length) {
      length = arr[i]
    }
  }

  for (let i = head; i <= length; i++) {
    counter[i] = 0
  }
...

またcounting法のいくつ注意点も感じました。負数、数字の区間（距離）が大きすぎる場合はcounting法に合わない。

Radix Sort

function radix(arr) {
  // digits
  let digits = 0
  let strArr = arr.map(num => num.toString())
  for (let i = 0; i < strArr.length; i++) {
    if (strArr[i].length > digits) {
      digits = strArr[i].length
    }
  }

  let copy = arr
  // let result = []
  let temp = [
    [],
    [],
    [],
    [],
    [],
    [],
    [],
    [],
    [],
    [],
  ]

  for (let k = 1; k <= digits; k++) {
    // console.log(copy)
    // console.log(temp)
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < 10; j++) {
        if (copy[i] % 10 === j) {
          temp[j].splice(temp.length, 0, arr[i])
        }
      }
    }
    // console.log(k, temp)
    let shiftArr = []
    for (let i = 0; i < temp.length; i++) {
      while (temp[i].length > 0) {
        shiftArr.push(temp[i].shift())
      }
    }
    arr = shiftArr

    for (let i = 0; i < shiftArr.length; i++) {
      copy[i] = Math.floor(shiftArr[i] / 10 ** k)
    }
    // console.log(k, shiftArr)
    // console.log(arr)
  }
  return arr
}
radix([3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127])
// radix([3221, 1, 10, 9680, 577, 9420, 7, 5622])

ラディックスと、丸二日戦いました。基数って十進法だから % 10 剰余を使えばいいって頭では理解できてるけど、実際書くと三重ループになったり、外に段階ごとのfunctionを書いたりして、でも何か違う気がしてしまって何度も削除しました。（剰余の再帰functionも書いてみたけど、配列を一つの値として返すのではなく、毎回返した値がほしい、その値で走査したい...これを思った時点でforしかないと感じました）
まず桁数を算出、これがないと一番外側にあるforが成り立ちません。
次は元の配列のコピー、と初期化した二次元配列グループ。
（元の配列で計算してはいけません、毎回グループ化された要素を平坦化した結果を記録しなきゃいけないから。しかし除算すると要素を変えてしまう、なのでcopyが必要。）
材料が揃えたので、さあ料理を始めましょう！
剰余ループは桁数回、要素ごとに施すためforで走査して、条件判断で基数グループに挿入していく。
shiftArrでグループ化された配列の要素を取り出し、元の配列を書き換える。
copyはshiftArrを10の桁数で除算した値を受けて（インデックス上書き）、二回目ループにいく。

shiftArrが本当に必要でしょうか。元の配列（arr）に上書きすればいいじゃないんですか。（自問自答）
正直、初心者である私は簡単な配列操作しかわかりません。
感覚としては、すべての要素の元はarrなので、できるだけ元の配列を変えないようにしていきたいと思っています。
また、元を少しずつ変えると、確定したものとまるごと置き換える、意味として違うとも思っています。

感想

ここに来られて五ヶ月かかりました。二ヶ月前の自分なんて基礎レベルの練習問題すら解けない、アルゴリズムを真似して書くのも絶対ありえなかった。やっとですね！Syntaxもメソッドの使い方も徐々に慣れてきました。しかし一つの山を越え、目の前にまたいくつの山が現れました。未解決の課題は未来の自分に任します。