読者です 読者をやめる 読者になる 読者になる

timakin.log

╭( ・ㅂ・)و ̑̑

文系が学ぶコンピューターサイエンス╭( ・ㅂ・)و ̑̑:第5回【選択ソート】

選択ソートとは?

選択ソートとは、配列の先頭と、それ以降の最小値を交換するのを、各値に対して施すソート。
原理はそこまで難しくない。
ある値より先に、自分より小さい値があったら、それのうち一番小さいものと交換して、
どんどん先に進んでいくだけ。
普通はバブルソートの次くらいに学ぶっぽい。

選択ソートの実装

  // 選択ソート。計算量O(n^2)。
  selectionSort: function(data) {
    var min;
    for (var i = 0; i < data.length - 1; i++) {
      // 先頭を最小値とする。
      min = i;

      // 先頭から順に、それより小さい値があった場合そのうち一番小さいものと交換する。
      // 
      for (var j = i + 1; j < data.length; j++) {
        if (data[min] > data[j]) { min = j }; 
      }
      if (i != min) { this.swap(data, i, min) };
    }
    return data;
  }