Sort/Bubble

バブルソート †

[編集]

ソートの中でも、一番直感的でわかりやすいソートです。
安定なソートですが、ソート時間はデータ量の２乗に比例します

データを昇順ソートする場合・・・

まず、１番目と２番目のデータを比較します。
１番目のデータのほうが大きければ、１番目と２番目を入れ替えます。
次に、２番目と３番目のデータを比較します。
２番目のデータのほうが大きければ、２番目と３番目を入れ替えます。
次に、３番目と４番目のデータを比較します。
３番目のデータのほうが大きければ、３番目と４番目を入れ替えます。

このとき、４番目のデータは必ず一番大きな数字になっているので
次は、４番目のデータを調べずに、同じことを繰り返します。

１番目と２番目のデータを比較します。
１番目のデータのほうが大きければ、１番目と２番目を入れ替えます。
次に、２番目と３番目のデータを比較します。
２番目のデータのほうが大きければ、２番目と３番目を入れ替えます。

同じように、３番目のデータは４番目より小さい一番大きな数字になっているので、
３番目のデータを調べずに、もう一度同じことをします。

１番目と２番目のデータを比較します。
１番目のデータのほうが大きければ、１番目と２番目を入れ替えます。

これで、ソート完了です。

例えば、

というデータをソートする場合、

１回目	4	2	1	3
	2	4	1	3
	2	1	4	3
	2	1	3	4

２回目	1	2	3	4
	1	2	3	4
	1	2	3	4

３回目	1	2	3	4
３回目	1	2	3	4

のようになります。ソートが必要ない場合も、比較してしまいます・・・

実装例

// 入れるデータ数
dim rando,80
randomize
// 適当なデータを入れる
// rando=2,4,1,3,5,12,19,6,13,8,7,18,16,9,17,0,15,14,11,10
repeat length(rando)
    rando(cnt)  = rnd(length(rando))
loop
 
// ソート前のデータをコピーしておく
notesel buf2
repeat length(rando)
    noteadd "rando("+cnt+") = "+rando(cnt),-1
loop
 
// バブルソート
repeat length(rando)-1
    repeat length(rando)-1-i
        // 比較のため一時的にデータを取り出す
        d1=rando(cnt) : d2=rando(cnt+1)
 
        // データを比較して大きい場合入れ替え
        // 降順の場合は小さいときに入れ替える
        if d1>d2 : rando(cnt)=d2 : rando(cnt+1)=d1
    loop
    i++
loop
 
// 整形
notesel buf
repeat length(rando)
    noteadd "rando("+cnt+") = "+rando(cnt),-1
loop
 
// データを表示する
title "バブルソートの例"
    objmode 1
    sysfont 17
    pos   2, 4 : mes "ソート前"
    pos 312, 4 : mes "ソート後"
    pos   0,20 : mesbox buf2,300,300,0
    pos 310,20 : mesbox  buf,300,300,0
stop

先ほど実行してみたところ、時々同じ数字が並んでいることがあります「 -- アキス 2007-05-14 (月) 09:04:29
状況がわからないけれど勘違いしていませんか?データ群に同じ値が複数あったならソート後はその値が連続して並びます。
例えば以下のようなデータを昇順でソートすれば
```
3, 2, 3, 1, 2, 3, 2, 1, 3
```
次のように並び換えられます。
```
1, 1, 2, 2, 2, 3, 3, 3, 3
```
-- naznyark? 2007-05-15 (火) 01:43:24

お名前:

OFFICIAL/関連

TUTORIAL

TOPICS

ETC

EDIT

REFERENCE

LOG

お知らせ

HSP Web-Ring

最新の40件

バブルソート †