Go言語 Ruby

バブルソート(Bubble Sort)とは?RubyとGo言語で実装

バブルソート(Bubble Sort)

バブルソートとは、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。
最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易で、並列処理との親和性が高い。

バブルソートとは下の図のように処理を進めていく。

  1. 隣り合う要素を比較し、入れ替えを行う
  2. これを最後の要素まで繰り返す(一番大きな値が末尾に来ることになる)
  3. 再び、隣り合う要素を比較し、入れ替えを行う
    • このとき、最後に比較する要素の位置を1つ左にずらす
    • 末尾の要素は、1回目の入れ替えで一番大きな値になっているので、比較する必要がない
  4. これを繰り返す

バブルソート(bubble sort)の処理フロー

バブルソート(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
}

 

-Go言語, Ruby

© 2021 フリエン生活 Powered by AFFINGER5