×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。


よく使う処理 :  桁分離ポインタ| ソート| 探索


ソート

いくつかの数値データを値の高い順(降順)に、または低い順(昇順)に並べ替える処理。並べ替える手順はクイックソート、マージソート、ヒープソートなど色々ありますが、ここでは一番わかりやすいと思われるバブルソートについて記します。

バブルソート
まず、並べ替える数値は列になって並んでいるものと考えます。次に、隣り合う数値同士を比較して大きければ(または小さければ)その数値同士を入れ替えます。この比較と入れ替えの処理を繰り返して整列します。

例:1,4,3,5,7,6,2,8という8つの数値を降順に並べ替える場合

以下の表のように並べ替えていきます。表において灰色で示した欄の数値が、比較する数値です。比較する数値は1つずつずらしていきます。この例では降順に並べ替えるので、比較して大きい方の数値を上に持ってきます。例えば、1巡目の比較1回目では

@1つ目と2つ目の数値を比較
A2つ目の方が大きいので1つ目と入れ替える
B比較する数値をずらす

という具合になり、以下同様に比較・入れ替えを最後の数値まで繰り返します。

<比較・入れ替え 1巡目>
比較1回目比較2回目比較3回目比較4回目比較5回目比較6回目比較7回目1巡目結果
14444444
41333333
33155555
55517777
77771666
66666122
22222218
88888881

<比較・入れ替え 2巡目>
比較1回目比較2回目比較3回目比較4回目比較5回目比較6回目比較7回目2巡目結果
44444444
33555555
55377777
77736666
66663333
22222288
88888822
11111111

<比較・入れ替え 3巡目>
比較1回目比較2回目比較3回目比較4回目比較5回目比較6回目比較7回目3巡目結果
45555555
54777777
77466666
66644444
33333888
88888333
22222222
11111111

<比較・入れ替え 4巡目>〜 省略

3巡目でやっと3,2,1という並びが見えました。4巡目以降も同様に比較・入れ替えを行うと何巡目かに整列が完了します。このバブルソートでは、並べ替えたい数値の個数をnとすると、必要な巡回数は最大でn-1となります。

実際にイベントとして記述する際は、並べ替えが(n-1)巡未満で完了するとは限らないので、(n-1)巡することになります。記述の構造としては繰り返し処理の中に繰り返し処理が1つあり、内側の繰り返しで比較・入れ替えを7(=n-1)回行い、外側の繰り返しでは内側の繰り返しを7(=n-1)回繰り返します。


ホームtkool2 → よく使う処理:ソート