バブルソート(C言語、Go言語)

バブルソートはわかりやすいソートです。隣どうしを比較して、前の方が値が大きければ値を交換します。それを繰り返し行うことでソートします。ただ、わかりやすく実装も簡単ですが、効率はよくありません。ソートのアルゴリズムとしてはまず使わないのではないでしょうか。アルゴリズム的にもつまらないですね。

バブルソートの名前は、値が泡(バブル)のように上へ登っていくからでしょうね。値が下がっていくようにも実装できますが、せっかくなので名前どおりにしてみました(笑)。

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