HSP3 プログラミングの基礎�W

☆ 直接選択法　　☆ 単純選択法　　☆ バブルソート法　　☆ 単純挿入法

並べ替え(sort : ソート)

☆ 直接選択法（昇順の場合）

データの並びの先頭(0番)と2つ目(1番)以降のデータとを順番に比較し、先頭(0番)のデータの方が大きければデータを入れ替える。すべての比較が終わった時点で先頭(0番)には最も小さいデータが格納されていることになる。これで、先頭(0番)のデータは確定である。 　( )内の数字は配列の添え字である。
次に、2つ目(1番)と3つ目(2番)以降のデータとを順番に比較し、2つ目(1番)のデータの方が大きければデータを入れ替える。すべての比較が終わった時点で2つ目(1番)には2つ目以降のデータの中で最も小さいデータが格納されていることになる。これで、2つ目(1番)のデータは確定である。
以降、3つ目(2番)と4つ目(3番)以降のデータ、4つ目(3番)と5つ目(4番)以降のデータ、…、8つ目(7番)と9つ目(8番)以降のデータとを順番に比較してデータを入れ替えていく。
最後に、9つ目(8番)と10個目(9番)のデータを比較してデータを入れ替えていく。

　左表のように、配列の○番と△番の値を比較していく。
　○番は、0, 1, 2, 3, 4, 5, 6, 7, 8 と変化していく。repeat命令の繰り返し回数は、「配列の個数−１」である。システム変数cntの値が使える。
　△番は、○＋１, …, 9 と変化していく。repeat命令の繰り返し回数は、「配列の個数−（○＋１）」である。システム変数cntの値は○＋１で初期化して使う。
 

　次のプログラムは、先頭と2番目以降のデータ、2番目と3番目以降のデータ、…を比較した結果を表示するサンプルである。

#define global swap(%1, %2) _wk = %1 : %1 = %2 : %2 = _wk
#module
#deffunc hyouji array dd
    data1 = ""
    foreach dd
        data1 = data1 + "[" + dd(cnt) + "] "
    loop
    mes data1
    return
#deffunc sort_num array dd, int flag
;
;sort_num  配列変数
;  flag=0:昇順、1:降順
;  直接選択法によるソートである。配列変数の内容が書き換えられる。
;
    repeat length(dd) - 1
        d1 = cnt
        repeat length(dd) - (d1 + 1), d1 + 1
            if flag = 0 & dd(d1) > dd(cnt) : swap dd(d1), dd(cnt)    ;昇順
            if flag = 1 & dd(d1) < dd(cnt) : swap dd(d1), dd(cnt)    ;降順
        loop
        hyouji dd    ;途中経過表示用
    loop
    return
#global
;main
    dim data, 10
    sdim data1
    data = 4, 2, 8, 6, 1, 10, 7, 9, 3, 5
    mes "元のデータ"
    hyouji data
;
    mes "ソート途中経過"
    sort_num data, 0
    mes "ソート結果"
    hyouji data
    stop

昇順

降順

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [1] [4] [8] [6] [2] [10] [7] [9] [3] [5] [1] [2] [8] [6] [4] [10] [7] [9] [3] [5] [1] [2] [3] [8] [6] [10] [7] [9] [4] [5] [1] [2] [3] [4] [8] [10] [7] [9] [6] [5] [1] [2] [3] [4] [5] [10] [8] [9] [7] [6] [1] [2] [3] [4] [5] [6] [10] [9] [8] [7] [1] [2] [3] [4] [5] [6] [7] [10] [9] [8] [1] [2] [3] [4] [5] [6] [7] [8] [10] [9] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ソート結果 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [10] [2] [4] [6] [1] [8] [7] [9] [3] [5] [10] [9] [2] [4] [1] [6] [7] [8] [3] [5] [10] [9] [8] [2] [1] [4] [6] [7] [3] [5] [10] [9] [8] [7] [1] [2] [4] [6] [3] [5] [10] [9] [8] [7] [6] [1] [2] [4] [3] [5] [10] [9] [8] [7] [6] [5] [1] [2] [3] [4] [10] [9] [8] [7] [6] [5] [4] [1] [2] [3] [10] [9] [8] [7] [6] [5] [4] [3] [1] [2] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1] ソートの結果 [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

☆ 単純選択法（昇順の場合）

　直接選択法と同じように比較していく。ただし、より小さい値が見つかったときに入れ替えるのではなく、より小さい値が格納された配列の番号（添字）を記憶しておき最後に値を入れ替える。

[1]	[2]
[3]	[4]

#define global swap(%1, %2) _wk = %1 : %1 = %2 : %2 = _wk
#module
#deffunc hyouji array dd
    data1 = ""
    foreach dd
        data1 = data1 + "[" + dd(cnt) + "] "
    loop
    mes data1
    return
#deffunc sort_num array dd, int flag
;
;sort_num  配列変数
;  flag=0:昇順、1:降順
;  単純選択法によるソートである。配列変数の内容が書き換えられる。
;
    repeat length(dd) - 1
        d1 = cnt
        minmax = d1
        repeat length(dd) - (d1 + 1), d1 + 1
            if flag = 0 & dd(minmax) > dd(cnt) : minmax = cnt    ;昇順
            if flag = 1 & dd(minmax) < dd(cnt) : minmax = cnt    ;降順
        loop
        swap dd(d1), dd(minmax)
        hyouji dd    ;途中経過表示用
    loop
    return
#global
;main
    dim data, 10
    sdim data1
    data = 4, 2, 8, 6, 1, 10, 7, 9, 3, 5
    mes "元のデータ"
    hyouji data
;
    mes "ソート途中経過"
    sort_num data, 0
    mes "ソート結果"
    hyouji data
    stop

昇順

降順

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [1] [2] [8] [6] [4] [10] [7] [9] [3] [5] [1] [2] [8] [6] [4] [10] [7] [9] [3] [5] [1] [2] [3] [6] [4] [10] [7] [9] [8] [5] [1] [2] [3] [4] [6] [10] [7] [9] [8] [5] [1] [2] [3] [4] [5] [10] [7] [9] [8] [6] [1] [2] [3] [4] [5] [6] [7] [9] [8] [10] [1] [2] [3] [4] [5] [6] [7] [9] [8] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ソートの結果 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [10] [2] [8] [6] [1] [4] [7] [9] [3] [5] [10] [9] [8] [6] [1] [4] [7] [2] [3] [5] [10] [9] [8] [6] [1] [4] [7] [2] [3] [5] [10] [9] [8] [7] [1] [4] [6] [2] [3] [5] [10] [9] [8] [7] [6] [4] [1] [2] [3] [5] [10] [9] [8] [7] [6] [5] [1] [2] [3] [4] [10] [9] [8] [7] [6] [5] [4] [2] [3] [1] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1] ソートの結果 [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

　より小さい値が見つかるたびにswapで交換するのではなく、その小さい値の番号（添字）だけを記憶しておくので、直接選択法より、こちらの単純選択法の方が処理は速くなる。

☆ バブルソート法（昇順の場合）

　隣同士のデータを比較していき、大きければ入れ替える処理を繰り返す。大きい値がどんどんと（配列番号の）後ろへ下がっていく。縦向きにしてみると大きい値である泡（バブル）が上がっていくように見える。

[1] 　(0)から(9)まで、隣同士を比較する。	[2] 　(0)から(8)まで、隣同士を比較する。
[3] 　(0)から(7)まで、隣同士を比較する。	[4] 　(0)から(6)まで、隣同士を比較する。

#define global swap(%1, %2) _wk = %1 : %1 = %2 : %2 = _wk
#module
#deffunc hyouji array dd
    data1 = ""
    foreach dd
        data1 = data1 + "[" + dd(cnt) + "] "
    loop
    mes data1
    return
#deffunc sort_num array dd, int flag
;
;sort_num  配列変数
;  flag=0:昇順、1:降順
;  バブルソート法によるソートである。配列変数の内容が書き換えられる。
;
    repeat length(dd) - 1
        d1 = cnt
        repeat length(dd) - (d1 + 1)
            if flag = 0 & dd(cnt) > dd(cnt + 1) : swap dd(cnt), dd(cnt + 1)    ;昇順
            if flag = 1 & dd(cnt) < dd(cnt + 1) : swap dd(cnt), dd(cnt + 1)    ;降順
        loop
        hyouji dd    ;途中経過表示用
    loop
    return
#global
;main
    dim data, 10
    sdim data1
    data = 4, 2, 8, 6, 1, 10, 7, 9, 3, 5
    mes "元のデータ"
    hyouji data
;
    mes "ソート途中経過"
    sort_num data, 0
    mes "ソート結果"
    hyouji data
    stop

昇順

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [2] [4] [6] [1] [8] [7] [9] [3] [5] [10] [2] [4] [1] [6] [7] [8] [3] [5] [9] [10] [2] [1] [4] [6] [7] [3] [5] [8] [9] [10] [1] [2] [4] [6] [3] [5] [7] [8] [9] [10] [1] [2] [4] [3] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ソート結果 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

　実行結果をよく見ると、処理の途中で並べ替えが完了している。最後までトレースするとわかるが、並べ替えが完了すると入れ替えが起こらなくなる。そこで、入れ替えがなくなった時点でループを抜け出すように変更すると次のようにプログラムすることができる。

#define global swap(%1, %2) _wk = %1 : %1 = %2 : %2 = _wk
#module
#deffunc hyouji array dd
    data1 = ""
    foreach dd
        data1 = data1 + "[" + dd(cnt) + "] "
    loop
    mes data1
    return
#deffunc sort_num array dd, int flag
;
;sort_num  配列変数
;  flag=0:昇順、1:降順
;  バブルソート法によるソートである。配列変数の内容が書き換えられる。
;
    repeat length(dd) - 1
        d1 = cnt
        owari = 1    ;入れ替え有無のフラグ
        repeat length(dd) - (d1 + 1)
            if flag = 0 & dd(cnt) > dd(cnt + 1) : swap dd(cnt), dd(cnt + 1) : owari = 0    ;昇順
            if flag = 1 & dd(cnt) < dd(cnt + 1) : swap dd(cnt), dd(cnt + 1) : owari = 0    ;降順
        loop
        hyouji dd    ;途中経過表示用
        if owari = 1 : break    ;入れ替えなしでループを抜け出す。
    loop
    return
#global
;main
    dim data, 10
    sdim data1
    data = 4, 2, 8, 6, 1, 10, 7, 9, 3, 5
    mes "元のデータ"
    hyouji data
;
    mes "ソート途中経過"
    sort_num data, 0
    mes "ソート結果"
    hyouji data
    stop

昇順

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [2] [4] [6] [1] [8] [7] [9] [3] [5] [10] [2] [4] [1] [6] [7] [8] [3] [5] [9] [10] [2] [1] [4] [6] [7] [3] [5] [8] [9] [10] [1] [2] [4] [6] [3] [5] [7] [8] [9] [10] [1] [2] [4] [3] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ソート結果 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

　昇順の実行結果を比べると途中経過の行数、すなわち繰り返し回数が減っているのがわかる。

☆ 単純挿入法（昇順の場合）

　先頭(0番)のデータは、まず確定とする。次(1番)のデータとこのデータより前にあるデータと比較していき、大きければ後ろへずらし、小さければ一つ前の場所に格納する。このようにデータの入る場所を探して、その場所に挿入していく形なので単純挿入法という。

[1] 1番をdxに格納。 dxと0番を比較。0番が大きいのでずらす。 0番より前はないので0番にdxを挿入。	[2] 2番をdxに格納。 dxと1番を比較。dxが大きいので、dxを(1+1)番に挿入。
[3] 3番をdxに格納。 dxと2番を比較。2番が大きいのでずらす。 dxと1番を比較。dxが大きいので、dxを(1+1)番に挿入。	[4] 4番をdxに格納。 dxと3番を比較。3番が大きいのでずらす。 　　…　…　… dxと0番を比較。0番が大きいのでずらす。 0番より前はないので0番にdxを挿入。
[5] 5番をdxに格納。 dxと4番を比較。dxが大きいので、dxを(4+1)番に挿入。	[6] 6番をdxに格納。 dxと5番を比較。5番が大きいのでずらす。 dxと4番を比較。4番が大きいのでずらす。 dxと3番を比較。dxが大きいので、dxを(3+1)番に挿入。
[7] 7番をdxに格納。 dxと6番を比較。6番が大きいのでずらす。 dxと5番を比較。dxが大きいので、dxを(5+1)番に挿入。	[8] 8番をdxに格納。 dxと7番を比較。7番が大きいのでずらす。 　　…　…　… dxと2番を比較。2番が大きいのでずらす。 dxと1番を比較。dxが大きいので、dxを(1+1)番に挿入。
[9] 9番をdxに格納。 dxと8番を比較。8番が大きいのでずらす。 　　…　…　… dxと4番を比較。4番が大きいのでずらす。 dxと3番を比較。dxが大きいので、dxを(3+1)番に挿入。	すべてのデータについて処理が終わったので、 これでソート完了である。

#define global swap(%1, %2) _wk = %1 : %1 = %2 : %2 = _wk
#module
#deffunc hyouji array dd
    data1 = ""
    foreach dd
        data1 = data1 + "[" + dd(cnt) + "] "
    loop
    mes data1
    return
#deffunc sort_num array dd, int flag
;
;sort_num  配列変数
;  flag=0:昇順、1:降順
;  単純挿入法によるソートである。配列変数の内容が書き換えられる。
;
    repeat length(dd) - 1, 1
        d1 = cnt
        dx = dd(d1)
        repeat d1, 1
            d2 = d1 - cnt
            if (flag = 0 & dd(d2) > dx) or (flag = 1 & dd(d2) < dx) {
                dd(d2 + 1) = dd(d2)
            } else {
                d2 = d2 + 1
                break
            }
        loop
        dd(d2) = dx
        hyouji dd    ;途中経過表示用
    loop
    return
#global
;main
    dim data, 10
    sdim data1
    data = 4, 2, 8, 6, 1, 10, 7, 9, 3, 5
    mes "元のデータ"
    hyouji data
;
    sort_num data, 0
    mes "ソート結果"
    hyouji data
    sort_num data, 1
    mes "ソート結果"
    hyouji data
    stop

昇順

降順

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [2] [4] [8] [6] [1] [10] [7] [9] [3] [5] [2] [4] [8] [6] [1] [10] [7] [9] [3] [5] [2] [4] [6] [8] [1] [10] [7] [9] [3] [5] [1] [2] [4] [6] [8] [10] [7] [9] [3] [5] [1] [2] [4] [6] [8] [10] [7] [9] [3] [5] [1] [2] [4] [6] [7] [8] [10] [9] [3] [5] [1] [2] [4] [6] [7] [8] [9] [10] [3] [5] [1] [2] [3] [4] [6] [7] [8] [9] [10] [5] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ソート結果 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

元のデータ [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] ソート途中経過 [4] [2] [8] [6] [1] [10] [7] [9] [3] [5] [8] [4] [2] [6] [1] [10] [7] [9] [3] [5] [8] [6] [4] [2] [1] [10] [7] [9] [3] [5] [8] [6] [4] [2] [1] [10] [7] [9] [3] [5] [10] [8] [6] [4] [2] [1] [7] [9] [3] [5] [10] [8] [7] [6] [4] [2] [1] [9] [3] [5] [10] [9] [8] [7] [6] [4] [2] [1] [3] [5] [10] [9] [8] [7] [6] [4] [3] [2] [1] [5] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1] ソート結果 [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

2006  © Hiroshi Masuda