■ バブルソート
隣り合う2つのデータを比較して、前の要素の方が大きかった場合、後ろの要素と交換する。
このアクションを先頭から順に繰り返すことで、要素を整列させるソート方法。
小さい要素が泡のように上がってくることから、こう名付けられた。
バブルソートは要素の数が小さいときは良いが、要素の数が大きくなればなるほど処理速度が遅くなる性質を持つ。
(例)[2,3,1,5,4] → [2,1,3,5,4] → [2,1,3,4,5] → [1,2,3,4,5]
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 // データ件数の定義 int sort[N]; // 数値を格納する配列 // バブルソートを行う関数 void BubbleSort(void) { int i, j, flag; do { flag = 0; for (i = 0; i < N-1; i++) { // 先頭から順に見ていって if (sort[i] > sort[i+1]) { // 左右の並びがおかしければ、入れ替える flag = 1; // 並び替えが行われた場合、flagに1を代入する j = sort[i]; // sort[i]の値を変数jに sort[i] = sort[i+1]; // sort[i+1]の値をsort[i]に sort[i+1] = j; // さっき変数jに入れた値をsort[i+1]に } } // flagの値が0の場合、一度もソートが行なわれなかったことになる → ソート完了 } while(flag == 1); } int main(void) { int i; srand((unsigned int)time(NULL)); // 謎 printf("ソート準備\n"); // 配列にランダムな値を格納 for (i = 0; i < N; i++) { sort[i] = rand(); // 乱数の生成と代入 printf("%d\n", sort[i]); } printf("\nソート開始!\n"); BubbleSort(); // バブルソート関数の実行 printf("\nソート終了:\n"); // ソート結果を出力 for (i = 0; i < N; i++) { printf("%d\n", sort[i]); } // 終了?? EIXT_SUCCESSはよく知らない return EXIT_SUCCESS; }
上述の通り、サンプルコードはC言語で書かれていたが、学習のため、Rubyで書きなおした。
# coding: utf-8 N = 10 # 配列の数 data = Array.new(N) def bubble_sort(data) loop do flag = 0 # 並び替えが起こったか否かの検証 j = 0 while N-1 > j do if data[j] > data[j+1] flag = 1 tmp = data[j] data[j] = data[j+1] data[j+1] = tmp end j = j + 1 end return data if flag == 0 end end puts "ソート準備!" # 乱数を生成して配列に格納する i = 0 while N > i do data[i] = rand(10000000) i = i + 1 end # 生成した配列を出力 data.each do |d| puts d end puts "ソート開始....." # ソート(bubble_sortメソッドの呼び出し) data2 = bubble_sort(data) data2.each do |d| puts d end puts "ソート終了!"