#10/20 Sorting: Bubble Sort [Cracking the Coding Interview Challenges]

#10 Sorting: Bubble Sort

www.hackerrank.com

solution

与えられた数値をバブルソートアルゴリズムを使って昇順にソートし、スワップ回数、ソートの最初と最後を指定のフォーマットで出力する問題。

以下、rubyでの解答。

def bubbleSort(n, elements)
    total = 0
    for i in 0..n-1 do
        swaps = 0
        for j in 0..n-2 do
            if elements[j] > elements[j + 1]
                elements[j], elements[j + 1] = elements[j + 1], elements[j]
                swaps += 1
            end
        end
        break if swaps == 0
        total += swaps
    end
    return total
end

input = $stdin.read.split("\n")
n, ary = input[0].to_i, input[1].split(" ").map(&:to_i)
total = bubbleSort(n, ary)

puts "Array is sorted in #{total} swaps."
puts "First Element: #{ary.first}"
puts "Last Element: #{ary.last}"

github.com

バブルソートとは

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソート - Wikipedia

まとめ

特に特筆すべき点なし