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

Insertion Sort(挿入ソート)の進化版です。

1 　ある間隔をあけた数字に対して比較します。
2 　必要であれば入れ替えます。
3 　比較した数字の間隔を小さくします。

1,2,3の繰り返しで、間隔がなくなれば終了です。

シェルソート : アルゴリズム

参考コードです。

func shellSort(arr: inout [Int]) -> [Int] {
  guard arr.count > 0 else { return arr }
  var gap = arr.count / 2
  while gap > 0 {
      for i in 0 ..< arr.count {
          var j = i + gap
          while j >= gap && j < arr.count {
              guard arr[j] < arr[j - gap] else { break }
              arr.swapAt(j, j - gap)
              j -= gap
          }
      }
      gap /= 2
  }
  return arr
}

"arr.swapAt()"を使って数値の入換えをしているところです。

次にinsertionSortと組み合わせてあるコードです。

tubackkhoa/swift3-algorithm

上記サイトを実行したところエラーが出たため少し修正させてもらいました。

insertionSort()

func insertionSort( list: inout [Int], start: Int, gap: Int) {
   for i in stride(from:start + gap ,to: list.count, by: gap) {
   let currentValue = list[i]
   var pos = i
   while pos >= gap && list[pos - gap] > currentValue {
     list[pos] = list[pos - gap]
     pos -= gap
   }
   list[pos] = currentValue
 }
}

for i in stride(from:start + gap ,to: list.count, by: gap)

で間隔(gap)をあけた数字を取得してリストの並び替えを行います。

shellSort()

func shellSort(_ list: inout [Int]) {
   var sublistCount = list.count / 2
   while sublistCount > 0 {
       for pos in 0..<sublistCount {
           insertionSort(list: &list, start: pos, gap: sublistCount)
       }
       sublistCount = sublistCount / 2
   }
}

var sublistCount = list.count / 2

で配列を分ける間隔を決めます。この場合配列の半分のインデックスを取得しています。

あとはinsertionSort()で順番を入換えて順番にします。

間隔を減らしていき、間隔がなくなったところで終わりとなります。

シェルソート | Programming Place Plus　アルゴリズムとデータ構造編【整列アルゴリズム】　第５章

このサイトわかりやすいです。