文系が学ぶコンピューターサイエンス╭( ・ㅂ・)و ̑̑:第6回【単純挿入ソート】
単純挿入ソートとは?
左(あるいは右)端からソート済みの区間がどんどん広がっていくというイメージでとらえる。
ソート済みの値より小さいものがあったら、それを挿入するために、
その値より大きい挿入済みの配列を1個ずつずらすやり方。
// 単純挿入ソート。最悪計算量O(n^2)。ループ回数から考えるとまあわかる。 insersionSort: function(data) { // 最初から最後までソート完了になるまで繰り返す var tmp, i; for (var sorted = 0; sorted < data.length - 1; sorted++) { // ソート完了している領域の直後の値を取り出す。 insert = data[sorted+1]; // ソート済みの中で、挿入できる場所があるかを調べる。 for (i = 0; i <= sorted; i++) { if (data[i] > insert) { break; //ずれている部分を記憶しつつ、サーチを止める。 } } // ずれていた箇所まで、1個ずつ要素をずらしていく。 // 最終的にずれていた部分、1つの要素で比べようとすると止まる。 while(i <= sorted + 1) { tmp = data[i]; data[i] = insert; insert = tmp; i++; } } return data; }