알고리즘과 자료 구조 - 정렬 (버블, 선택, 삽입, 퀵, 합병, 힙, 계수)

인생노잼시기·2021년 6월 23일
알고리즘과 자료구조
0

🌲알고리즘과 자료구조 [스위프트]

목록 보기
10/16

출처: https://github.com/raywenderlich/swift-algorithm-club

버블정렬

하나씩 증가하면서 바로 옆에 있는거랑 비교하는데
회전이 끝날때마다 마지막 숫자는 정렬되어 더 이상 비교할 필요가 없다.

  • Runtime: 버블버블
    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/@msi753/알고리즘과-자료-구조-기초-삽입정렬

퀵정렬

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)

로무토Lomuto

맨 뒤에 있는 원소를 피벗으로 한다

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를 증가시키면서 high(피벗)보다 i가 크면 자리를 바꾼다

[| 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)
  }
}

호어Hoare 🦩

분할(Divide) || 파티션(Partition)

리스트의 첫 번째 데이터를 피벗으로 설정한다.
5 7 9 0 3 1 6 2 4 8
오른쪽으로 증가하면서 5보다 큰 데이터 7 선택
왼쪽으로 감소하면서 5보다 작은 데이터 4 선택 후 변경한다
5 4 9 0 3 1 6 2 7 8

5 4 9 0 3 1 6 2 7 8
5 4 2 0 3 1 6 9 7 8

엇갈린 경우 작은 데이터와 피벗의 위치를 변경한다
5 4 2 0 3 1 6 9 7 8
1 4 2 0 3 5 6 9 7 8
5를 기준으로
왼쪽은 모두 5보다 작고
오른쪽은 모두 5보다 크다

반복

1 4 2 0 3 이 부분과
6 9 7 8 이 부분에서 각각 분할의 과정을 반복한다

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/@msi753/알고리즘과-자료-구조-기초-합병-정렬

힙정렬

  • 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을 @escaping 해줘야한다는데...
잘 모르겠다...
어렵구만...

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)
    }
}
profile
인생노잼시기
인생노잼
이전 포스트

알고리즘과 자료 구조 - 기초 - 보이어무어 Boyer-Moore string search

다음 포스트

알고리즘과 자료 구조 - deque덱 (🦩)

0개의 댓글