#12/20 Merge Sort: Counting Inversions [Cracking the Coding Interview Challenges]

#12 Merge Sort: Counting Inversions

www.hackerrank.com

以下のようなインプットが与えられる。

2  
5  
1 1 1 2 2  
5  
2 1 3 1 2
  • 1行目はデータセットの総数
  • 2行目以降はデータセットの総数分だけ以下の入力の繰り返し
    • データの要素の数が整数で与えられる
    • スペース区切りで上記要素の数だけ整数が与えられる

与えられたデータをマージソートし、swapした回数を出力する。 上記のインプットの場合、2個のデータセットが与えられるので、それぞれに対して マージソートを行いswap数を出力する。

0  
4   

solution

以下、rubyでの解。

class Solution

    def initialize(ary)
        @ary = ary
        @swaps = 0
    end

    def mergeSort(ary = @ary)
        return ary if (len = ary.size) <= 1
        ary = ary.clone
        mid = len == 2 ? 1 : len / 2
        list1 = ary.slice(0, mid)
        list2 = ary.slice(mid, len - mid)

        return merge(self.mergeSort(list1), self.mergeSort(list2))
    end

    def getSwaps
        return @swaps
    end

    private
        def merge(list1, list2)
            len1, len2 = list1.size, list2.size
            result = Array.new(len1 + len2)
            a, b, i, j, k = list1[0], list2[0], 0, 0, 0
            loop {
                if a <= b then
                    result[i] = a
                    i += 1
                    j += 1
                    break unless j < len1
                    a = list1[j]
                else
                    # count number of swaps here
                    @swaps += len1 - j
                    result[i] = b
                    i += 1
                    k += 1
                    break unless k < len2
                    b = list2[k]
                end
            }
            while j < len1 do
                result[i] = list1[j]
                i += 1
                j += 1
            end
            while k < len2 do
                result[i] = list2[k]
                i += 1
                k += 1
            end
            return result
        end
end

input = $stdin.read.split("\n")
d = input.shift.to_i
d.times do |v|
    n, ary = input.shift.to_i, input.shift.split(" ").map(&:to_i)
    s = Solution.new(ary)
    s.mergeSort
    puts s.getSwaps
end

github.com

マージソートとは

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする。 (ナイーブな)クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。

マージソート - Wikipedia