Merge Sort: Counting Inversions in HackerRank

問題

Int型の配列が与えられ、ソートするために必要なスワップの数をカウントするという問題

www.hackerrank.com

解き方

O(N2)の解法

この解法はバブルソートの要領で解く。 forループを2重にしてiを0 ≦ i < arr.length, jをi+1 ≦ j < arr.lengthのようにループさせた時に、arr[i] > arr[j]の条件でカウントしてあげると解ける。

O(NlogN)の解法

この解法はマージソートの要領で解く。 2つの配列をマージさせる時に、左側の配列の値が大きければ、移動させる距離の分だけカウントさせてあげることで、スワップの回数を取得することができる。

ソースコード