バブルソート(Bubble Sort)
バブルソートとは、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。
最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易で、並列処理との親和性が高い。
バブルソートとは下の図のように処理を進めていく。
- 隣り合う要素を比較し、入れ替えを行う
- これを最後の要素まで繰り返す(一番大きな値が末尾に来ることになる)
- 再び、隣り合う要素を比較し、入れ替えを行う
- このとき、最後に比較する要素の位置を1つ左にずらす
- 末尾の要素は、1回目の入れ替えで一番大きな値になっているので、比較する必要がない
- これを繰り返す
バブルソート(Bubble Sort)をRubyで実装
def bubble_sort(ary) len = ary.length len.times do |i| # 比較する位置を1つずつ左にずらすため、「- i」している (len - 1 - i).times do |j| if ary[j] > ary[j + 1] ary[j], ary[j + 1] = ary[j + 1], ary[j] end end end return ary end numbers = Array.new(10) { rand 100 } p(bubble_sort(numbers))
バブルソート(Bubble Sort)をGo言語で実装
package main import ( "fmt" "math/rand" "time" ) func main() { numbers := generateRandomNumbers(10) fmt.Println(bubbleSort(numbers)) } func generateRandomNumbers(size int) []int { rand.Seed(time.Now().UnixNano()) numbers := make([]int, 0, size) for i := 0; i < size; i++ { numbers = append(numbers, rand.Intn(100)) } return numbers } func bubbleSort(numbers []int) []int { count := len(numbers) for i := 0; i < count; i++ { for j := 0; j < (count - 1 - i); j++ { if numbers[j] > numbers[j+1] { numbers[j], numbers[j+1] = numbers[j+1], numbers[j] } } } return numbers }