バブルソートやってみたったんごwww
バブルソートってなんやねん
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。
隣り合う要素の大小を比較しながら整列させること。
最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、
また並列処理との親和性が高いことから、しばしば用いられる。
安定な内部ソート。基本交換法、隣接交換法ともいう。
(単に交換法と言う場合もある)
ほぉ。
横同士を比較して整列させるのをバブルソートっていうんか。
メリットは簡単
デメッリトは遅い
シンプルやなぁ。
動作例をみてみる。
初期データ: 8 4 3 7 6 5 2 1
結果が確定した部を太字でしめすと、
4 3 7 6 5 2 1 8 (1回目の外側ループ終了時 交換回数:7)
3 4 6 5 2 1 7 8 (2回目の外側ループ終了時 交換回数:5)
3 4 5 2 1 6 7 8 (3回目の外側ループ終了時 交換回数:3)
3 4 2 1 5 6 7 8 (4回目の外側ループ終了時 交換回数:2)
3 2 1 4 5 6 7 8 (5回目の外側ループ終了時 交換回数:2)
2 1 3 4 5 6 7 8 (6回目の外側ループ終了時 交換回数:2)
1 2 3 4 5 6 7 8 (7回目の外側ループ終了時 交換回数:1)
交換回数の合計:7+5+3+2+2+2+1=22
実際に作ってみた。
<?php
//0~9までの配列を用意
$array = range('0', '9');
//配列の中身をシャッフル
shuffle($array);
//配列の数をカウント
$count = count($array);
// 要素数回繰り返し
for($element = 0; $element < $count; $element++)
{
// 要素数-1繰り返して隣接キーを取得
for($key = 1; $key < $count; $key++)
{
// 隣接要素を比較し大小が逆なら入替える
if($array[$key-1] > $array[$key])
{
$temporary_data = $array[$key];
$array[$key] = $array[$key-1];
$array[$key-1] = $temporary_data;
}
}
}
配列に値を入れるのがめんどくさったから
0-9までの値を指定してみたった。
そのあとソートなのに綺麗に並んでたらソートする意味ないから
シャッフルで配列の値の位置を変更してみたったw
少しハマったのが入れ替え作業
前キーの値が大きければ
後キーの値を一時保存
$temporary_data = $array[$key];
前キーの値を後キーの変数に代入して$array[$key] = $array[$key-1];
後キーを前キーに代入
$array[$key-1] = $temporary_data;
※前キーは$key-1、後キーは$key
まとめ
自分がなにを作ろうとしてるのか
ちゃんとイメージして書かないと途中からわけわからなくなってきたw
特に不等号とかはいるとすぐに混乱してくるw
作ったりやったりすると自分のなにができないところなのかわかる。
なにがわからなかったのかなんでわからなかったのか
ちゃんとそのへん残してなんでわかったのかもかけるようになりたい。