ソース:https://github.com/raywenderlich/swift-algorithm-club

泡の位置合わせ

一つずつ増えて、隣との比較.
回転が終わるたびに、最後の数字は揃えられ、比較する必要はありません.

Runtime:Bubble Bubble
Average: O(N^2)
Worst: O(N^2)

Memory:
O(1)

for i in 0..<array.count {
    for j in 1..<array.count-i {
        if array[j] < array[j-1] {
            let tmp = array[j-1]
            array[j-1] = array[j]
            array[j] = tmp
        }
    }
}

ComparisonとGenericを使用した関数の作成

import Foundation

public func bubbleSort<T> (_ elements: [T]) -> [T] where T: Comparable {
    return bubbleSort(elements, <)
}

public func bubbleSort<T> (_ elements: [T], _ comparison: (T, T) -> Bool) -> [T] {
    var array = elements
    
    for i in 0..<array.count {
        for j in 1..<array.count-i {
            if comparison(array[j], array[j-1]) {
                let tmp = array[j-1]
                array[j-1] = array[j]
                array[j] = tmp
            }
        }
    }
    return array
}

var array = [4,2,1,3]

print("before:",array)
print("after:", bubbleSort(array))
print("after:", bubbleSort(array, <))
print("after:", bubbleSort(array, >))

選択

昇順の場合
毎回一番小さいのを選びます

[ ...sorted numbers... | ...unsorted numbers... ]
[| 5, 8, 3, 4, 6 ]
[ 3 | 8, 5, 4, 6 ]
[ 3, 4 | 5, 8, 6 ]
[ 3, 4, 5 | 8, 6 ]
[ 3, 4, 5, 8 | 6 ]

O(n^2)中からぐるっと回って外からぐるっと回って
挿入位置合わせよりも遅く、泡位置合わせよりも速くなります.
左から順に並びます.
最後の要素は自動的に決定されるので、外側ループのインデックスはa.count-2に計算するだけです.

func selectionSort(_ array: [Int]) -> [Int] {
    guard array.count > 1 else { return array } //원소가 1개 미만이면 종료
    
    var a = array
    
    for x in 0..<a.count-1 {    //막대기 하나씩 이동
        var lowest = x
        for y in x+1..<a.count {    //여기서 가장 작은 원소 구하기
            if a[y] < a[lowest] {
                lowest = y
            }
        }
        
        if x != lowest {    //같은 경우 스위프트는 변경할 수 없기 때문에 체크가 필요하다
            a.swapAt(x, lowest)
        }
    }
    return a
}

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list)

isOrderedBeforeソートの使用

public func selectionSort<T: Comparable>(_ array: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
    guard array.count > 1 else { return array }
    
    var a = array
    for x in 0..<a.count-1 {
        var lowest = x
        for y in x+1..<a.count {
            if isOrderedBefore(a[y], a[lowest]) {
                lowest = y
            }
        }
        
        if x != lowest {
            a.swapAt(x, lowest)
        }
    }
    
    return a
}

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list, <)

整列挿入

https://velog.io/@msi 753/アルゴリズムおよび-リソース-構造-ベース-挿入ソート

クイックソート

pivot피벗
アレイの長さの中央にある要素をピボットとして指定します.
その要素より小さいものと大きいものを繰り返し区別します.O(NlogN)

func quicksort<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { return a }

  let pivot = a[a.count/2]
  let less = a.filter { $0 < pivot }
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }

  return quicksort(less) + equal + quicksort(greater)
}

let list = [ 10, 0, 3, 9, 2, 14, 8, 27, 1, 5, 8, -1, 26 ]
quicksort(list)

ロムト・ルムト

一番後ろの要素を軸に

func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
    let pivot = a[high]
    
    var i = low
    for j in low..<high {
        if a[j] <= pivot {
            a.swapAt(i, j)
            i += 1
        }
    }
    
    a.swapAt(i, high)
    return i
}

var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
let p = partitionLomuto(&list, low: 0, high: list.count - 1)

[| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
   low                                       high
   i
   j

jを大きくすると、iがhigh(軸心)より大きいと位置が変化する

[| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
   low                                        high
   i
       j

[ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]
  low                                         high
      i

上の関数を実行して、iとhighを次のように置き換えます.
high(軸心)を基準として、i回が等しい以上である

[ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
  low                                        high
                         i                   j
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]

func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let pivot = a[high]

  var i = low
  for j in low..<high {
    if a[j] <= pivot {
      a.swapAt(i, j)
      i += 1
    }
  }

  a.swapAt(i, high)
  return i
}

var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quicksortLomuto(&list, low: 0, high: list2.count - 1)

func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let p = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: p - 1)
    quicksortLomuto(&a, low: p + 1, high: high)
  }
}

オーストラリア🦩

パーティション|パーティション

リストの첫 번째 데이터を피벗に設定します.5 7 9 0 3 1 6 2 4 8
5より大きいデータ7を選択(右に拡張)
左に減らし、5未満のデータ4を選択して変更5 4 9 0 3 1 6 2 7 85 4 9 0 3 1 6 2 7 85 4 2 0 3 1 6 9 7 8
ずらす場合は、작은 데이터と피벗の位置を変更します5 4 2 0 3 1 6 9 7 81 4 2 0 3 5 6 9 7 8
5を基準に
左は5未満
右も5より大きい

繰り返し

14203この部分と69178この部分で分割のプロセスをそれぞれ繰り返す

func partitionHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
  let pivot = a[low]	//첫번째 데이터가 피벗
  var i = low - 1	//i는 왼쪽
  var j = high + 1	//j는 오른쪽

  while true {
    repeat { j -= 1 } while a[j] > pivot	//피벗보다 큰 데이터 찾을 때까지 반복
    repeat { i += 1 } while a[i] < pivot	//피벗보다 작은 데이터 찾을 때까지 반복

    if i < j {
      a.swapAt(i, j)
    } else {
      return j
    }
  }
}

var list = [ 8, 0, 3, 9, 2, 14, 10, 27, 1, 5, 8, -1, 26 ]
let p = partitionHoare(&list, low: 0, high: list.count - 1)		// 파티션 인덱스 구하기

func quicksortHoare<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
  if low < high {
    let p = partitionHoare(&a, low: low, high: high)
    quicksortHoare(&a, low: low, high: p)
    quicksortHoare(&a, low: p + 1, high: high)
  }
}

連結ソート

https://velog.io/@msi 753/アルゴリズムおよび-リソース-構造-ベース-マージ-ソート

お尻の位置合わせ

maxheaps: Elements with a higher value represent higher priority. サブノードより大きい値

minheaps: Elements with a lower value represent higher priority. サブノード値より小さい

Removing the highest priority element

9郎3の位置を変える.

8対3の大きさ

Adding a new element

Practical Representation

structなので@逃走priorityfunctionが必要です...
よくわかりませんが...
難しいですね.

struct Heap<Element> {
    var elements: [Element]
    let priorityFunction: (Element, Element) -> Bool    //우선순위 비교하기
    
    init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) {
        self.elements = elements
        self.priorityFunction = priorityFunction
        buildHeap()
    }
    
    mutating func buildHeap() {
        for index in (0..<count/2).reversed() {
            shiftDown(elementAtIndex: index)
        }
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var count: Int {
        return elements.count
    }
    
    func peek() -> Element? {
        return elements.first
    }
    
    //MARK: - index 구하기
    func isRoot(_ index: Int) -> Bool {
        return (index==0)
    }
    
    func leftChildIndex(of index: Int) -> Int {
        return (2*index)+1
    }
    
    func rightChildIndex(of index: Int) -> Int {
        return (2*index)+2
    }
    
    func parentIndex(of index: Int) -> Int {
        return (index-1)/2
    }
    
    //MARK: - 우선순위 비교하기
    func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
        return priorityFunction(elements[firstIndex], elements[secondIndex])
    }
    
    func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
        guard childIndex<count && isHigherPriority(at: childIndex, than: parentIndex) else {
            return parentIndex
        }
        return childIndex
    }
    
    func highestPriorityIndex(for parent: Int) -> Int {
        //parent와 leftChild비교 후, rightChild와 비교해서 큰 값 구하기
        return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent))
    }
    
    mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
        guard firstIndex != secondIndex else {
            return
        }
        elements.swapAt(firstIndex, secondIndex)
    }
    
    //MARK: - 새로운 원소 넣기
    mutating func enqueue(_ element: Element) {
        elements.append(element)
        shiftUp(elementAtIndex: count-1)
    }
    
    mutating func shiftUp(elementAtIndex index: Int) {
        let parent = parentIndex(of: index)
        guard !isRoot(index), isHigherPriority(at: index, than: parent) else {
            return
        }
        swapElement(at: index, with: parent)
        shiftUp(elementAtIndex: parent)
    }
    
    //MARK: - 가장 우선순위 높은 원소 제거하기
    mutating func dequeue() -> Element? {
        guard !isEmpty else {
            return nil
        }
        swapElement(at: 0, with: count-1)   //첫번째원소와 마지막원소 바꾸기
        let element = elements.removeLast()
        if !isEmpty {
            shiftUp(elementAtIndex: 0)
        }
        return element  //가장 우선순위가 높은 원소
    }
    
    mutating func shiftDown(elementAtIndex index: Int) {
        let childIndex = highestPriorityIndex(for: index)
        if index == childIndex {
            return
        }
        swapElement(at: index, with: childIndex)
        shiftDown(elementAtIndex: childIndex)
    }
}


var heap = Heap(elements: [3, 2, 8, 5, 0], priorityFunction: >) //[8, 5, 3, 2, 0]

ソート数

array: [ 10, 9, 8, 7, 1, 2, 7, 3 ]

//step1
시간복잡도가 O(N+K)
N: 데이터의 개수
K: 데이터 중 최댓값
Index 0 1 2 3 4 5 6 7 8 9 10
Count 0 1 1 1 0 0 0 2 1 1 1

그리고 인덱스에 들어있는 횟수만큼 그 숫자를 꺼낸다

import Foundation

let array = [10, 9, 8, 7, 1, 2, 7, 3]

let maxElement = array.max() ?? 0
var countArray = [Int](repeating: 0, count: Int(maxElement+1))

//step1
for element in array {
    countArray[element] += 1
}

for i in 0..<countArray.count {
    for _ in 0..<countArray[i] {
        print(i)
    }
}