정렬
- 어떤 데이터 그룹이 주어졌을 때 이를 주어진 순서대로 나열하여 재배치하는 행위
- 정렬은 이진 탐색의 전처리 과정이기도 하다.
- 정렬의 종류: 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 합병 정렬
안정 정렬
- 같은 값을 가지는 복수의 원소들이 정렬 후에도 정렬 전과 같은 순서를 가지는 것
버블 정렬
시간 복잡도: O(n^2)
- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교차한다.
- 한번 순회할 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여서 버블정렬 이라고 한다.
과정
- 1회전
- 첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
- 2회전
- 첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
- 3회전
- 첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
- 4회전
- 첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.
장점
- 구현이 매우 간단하다.
단점
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
- 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
- 일반적으로 자료의 교환 작업이 자료의 이동 작업보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
비교뿐만 아니라 이동작업도 많다
Swift 코드
func bubbleSort(_ array: inout [Int]) {
guard array.count > 1 else { return }
for i in 0..<array.count {
// 각 패스의 끝에는 가장 큰 원소가 위치하므로,
// 패스가 반복될 때마다 비교할 원소의 개수를 줄여줍니다.
for j in 0..<array.count - 1 - i {
if array[j] > array[j+1] {
array.swapAt(j, j+1)
}
}
}
}
선택 정렬
시간 복잡도: O(n^2)
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 선택 정렬이라고 한다.
과정
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다.
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n 개의 주어진 리스트를 이와 같은 방법으로 정렬하는데, O(n^2) 만큼의 시간이 걸린다.
장점
- 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
단점
- 시간복잡도가 비효율적이며, 대부분의 경우 다른 알고리즘에 비해 느리다.
Swift 코드
func selectionSort(_ array: inout [Int]) {
guard array.count > 1 else {
return
}
for stand in 0..<(array.count - 1) {
var lowestIndex= stand
for index in (stand + 1)..<array.count {
if array[i] < array[lowestIndex] {
lowestIndex= i
}
}
if currentIndex != lowestIndex {
array.swapAt(stand, lowestIndex)
}
}
}삽입 정렬
시간 복잡도: 최선 O(n), 최악 O(n^2)
- 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬 되어있을 때’ 효율적인 정렬 방법이다.
- 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입 한다는 의미에서 삽입 정렬이라고 부른다.
과정
- 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어있다고 가정한다.
- 삽입 정렬은 두 번째 데이터부터 시작한다. → 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단
- 0~1번 인덱스 중 1번 인덱스 값이 들어가야 할 위치를 찾아서 넣는다.
- 0~2번 인덱스 중 2번 인덱스 값이 들어가야 할 위치를 찾아서 넣는다.
- 0~n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 넣는다.
장점
- 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
- 최선의 경우 O(N)의 시간 복잡도를 가진다.
- 정렬이 거의 되어있는 상황에서는 퀵정렬보다 속도가 빠를 수도 있다.
단점
- 평균 시간 복잡도가 O(n^2)으로, 데이터의 수가 많을 경우 성능이 떨어진다.
Swift 코드
func insertionSort(_ array: inout [Int]) {
for i in 1..<array.count {
let key = array[i]
var j = i - 1
while j >= 0 && array[j] > key {
// 삽입 위치가 인덱스 0 이상이거나 삽입 데이터가 비교 데이터보다 작은 경우 반복
array[j + 1] = array[j]
j -= 1
}
array[j + 1] = key
}
}
선택 정렬과 삽입 정렬
- 선택 정렬과 삽입 정렬의 시간 복잡도는 모두 O(n^2)이다. 하지만 선택 정렬은 매번 최소 값을 찾아야 하고 삽입 정렬은 이미 정렬된 부분과 비교해 나가기 때문에 최악의 경우에도 실질적으로 선택 정렬보다 연산 횟수가 적다.
퀵정렬
시간 복잡도: O(n log n) 최악의 경우: O(n^2)
피벗
- 교환하기 위한 ‘기준’을 나타낸다.
퀵 정렬에는 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때 피벗이 기준이되어 교환을 수행한다.
또한 분할 정복 알고리즘으로 동작한다.
분할 정복 방법
- 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
- 분할 정복 방법은 대게 재귀 함수를 이용하여 구현한다.
과정
- 피벗의 기준을 설정한다. → 리스트에서 첫 번째 데이터를 피벗으로 정한다.
- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
- 왼쪽 리스트, 오른쪽 리스트 즉, 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
- 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.
- 리스트의 크기가 0이나 1이 될때까지
장점
- 평균적으로 다른 정렬 알고리즘보다 빠르게 동작한다.
- 별도의 메모리를 필요로 하지 않아서 공간 복잡도가 작다.
단점
- 최악의 경우(정렬 대상이 이미 정렬되어 있거나, 역순으로 정렬되어 있는 경우) 시간 복잡도가 O(n^2)로 느려진다.
- pivot의 선택에 따라서 성능이 달라질 수 있다. 특정한 상황에서는 pivot을 선택하는 방법에 따라서 퀵 정렬의 속도가 느려지는 것으로 잘 알려져 있는데, 이를 해결하기 위한 방법으로, pivot을 랜덤하게 선택하거나, 중간 값을 선택하는 등의 방법이 있다.
- 안정정렬이 아니다.
Swift 코드
func quickSort(_ array: [Int]) -> [Int] {
guard let first = array.first, array.count > 1 else { return array }
let pivot = first
let left = array.filter { $0 < pivot }
let right = array.filter { $0 > pivot }
return quickSort(left) + [pivot] + quickSort(right)
}
계수 정렬
시간 복잡도: O(n + k) k: 입력 값의 최대 값
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 계수 정렬은 ‘데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때’만 사용 가능
- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 백만을 넘지 않을 때 효과적으로 사용할 수 있다.
- ‘모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언’해야 하기 때문
과정
- 입력받은 배열 A의 요소값들의 등장횟수를 저장할 배열 B와 최종적으로 정렬된 값들을 담을 배열 C를 준비한다.
- 입력받은 배열에서 값을 하나씩 꺼내서 해당 값을 배열 B의 인덱스로 사용해 B 의 요소 값을 하나 증가시킨다. (B[A[i]]++)
- B가 완성되면 B의 각 요소들을 누적합으로 갱신한다. B[i] = B[i] + B[i-1]
- A 의 가장 뒤에서 부터 값을 하나씩 꺼내서 해당값을 B의 인덱스로 사용하고 참조된 B의 값을 배열 C의 인덱스로 사용해서 배열 C에 A에서 꺼낸 값을 넣는다. C[B[A[i]]] = A[i]
- 사용된 B의 값을 하나 감소시킨다. (B[A[i]]--)
- A의 모든 요소에 대해 4번, 5번 과정을 반복한다.
배열이 여러개 사용되고 서로가 서로를 인덱스로 사용하는 상황이랑 글로는 이해하기가 쉽지 않다. 그림으로 알아보자.
장점
- 비교 연산이 필요하지 않아 실행 시간이 빠르며, 입력 값의 범위가 제한되어 있어 매우 큰 입력 값도 처리할 수 있다.
단점
- 정수형 자료형에 대해서만 적용 가능하다.
- 출력 값이 제한되어 있어 입력 값의 범위가 크게 차이나면 메모리 낭비가 심해진다.
- 입력 값이 실수형이거나, 문자열일 경우 적용이 불가능하다.
일반적인 알고리즘보다 빠른 속도를 보이지만, k가 n에 비해 매우 크거나 작은 경우에는 적합하지 않을 수 있다.
Swift 코드
func countingSort(_ arr: [Int], _ maxVal: Int) -> [Int] {
var counts: [Int] = Array(repeating: 0, count: maxVal + 1)
for element in arr {
counts[element] += 1
}
for i in 1...maxVal {
counts[i] += counts[i-1]
}
var sortedArr = [Int](repeating: 0, count: arr.count)
for element in arr {
sortedArr[counts[element]-1] = element
counts[element] -= 1
}
return sortedArr
}
합병 정렬
평균 시간 복잡도: O(n log n)
- 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트에 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합친다.
크게 보면 분할 단계와 병합 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야하는 분할 비용보다 모든 값들을 비교해야하는 병합 비용이 더 크다.
- 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하다.
- 다른 정렬 알고리즘과 달리 인접한 값들 간에 상호 자리 교대가 일어나지 않는다.
과정
예를 들어, 다음과 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정해보자.
[6, 5, 3, 1, 8, 7, 2, 4]
먼저 하나의 배열을 두 개로 쪼갠다.
[6, 5, 3, 1] [8, 7, 2, 4]
그래고 다시 두 개의 배열을 네 개로 쪼갠다.
[6, 5] [3, 1] [8, 7] [2, 4]
마지막으로 디시 네 개의 배열을 여덜 개로 쪼갠다.
[6] [5] [3] [1] [8] [7] [2] [4]
이제 더 이상 쪼갤 수가 없으니 두 개씩 합친다. 합칠 때는 작은 숫자가 앞에 큰 수자를 뒤에 위치시킨다.
[5, 6] [1, 3] [7, 8] [2, 4]
이제 4개의 배열을 2개로 합친다. 각 배열 내에서 가장 작은 값 2개를 비교해서 더 작은 값을 먼저 선택하면 자연스럽게 크기 순으로 선택이 된다.
[1, 3, 5, 6] [2, 4, 7, 8]
최종적으로 2개의 배열도 마찬가지로 크기 순으로 선택하가면서 하나로 합치면 정렬된 배열을 얻을 수 있다.
[1, 2, 3, 4, 5, 6, 7, 8]
장점
- 안정적인 정렬 방법
- 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
- 만약 레코드를 연결 리스트로 구성하면, 링크 인덱스만 변경되므로 이동은 무시할 수 있을 정도로 작아진다.
- 연결리스트를 사용한 경우, 합병 정렬은 퀵 정렬을 포함한 어떤 정렬 방법보다 효율적이다.
단점
- 레코드를 배열로 구성하면, 임시 배열이 필요하다.
- 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
- 마지막에 합치는 과정에서도 추가적인 복사가 필요하다.
Swift 코드
func mergeSort(_ array: [Int]) -> [Int] {
if array.count <= 1 { return array }
let center = array.count / 2
let left = Array(array[0..<center])
let right = Array(array[center..<array.count])
func merge(_ left: [Int],_ right: [Int]) -> [Int] {
var left = left
var right = right
var result: [Int] = []
while !left.isEmpty && !right.isEmpty {
if left[0] < right[0] {
result.append(left.removeFirst())
} else {
result.append(right.removeFirst())
}
}
// 왼쪽 배열의 요소가 남은 경우
if !left.isEmpty {
result.append(contentsOf: left)
}
// 오른쪽 배열의 요소가 남은 경우
if !right.isEmpty {
result.append(contentsOf: right)
}
return result
}
return merge(mergeSort(left), mergeSort(right))
}
퀵 정렬 VS 합병 정렬
퀵 정렬과 합병 정렬은 모두 O(n log n)의 시간 복잡도를 가진다. 하지만 정렬 방식은 다르다.
퀵 정렬은 분할 정복 방식을 사용하는데, 피벗을 기준으로 리스트를 분할하여 각각 독립적으로 정렬한다. 따라서 피벗의 선택에 따라서 성능이 크게 달라질 수 있으며, 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다.
합병 정렬도 분할 정복 방식을 사용하긴 하지만, 리스트를 특별한 기준 값으로 나누는 것이 아니라 단지 리스트를 반으로 나눈 후에 각각을 재귀적으로 합병 정렬을 수행하고 하나의 리스트로 합병한다. 즉, 퀵 정렬은 정렬 후 → 분할이지만 합병 정렬은 분할 → 정렬 → 합병이다.
이러한 방식을 사용하기 때문에 합병 정렬은 안정적인 정렬 알고리즘이며, 데이터의 분포에 상관없이 항상 O(n log n)의 시간 복잡도를 가진다. 하지만 메모리를 많이 사용한다는 단점이 있다.
정리
- 버블 정렬, 선택 정렬: 구현이 간단하고 이해하기 쉽지만, 시간 복잡도가 O(n^2)으로 비효율적인 알고리즘이므로 작은 규모의 데이터를 정렬할 때 사용하는 것이 좋다.
- 삽입 정렬: 구현이 간단하고 효율적인 알고리즘이지만, 시간 복잡도가 O(n^2) 으로 더 효율적인 알고리즘과 비교했을 때 성능이 떨어지므로 중간 규모의 데이터를 정렬할 때 사용하는 것이 좋다. 정렬이 거의 되어있는 경우 퀵 정렬보다 빠른 속도를 자랑한다.
- 퀵 정렬: 평균적으로 가장 빠르고 효율적인 알고리즘 중 하나이지만, 최악의 경우 시간 복잡도가 O(n^2)로 성능이 떨어지므로 대부분의 데이터를 정렬할 때 사용하는 것이 좋다.
- 계수 정렬: 데이터의 범위가 제한적이고 정수 형태의 데이터를 정렬할 때 가장 효율적인 알고리즘이므로 데이터의 범위가 제한적이고 큰 데이터를 정렬할 때 사용하는 것이 좋다.
- 합병 정렬: 안정적인 정렬 알고리즘 중 하나로, 최악의 경우 시간 복잡도가 O(n log n)으로 효율적인 알고리즘이지만, 다른 정렬 알고리즘보다 구현이 복잡하므로 대부분의 데이터를 정렬할 때 사용하는 것이 좋다.
Swift의 sort 함수
Swift는 기본 라이브러리에서 sort() 함수를 통해 배열의 정렬 기능을 제공한다.
그렇다면 swift에서는 배열의 정렬을 어떤 알고리즘으로 구성했을까?
Swift 버전에 따라 정렬 알고리즘을 다르게 사용할 수 있다.
이전에는 introsort 알고리즘을 사용했다고 하지만 현재(2023.5.6) Swift 5 버전부터는 Timsort를 사용한다고 한다. swift/Sort.swift at main · apple/swift (github.com)
여기서 Timsort는 수 많은 종류의 실세계 데이터에 잘 수행하도록 설계된 하이브리드형 안정 정렬 알고리즘 중 하나라고 한다.
좀 더 쉽게 말하자면, 합병 정렬과 삽입 정렬을 결합한 알고리즘이며, Timsort는 안정적이고 최선, 평균, 최악 시간 복잡도가 모두 O(n log n)으로 매우 효율적인 알고리즘이라고 한다.
출처
[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog (gmlwjd9405.github.io)
[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog (gmlwjd9405.github.io)
이것이 취업을 위한 코딩 테스트다. (나동빈 저)
swift/Sort.swift at main · apple/swift (github.com)