정렬 (버블, 선택, 삽입, 퀵, 합병, 힙, 계수)
출처: 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)
}
}
Author And Source
이 문제에 관하여(정렬 (버블, 선택, 삽입, 퀵, 합병, 힙, 계수)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@msi753/알고리즘과-자료-구조-정렬
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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)
}
}
Author And Source
이 문제에 관하여(정렬 (버블, 선택, 삽입, 퀵, 합병, 힙, 계수)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@msi753/알고리즘과-자료-구조-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)