【JavaScript】配列のソートについてちょっとじっくり考えてみました

　予め断っておきますが、車輪の再発明というか、火おこしみたいな記事です。

var numbers = [5, 8, 1, 4, 7, 10, 2, 6];

numbers.sort(function(first, second) {
  return first - second;
});

console.log(numbers);
//=> "[1, 2, 4, 5, 6, 7, 8, 10]"

　初めてこれを目にした時、これは一体どうなってんだ？ってなりました。よく書籍にも登場しますが詳しい解説がないような気がします。結論だけだったり解説が簡潔すぎたりで。そこで、自作する過程で何か得られるのではないかと思ってやってみます。

　①配列から最小のものを抽出する。
　②それを新配列に追加する。
　③配列からいま抽出したものを削除する。
　④これを繰り返す。
　⑤最後に新配列を出力。

　こんな感じでしょうか？

　まず最小のものを抽出する関数から作ってみます。Math.min()を使っているようでは火おこしとは言えないのでこれも自作してみます。関数名が重複するのもややこしいのでhiokoshiオブジェクトを作ってそのメソッドという位置づけでやっていきます。

var hiokoshi = {};

var numbers = [5, 8, 1, 4, 7, 10, 2, 6];

hiokoshi.min = function(ary) {
  var num = ary[0];
  for (var i=1; i<ary.length; i++) {
    if (num <= ary[i]) {
      num = num;
    } else if (num > ary[i]) {
      num = ary[i];
    }
  }
  return num;
};

console.log(hiokoshi.min(numbers));
//=> 1

　n番目とn+1番目の数値を比較して小さい方を勝者とし、これを繰り返して最後に勝ち残ったものが答えということになります。つまり、5 vs 8 => 5, 5 vs 1 => 1, 1 vs 7 => 1,・・・という感じです。

　ソートに取り掛かります。最初に提示した考え方で昇順に並び替える関数sort_ascを作ってみます。

hiokoshi.sort_asc = function(ary) {
  var new_ary = [];
  while (ary.length) {
    var num = hiokoshi.min(ary);
    new_ary.push(num);
    for (var i=0; i<ary.length; i++) {
      if (num === ary[i]) {
        ary.splice(i,1); // .spliceの火おこしは勘弁。
        break; // 重複値が不要であればここは外す。
      }
    }
  }
  return new_ary;
};

console.log(hiokoshi.sort_asc(numbers));
//=> "[1, 2, 4, 5, 6, 7, 8, 10]"

　最初に述べたように、配列の中から最小値を取得して新配列に追加するとともに配列から最小値を削除し、この動作を繰り返していけば昇順ソートされた配列が得られます。

　しかし、冒頭のコードが内部でどう動いているのかは謎のままで得られたものはないです（苦笑）。内部では新しい配列を用意するなんてことはしてなさそうだし。また随時編集していきたいと思います。