JavaScript講座

並び替え(ソート)

ABCDEF
1num基本交換基本選択基本挿入
10比較回数
11
12交換回数
13
14
input_elements

A2:A9…<input type="number" name="num">

document.getElementsByName('num')

exch_nums
基本交換法用配列
slct_nums
基本選択法用配列
ins_nums
基本挿入法用配列
const exch_nums = [];
const slct_nums = [];
const ins_nums = [];
const input_elements = document.getElementsByName('num');
for(let i=0,j=0;i<input_elements.length;i++){
  if(!isNaN(parseInt(input_elements[i].value))){
    exch_nums[j]=parseInt(input_elements[i].value);
    slct_nums[j]=parseInt(input_elements[i].value);
    ins_nums[j]=parseInt(input_elements[i].value);
    j++;
  }
}
実習用ファイル

ソートのアルゴリズムは多数あるが、今回は基本的なアルゴリズムを取り上げる。

基本交換法

0:3までの配列について最大値確定
num
[0][1][2][3]
4213
  1. [0]
    4
    [1]
    2
    [2][3]
    13
    比較[0]:4 > [1]:2
  2. [0]
    2
    [1]
    4
    [2][3]
    13
    [0]と[1]の中身を交換する
  3. [0]
    2
    [1]
    4
    [2]
    1
    [3]
    3
    比較[1]:4 > [2]:1
  4. [0]
    2
    [1]
    1
    [2]
    4
    [3]
    3
    [1]と[2]の中身を交換する
  5. [0][1]
    21
    [2]
    4
    [3]
    3
    比較[2]:4 > [3]:3
  6. [0][1][2][3]
    2134
    [2]と[3]を交換し、number[3]の最大値が確定
0:2までの配列について最大値確定
num
[0][1][2][3]
2134
  1. [0]
    2
    [1]
    1
    [2][3]
    34
    比較[0]:2 > [1]:1
  2. [0]
    1
    [1]
    2
    [2][3]
    34
    [0]と[1]の中身を交換する
  3. [0]
    1
    [1]
    2
    [2]
    3
    [3]
    4
    比較[1]:2 < [2]:3
  4. [0][1][2][3]
    1234
    number[2]の最大値が確定
0:1までの配列について最大値確定
num
[0][1][2][3]
1234
  1. [0][1][2][3]
    1234
    比較[1]:1 < [2]:2
  2. [0][1][2][3]
    1234
    number[1]の最大値が確定
ソート終わり
num
[0][1][2][3]
1234 
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]
4213
  1. [0]
    4
    [1][2]
    21
    [3]
    3
    比較[0]:4 > [3]:3
  2. [0]
    3
    [1][2]
    21
    [3]
    4
    [0]と[3]の中身を交換する
  3. [0]
    3
    [1]
    2
    [2]
    1
    [3]
    4
    比較[1]:2 < [3]:4
  4. [0][1]
    32
    [2]
    1
    [3]
    4
    比較[2]:1 < [3]:4
  5. [0][1][2][3]
    3214
    number[3]の最大値が確定
0:2までの配列について最大値確定
num
[0][1][2][3]
3214
  1. [0]
    3
    [1]
    2
    [2]
    1
    [3]
    4
    比較[0]:3 > [3]:1
  2. [0]
    1
    [1]
    2
    [2]
    3
    [3]
    4
    [0]と[2]の中身を交換する
  3. [0]
    1
    [1]
    2
    [2]
    3
    [3]
    4
    比較[0]:1 <[3]:3
  4. [0][1][2][3]
    1234
    number[2]の最大値が確定
0:1までの配列について最大値確定
num
[0][1][2][3]
1234
  1. [0]
    1
    [1]
    2
    [2][3]
    34
    比較[0]:1 <[1]:2
  2. num
    [0][1][2][3]
    1234
    number[1]の最大値が確定
ソート終わり
num
[0][1][2][3]
1234
  • 最大値確定までに交換回数を削減できる。
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]
4213
  1. [0]
    4
    [1]
    2
    [2][3]
    13
    比較[0]:4 > [1]:2
  2. [0]
    2
    [1]
    4
    [2][3]
    13
    [1]と[0]の中身を交換する
[2]までの配列について部分ソート
num
[0][1][2][3]
2413
  • [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]
    43
    比較[0]:2 > [1]:1
  • [0]
    1
    [1]
    2
    [2][3]
    43
    [1]と[0]の中身を交換する
[3]までの範囲について部分ソート
num
[0][1][2][3]
1243
  • [0][1]
    12
    [2]
    4
    [3]
    3
    比較[2]:4 > [3]:3
  • [0][1]
    12
    [2]
    3
    [3]
    4
    [2]と[3]の中身を交換する
  • [0]
    1
    [1]
    2
    [2]
    3
    [3]
    4
    比較[1]:2 < [2]:3
  • [0][1][2][3]
    1234
    交換がないのでこの時点で部分ソート終了
ソート終わり
num
[0][1][2][3]
1234
  • 入れ替えがなかった時点でループを抜けられる→比較回数を削減できる。
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;
    }
  }
}