並び替え(ソート)
- 実習用ファイル
ソートのアルゴリズムは多数あるが、今回は基本的なアルゴリズムを取り上げる。
基本交換法
- 0:3までの配列について最大値確定
-
num [0] [1] [2] [3] 4 2 1 3 -
[0] 4 [1] 2 [2] [3] 1 3 比較[0]:4 > [1]:2 -
[0] 2 [1] 4 [2] [3] 1 3 [0]と[1]の中身を交換する -
[0] 2 [1] 4 [2] 1 [3] 3 比較[1]:4 > [2]:1 -
[0] 2 [1] 1 [2] 4 [3] 3 [1]と[2]の中身を交換する -
[0] [1] 2 1 [2] 4 [3] 3 比較[2]:4 > [3]:3 -
[0] [1] [2] [3] 2 1 3 4 [2]と[3]を交換し、number[3]の最大値が確定
-
- 0:2までの配列について最大値確定
-
num [0] [1] [2] [3] 2 1 3 4 -
[0] 2 [1] 1 [2] [3] 3 4 比較[0]:2 > [1]:1 -
[0] 1 [1] 2 [2] [3] 3 4 [0]と[1]の中身を交換する -
[0] 1 [1] 2 [2] 3 [3] 4 比較[1]:2 < [2]:3 -
[0] [1] [2] [3] 1 2 3 4 number[2]の最大値が確定
-
- 0:1までの配列について最大値確定
-
num [0] [1] [2] [3] 1 2 3 4 -
[0] [1] [2] [3] 1 2 3 4 比較[1]:1 < [2]:2 -
[0] [1] [2] [3] 1 2 3 4 number[1]の最大値が確定
-
- ソート終わり
-
num [0] [1] [2] [3] 1 2 3 4
for(let end=exch_nums.length-1;end>0; end--){ for(let n=0; n<end; n++){ if(exch_nums[n]>exch_nums[n+1]){ const tmp = exch_nums[n+1]; exch_nums[n+1] = exch_nums[n]; exch_nums[n] = tmp; } } }
基本選択法
- 0:3までの配列について最大値確定
-
num [0] [1] [2] [3] 4 2 1 3 -
[0] 4 [1] [2] 2 1 [3] 3 比較[0]:4 > [3]:3 -
[0] 3 [1] [2] 2 1 [3] 4 [0]と[3]の中身を交換する -
[0] 3 [1] 2 [2] 1 [3] 4 比較[1]:2 < [3]:4 -
[0] [1] 3 2 [2] 1 [3] 4 比較[2]:1 < [3]:4 -
[0] [1] [2] [3] 3 2 1 4 number[3]の最大値が確定
-
- 0:2までの配列について最大値確定
-
num [0] [1] [2] [3] 3 2 1 4 -
[0] 3 [1] 2 [2] 1 [3] 4 比較[0]:3 > [3]:1 -
[0] 1 [1] 2 [2] 3 [3] 4 [0]と[2]の中身を交換する -
[0] 1 [1] 2 [2] 3 [3] 4 比較[0]:1 <[3]:3 -
[0] [1] [2] [3] 1 2 3 4 number[2]の最大値が確定
-
- 0:1までの配列について最大値確定
-
num [0] [1] [2] [3] 1 2 3 4 -
[0] 1 [1] 2 [2] [3] 3 4 比較[0]:1 <[1]:2 -
num [0] [1] [2] [3] 1 2 3 4 number[1]の最大値が確定
-
- ソート終わり
-
num [0] [1] [2] [3] 1 2 3 4
- 最大値確定までに交換回数を削減できる。
for(let end=slct_nums.length-1;end>0;end--){ for(let n=0; n< end; n++){ if(slct_nums[n]>slct_nums[end]){ const tmp = slct_nums[end]; slct_nums[end] = slct_nums[n]; slct_nums[n] = tmp; } } }
基本挿入法
- [1]までの配列について部分ソート
-
num [0] [1] [2] [3] 4 2 1 3 -
[0] 4 [1] 2 [2] [3] 1 3 比較[0]:4 > [1]:2 -
[0] 2 [1] 4 [2] [3] 1 3 [1]と[0]の中身を交換する
-
- [2]までの配列について部分ソート
-
num [0] [1] [2] [3] 2 4 1 3 -
[0] 2 [1] 4 [2] 1 [3] 3 比較[1]:4 > [2]:1 -
[0] 2 [1] 1 [2] 4 [3] 3 [2]と[1]の中身を交換する -
[0] 2 [1] 1 [2] [3] 4 3 比較[0]:2 > [1]:1 -
[0] 1 [1] 2 [2] [3] 4 3 [1]と[0]の中身を交換する- [3]までの範囲について部分ソート
num [0] [1] [2] [3] 1 2 4 3 -
[0] [1] 1 2 [2] 4 [3] 3 比較[2]:4 > [3]:3 -
[0] [1] 1 2 [2] 3 [3] 4 [2]と[3]の中身を交換する -
[0] 1 [1] 2 [2] 3 [3] 4 比較[1]:2 < [2]:3 -
[0] [1] [2] [3] 1 2 3 4 交換がないのでこの時点で部分ソート終了- ソート終わり
num [0] [1] [2] [3] 1 2 3 4 - 入れ替えがなかった時点でループを抜けられる→比較回数を削減できる。
for(let unsorted=1;unsorted<ins_nums.length;unsorted++){ for(let target=unsorted;target>0;target--){ if(ins_nums[sorted-1]>ins_nums[target]){ const tmp = ins_nums[target-1]; ins_nums[target-1] = ins_nums[target]; ins_nums[target] = tmp; }else{ break; } } }
-