バブルソートはわかりやすいソートです。隣どうしを比較して、前の方が値が大きければ値を交換します。それを繰り返し行うことでソートします。ただ、わかりやすく実装も簡単ですが、効率はよくありません。ソートのアルゴリズムとしてはまず使わないのではないでしょうか。アルゴリズム的にもつまらないですね。
バブルソートの名前は、値が泡(バブル)のように上へ登っていくからでしょうね。値が下がっていくようにも実装できますが、せっかくなので名前どおりにしてみました(笑)。
C言語版。
bubble_sort.c
#include <stdio.h> void bubble_sort(int ar[], int len) { int i, j, tmp; for (i = len - 2; i >= 0; i--) for (j = 0; j <= i; j++) if (ar[j] > ar[j + 1]) { tmp = ar[j]; ar[j] = ar[j + 1]; ar[j + 1] = tmp; } } int main () { int ar[] = {3, 1, 5, 2, 9, 7, 0}; int len = sizeof ar / sizeof(int); bubble_sort(ar, len); printf("["); for (int i = 0; i < len; i++) { printf("%d, ", ar[i]); } printf("\b\b]\n"); return 0; }
Go言語版。C の場合とほとんど同じで、工夫の余地はありません。
bubble_sort2.go
package main import "fmt" func bubble_sort(ar []int) []int { for i := len(ar) - 2 ; i >= 0; i-- { for j := 0; j <= i; j++ { if ar[j] > ar[j + 1] { ar[j], ar[j + 1] = ar[j + 1], ar[j] } } } return ar } func main() { fmt.Println(bubble_sort([]int{5, 2, 1, 8, 6, 3, 0})) }
おまけ。Ruby 版。
class Array def bubble_sort (size - 2).downto(0) do |i| (i + 1).times do |j| self[j], self[j + 1] = self[j + 1], self[j] if self[j] > self[j + 1] end end self end end
なお、これらの実装では与えられた配列が破壊的に変更されます。