ちょっとアルゴニズム - Comb Sort(Swift)

Bubble Sortの改良版という位置付けでのようです。Bubble Sortは隣あわせの数字を比較するということで、Comb Sortは隣ではなく、間隔を開けて比較するということです。

あれっと思う人もいると思います。間隔を開けて比べて入れ替える？というのは何か他にもあったぞ。というふうに。

そうなんです、なんと、以下のソートが思い浮かびます。

"Shell Sort"です。このソートアルゴリズムも間隔を開けて、徐々に間を詰めていくという方法で並び替えていきます。

違いは"Shell Sort"では間隔は配列の1/2などに決めて行いますが、Comb Sortは、"1.3"で割ったものを間隔として比較、並び替えをしていきます。

raywenderlich/swift-algorithm-club

while !(index + gap >= copy.count) {
if copy[index] > copy[index + gap] {
copy.swapAt(index, index + gap)
}

少し"swap"のところ修正していますが、

func combSort (input: [Int]) -> [Int] {
   var copy: [Int] = input
   var gap = copy.count
   let shrink = 1.3
   while gap > 1 {
       gap = (Int)(Double(gap) / shrink)
       if gap < 1 {
           gap = 1
       }
   
       var index = 0
       while !(index + gap >= copy.count) {
           if copy[index] > copy[index + gap] {
               copy.swapAt(index, index + gap)
           }
           index += 1
       }
   }
   return copy
}

gap = (Int)(Double(gap) / shrink)

を決めて、

"gap"の数だけ間を開けて大小比較して、必要があれば入れ替え"swap"します。

そしてもう一度、gapをshrink、1.3で割って新しい"gap"でまた同じことを繰り返します。

試して見ます。

var arr = [6,1,4,2]
combSort(input: arr)

とすると、

[1, 2, 4, 6]

とソートされます。