Swiftで学ぶソートアルゴリズム入門

バブルソート

隣り合う要素の大小を比べてソートする方法

余談⚡️バブルソートは実装が簡単だが計算量が多い重い処理である。
このことで話題になったオバマ元大統領の話エピソードがあります笑
良かったら読んでみてください。
https://plusblog.jp/6597/

選択ソート

バブルソートの改良。配列の最小、もしくは最大の要素を見つけ出し、それを先頭に持ってくるという一連の処理を繰り返しすることでソートしていく方法。

挿入ソート

未整列の要素を一つずつ、整列済みの列の適切な位置に挿入していく方法。

マージソート

配列を2分割するのを繰り返し、要素数が1になるまで細かくして、要素同士を比較しながら戻していく方法。

クイックソート

名前の通り、データの比較、交換回数が他のものと比べて少なく計算量が少ない。
ある基準値（pivot）を決めて、その基準値から小さいグループ、大きいグループ分割していくのを再帰的に実行しソートする方法

Swiftで書いてみる

bubbleSort.swift

class BubbleSort {
    func sort(_ array: [Int]) -> [Int] {
        var arr = array
        let n = arr.count
        for i in 0..<n-1 {
            for j in 0..<n-i-1 {
                if arr[j] > arr[j+1] {
                    // 大小を比較して入れ替える
                    let temp = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = temp
                }
            }
        }
        return arr
    }
}

SelectionSort.swift

class SelectionSort {
func selectionSort(_ array: [Int]) -> [Int] {
  if array.count <= 1 else { return array }
  var aｒｒ = array                    // 引数の配列を変数に入れて
  for x in 0 ..<aｒｒ.count - 1 {     // 長さの数だけFor文
    var lowest = x
    for y in x + 1 ..<aｒｒ.count {   // インデックス番号がXより先の要素をみていく
      if aｒｒ[y] < aｒｒ[lowest] {
        lowest = y　 //lowestを更新していく
      }
    }

    if x != lowest {               // もしxがLowestでなければ実際に配列の要素同士を入れ替える。
      aｒｒ.swapAt(x, lowest)
    }
  }
  return aｒｒ
}
}

InsertionSort.swift

class InsertionSort {
 func insertionSort(_ array: [Int]) -> [Int] {
    var sortedArray = array          // 引数の配列を変数に入れる。
    for index in 1..<sortedArray.count {         // 配列の長さ分、for分で繰り返し。
        var currentIndex = index //現在追っているindexを変数に入れてCurrentIndexを更新する
// CurrentIndexが　0より大きく、 配列[currentIndex] < 配列[currentIndex - 1]であるかぎり入れ替え続ける。
        while currentIndex > 0 && sortedArray[currentIndex] < sortedArray[currentIndex - 1] { 
           //SwapAtは指定したインデックス番号の要素を入れ替える
            sortedArray.swapAt(currentIndex - 1, currentIndex)
            currentIndex -= 1
        }
    }
    return sortedArray
  }
}

MergeSort.swift

 class MergeSort {
 func mergeSort(_ array:[Int])->[Int] {
    guard array.count > 1 else { return array }
    let middle = array.count / 2
    //配列を分割
    let left = mergeSort(Array(array[0..<middle]))
    let right = mergeSort(Array(array[middle..<array.count]))
    return merge(left, right)
}
func merge(_ left:[Int],_ right:[Int])->[Int] {
    var leftIndex = 0
    var rightIndex = 0
    var result = [Int]()
    result.reserveCapacity(left.count + right.count)
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            result.append(left[leftIndex])
            leftIndex += 1
        } else if left[leftIndex] > right[rightIndex] {
            result.append(right[rightIndex])
            rightIndex += 1
        } else {
            result.append(right[rightIndex])
            result.append(left[leftIndex])
            rightIndex += 1
            leftIndex += 1
        }
    }
    while leftIndex < left.count {
        result.append(left[leftIndex])
        leftIndex += 1
    }
    while rightIndex < right.count {
        result.append(right[rightIndex])
        rightIndex += 1
    }
    return result
}
}

}

QuickSort.swift

class QuickSort {
func quicksort(_ array: [Int]) -> [Int] {
    // 配列のcountが1以下の時ソート済みにしてあげる
  guard array.count > 1 else {
      return array
  }
//基準値を設定
  let pivot = array[array.count/2]
    // 基準値より小さいグループ
  let less = array.filter { $0 < pivot }
    //基準値と同じグループ
  let equal = array.filter { $0 == pivot }
    // 基準値より大きいグループ
  let greater = array.filter { $0 > pivot }
    // 　小さいグループ、大きいグループそれぞれの配列を再帰的に処理する
  return quicksort(less) + equal + quicksort(greater)
    }
}

最後に

最近、アルゴ式というサービスでアルゴリズムを勉強しています。
僕のようなプログラミング初心者でも分かりやすく学べるので、是非、覗いてみてください。