『アルゴリズムとデータ構造』学習ノート：バブルソート

■ バブルソート
隣り合う２つのデータを比較して、前の要素の方が大きかった場合、後ろの要素と交換する。
このアクションを先頭から順に繰り返すことで、要素を整列させるソート方法。
小さい要素が泡のように上がってくることから、こう名付けられた。
バブルソートは要素の数が小さいときは良いが、要素の数が大きくなればなるほど処理速度が遅くなる性質を持つ。
（例）[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 "ソート終了！"