[Swift 알고리즘] 정렬 알고리즘
2022. 5. 23. 15:32ㆍSwift 코딩테스트/Swift 알고리즘
728x90
//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎
대부분 O(n²)과 O(nlogn) 사이의 시간 복잡도
| 정렬 알고리즘 | 정의 | 시간복잡도 |
| 버블(bubble) | 데이터의 인접 요소기리 비교하고, swap 연산을 수행하며 정렬하는 방식 | O(n²) |
| 선택(selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 | O(n²) |
| 삽입(insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 | O(n²) |
| 퀵(quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 | O(nlogn) |
| 병합(merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 | O(nlogn) |
| 힙(heap) | 힙이라는 자료구조를 사용해서 최소힙 또는 최대힙으로 정렬하는 방식 | O(nlogn) |
| 기수(radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 | O(kn) |
| 계수(counting) | 데이터가 몇 번 나타나는지를 새어서 정렬하는 방식 | O(n) |
1. 버블 정렬(bubble): 두 인접한 데이터를 비교해 정렬
- 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬
- 원본 데이터의 순서가 훼손된다.
- 시간 복잡도 O(n²): 다른 정렬 알고리즘보다 속도가 느린 편
- 수행시간: (n-1) + (n-2) + ... + 2 + 1 = O(n²)
- worst 케이스와 average 케이스 모두 O(n²)
- 배열이 운 좋게도 이미 정렬되어 있는경우에도 의미 없이 순환함
- 수행시간: (n-1) + (n-2) + ... + 2 + 1 = O(n²)
[버블정렬 코드 개요]
A: 정렬할 배열
N: 정렬할 수 개수
func bubbleSort(A[], n){
for i in 0..<(n - 1){
for j in 0..<(n - 1 - i){ //i를 빼는 것은 정렬된 범위를 제외하는 것
if A[j] > A[j + 1]{
let temp = A[j]
A[j] = A[j + 1]
A[j + 1] = temp
}
}
}
}[백준 2750 버블정렬]
func bubbleSort(a: [Int], n: Int) -> [Int]{
var arr = a
for i in 0..<n - 1{
for j in 0..<n - 1 - i{
if arr[j] > arr[j + 1]{
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
return arr
}
2. 선택정렬: 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택
- 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap 하는 것
- 맨 오른 쪽 원소를 제외하고 루프 반복
- 하나의 원소만 남을 때 까지 루프를 반복
- 원본 데이터의 순서가 훼손된다.
- 맨 오른 쪽 원소를 제외하고 루프 반복
- 시간 복잡도 O(n²): 다른 정렬 알고리즘보다 속도가 느린 편
- 수행시간: (n-1) + (n-2) + ... + 2 + 1 = O(n²)
- worst 케이스와 average 케이스 모두 O(n²)
- 수행시간: (n-1) + (n-2) + ... + 2 + 1 = O(n²)
[선택정렬 코드 개요]
A: 정렬할 배열
N: 정렬할 수 개수
//오름차순
func selectionSort(A[], N){
for i in 0..<N-1{ //1개가 남을 때 까지 반복
for j in (i+1)..<N{ //i는 0부터 시작 -> j는 그 다음 1부터 시작
Min의 index찾기
}
Min과 현재 i 값 교환
}[백준 2750 선택정렬]
func selectionSort(a: [Int], n: Int) -> [Int]{
var arr = a
for i in 0..<n-1{
var min = i
for j in i+1..<n{
if arr[j] < arr[min]{
min = j
}
}
arr.swapAt(min, i)
}
return arr
}3. 삽입정렬: 이미 정렬된 데이터 범위에서 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬
- 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 삽입 정렬의 핵심
- A[1...i]의 적당한 자리에 A[i]를 삽입한다.
- A[i]가 A[i-1]보다 크면 제자리에 두고
- 그렇지 않다면 A[i-1]부터 왼쪽으로 돌며 A[i]의 위치를 찾는다.
- A[i]가 삽입될 자리부터 시작해서 그 이후(오른쪽)의 원소들은 모두 한 칸씩 오른쪽으로 shift한다.
- A[1...i]의 적당한 자리에 A[i]를 삽입한다.
- 시간 복잡도 O(n²): 다른 정렬 알고리즘보다 속도가 느린 편
- 수행시간: (n-1) + (n-2) + ... + 2 + 1 = O(n²)
- worst case: 1 + 2 + ... + (n -2) + (n-1)
- average case: 1/2 * ( 1 + 2 + ... + (n-2) + (n-1))
- best case: O(n): 다 정렬되어 있는 경우
- 삽입 정렬은 수행시간이 O(n²)인 비효율적인 정렬 알고리즘에 속하지만,배열이 모두 정렬되어 있는 상태에서는 가장 매력적인 알고리즘이다. 정렬되어 있다면 shift할 필요 없이 외부의 for 루프만 돌면 되기 때문에 O(n) 수행시간이 소요된다.
- 수행시간: (n-1) + (n-2) + ... + 2 + 1 = O(n²)
- 정렬을 기다리고 있는 부분의 값들의 상대적 위치가 원래 그대로 유지되고 있는, 상당히 안정적인 정렬이다.
- 선택정렬과 버블정렬은 정렬되지 않은 배열의 크기를 하나씩 줄여나간다.
- 삽입정렬은 한 개짜리 배열에서 시작해서 이미 정렬된 배열의 크기를 하나씩 늘려나가는 과정에서 차이가 있다.
[삽입정렬 코드 개요]
A: 정렬할 배열
N: 정렬할 수 개수
func insertionSort(A[], N){
for i in 0..<N{
var temp = A[i] //선택 데이터
var insertIndex = 0 //삽입할 인덱스를 저장할 변수
//이전의 정렬된 범위 내에서 역순으로 들어갈 위치를 검색
while insertIndex >= 0 && A[insertIndex] > temp {
//정렬된 범위내에서 선택 데이터보다 크면 오른쪽으로 shift
A[insertIndex + 1] = A[insertIndex]
insertIndex -= 1
}
A[insertIndex + 1] = temp //루프를 빠져나와서 선택 데이터를 삽입
}
}[백준 2750 삽입정렬]
func insertionSort(a: [Int], n: Int) -> [Int]{
var arr = a
for i in 1..<n{
var temp = arr[i]
var j = i - 1
while j >= 0 && arr[j] > temp {
arr[j+1] = arr[j]
j -= 1
}
arr[j+1] = temp
}
return arr
}4. 퀵정렬: 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬
- 기준값(pivot)을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것
- 데이터를 분할할 pivot을 설정한다.
- pivot이 제일 작은 값 or 큰 값인지 알 수 없기 때문에(=상관 없기 때문에) 중간에 위치한 값으로 설정
- pivot을 기준으로 데이터를 2개의 집합으로 분리한다.
- pivot을 기준으로 가장 왼쪽에 있는 데이터를 start
- start가 pivot보다 작으면 → start += 1
- start가 pivot보다 크면 → start 멈춤
- pivot을 기준으로 가장 오른쪽에 있는 데이터를 end
- end가 pivot보다 크면 → end -= 1
- end가 pivot보다 작으면 → end 멈춤
- start와 end이 둘 다 멈췄을 때 start와 end를 swap한 후 start +=1 , end -= 1
- start == end 지점의 데이터가 pivot보다 크면 pivot의 위치는 -1, 작으면 +1
- start ≥ end가 되면 종료 → pivot을 기준으로 분할된 집합에서 다시 반복
- 분리 집합의 요소가 1개 이하가 될 때 까지 재귀
- pivot을 기준으로 가장 왼쪽에 있는 데이터를 start
- 데이터를 분할할 pivot을 설정한다.
- 시간 복잡도: O(nlogn)
- 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미친다.
- worst case: O(n²): 기준값이 항상 끝값일 경우
[퀵정렬 코드 개요] - 중간 값 Pivot은 swap시에 업데이트가 필요하다
func quickSort(start: Int, end: Int){
if start >= end { return }
var left = start
var right = end
var pivot = (left + right) / 2
while left <= right{
while left < end && arr[left] < arr[pivot]{
left += 1
}
while right > start && arr[right] > arr[pivot]{
right -= 1
}
if left <= right {
//pivot도 swap되면 인덱스 개념인 pivot도 업데이트 되어야 한다
if pivot == left {
pivot = right
}else if pivot == right{
pivot = left
}
arr.swapAt(left, right)
left += 1
right -= 1
}
}
if start < right {
quickSort(start: start, end: right)
}
if left < end {
quickSort(start: left, end: end)
}
}[퀵정렬 코드 개요] - 고차함수 filter 사용 - pivot이 가운데 있는 경우
A: 정렬할 배열
quickSort(A[]) -> [Int]{
guard A.count > 1 else {return A} //집합의 요소가 1개 이하라면 종료
let pivot = A[A.count / 2] //pivot이 가운데 있는 경우
let left = A.filter {$0 < pivot}
let right = A.filter {$0 > pivot}
let equal = A.filter {$0 == pivot} //equal을 따로 처리하지 않으면 배열의 개수가 달라짐
return quickSort(left) + equal + quickSort(right)
}
filter 함수 참고 바람: https://ksk9820.tistory.com/127
[백준 2750 퀵정렬]
func quickSort(a: [Int]) -> [Int]{
var arr = a
guard arr.count > 1 else {return arr}
let pivot = arr[arr.count / 2]
let left = arr.filter {$0 < pivot}
let right = arr.filter {$0 > pivot}
let equal = arr.filter {$0 == pivot}
return quickSort(a: left) + equal + quickSort(a: right)
}
퀵정렬의 경우
1. pivot값이 중간값인 상태에서(제일 왼쪽 값과 swap하지 않은 상태에서)
2. right, left로 quickSort를 호출하지 않고 pivot - 1, pivot + 1로 quickSort를 호출하여 정렬하는 방법
을 구현하고 싶었으나 아직 구현하지 못했다. 만약 위의 상황으로 퀵정렬을 구현하는 방법을 알고 계신분이 있다면 댓글 꼭 부탁드립니다.
1. pivot = left + right / 2 인 상황에서 pivot -1, pivot + 1 의 재귀함수를 호출 하면?
2. pivot이 가운데에 위치한 상황에서 pivot도 swap될 수 있기 때문에 pivot의 index를 업데이트하는데 맞는지
3. left와 right이 엇갈리는 경우 right과 pivot을 swap했는데도 정렬되지 않음
5. 병합정렬: 분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
- 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다.
- 배열 요소의 개수가 1개 → 2개 → 4개 → 8개 → ... → n개가 되도록 분할한 후 정렬해서 병합 재귀
- 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동
- 두 배열 중(left or right) 모든 값을 결과 배열에 넣은 배열이 생긴다면
- 아직 요소가 남아 있는 배열의 값을 그대로 결과 배열에 추가한다.
- 이미 정렬되어 있는 배열이기 때문에 그대로 추가해도 무방
- 아직 요소가 남아 있는 배열의 값을 그대로 결과 배열에 추가한다.
- 배열 요소의 개수가 1개 → 2개 → 4개 → 8개 → ... → n개가 되도록 분할한 후 정렬해서 병합 재귀
- 시간 복잡도: O(nlogn)
[병합정렬 코드 개요]
A: 정렬할 배열
B: 정렬된 배열
func divide(A[]) -> [Int] {
//배열 요소의 개수가 1개이면 값을 비교할 수 없기 때문에 재귀 종료 지점 설정
if A.count <= 1 { return }
let mid = A.count / 2
let left = [0..<mid]
let right = [mid..<A.count]
return mergeSort(divide(left), divide(right))
}
func mergeSort(Left[], Right[]) -> [Int]{
//Left와 Right을 비교할 수 있을 때 == Left와 Right에 비교할 요소가 남아 있을 떄 까지
while !Left.isEmpty && !Right.isEmpty{
//Left의 첫 요소와 Right의 첫 요소를 비교해서 작은값을 Result에 넣고 해당 값 삭제
if Left[0] > Right[0]{
result.append(Left.removeFirst())
}else{
//반대
}
}
if !empty{
//어느 한 배열에 요소가 하나도 없을 때 남은 배열(정렬된 상태)를 result에 추가하고 리턴
B.append()
}
return B
}[백준 2750 병합정렬]
func divide(a: [Int]) -> [Int]{
if a.count <= 1 {return a}
let mid = a.count / 2
let left = Array(a[0..<mid]) //Array()를 하지 않으면 ArraySlice<Int>이기 때문
let right = Array(a[mid..<a.count])
return mergeSort(left: divide(a: left), right: divide(a: right))
}
func mergeSort(left: [Int], right: [Int]) -> [Int]{
var result: [Int] = []
var l = left
var r = right
while !l.isEmpty && !r.isEmpty{
if l.first! > r.first! {
result.append(r.removeFirst())
}else{
result.append(l.removeFirst())
}
}
//left와 right중 하나라도 empty가 되면
if !l.isEmpty{
result.append(contentsOf: l)
}
if !r.isEmpty{
result.append(contentsOf: r)
}
return result
}
6. 힙정렬: 힙이라는 특수한 자료구조를 사용하는 정렬 알고리즘
- 힙(Heap)
- 이진 트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽 부터 꽉 채워져 있다.
- 최소힙의 각 노드의 값은 자신의 자식 값보다 작다. → 루트 노드에는 최소값
- 최대힙의 각 노드의 값은 자신의 자식 값보다 크다. → 루트 노드에는 최대값
- 힙의 모든 노드는 하나씩의 값을 가지고 있다.
- 각 노드의 값은 자신의 자식 값보다 작다.(최소힙일 때)
- 힙정렬은 먼저 주어진 배열을 힙으로 만든다.
- (루트 노드에 있는 원소를 제거하여 다른 곳에 저장한다.)
- 맨 끝에 있는 원소와 루트 노드를 교환한다.
- 루트 노드와 자식들간에 힙성질이 깨짐
- heapify()를 이용해 힙성질을 만족하도록 수선한다.
- heapify(A[], k, n): A[k]를 루트로 하는 트리를 힙성질을 만족하도록 수선
- A[k]에 매달린 두 서브트리가 힙성질을 만족하는 상태에서 A[k]를 루트로 하는 서브트리 전체가 힙성질을 만족하도록 수선
- 힙은 완전이진트리이기 때문에 인덱스의 절반(1/2)만 확인해줘도 된다.
- 리프 노드는 그 자체로 힙성질을 만족 → 리프 노드가 아닌 노드들을 맨뒤에서 부터 수선
- heapify(A[], k, n): A[k]를 루트로 하는 트리를 힙성질을 만족하도록 수선
- heapify()를 이용해 힙성질을 만족하도록 수선한다.
- 루트 노드와 자식들간에 힙성질이 깨짐
- 맨 끝에 있는 원소와 루트 노드를 교환한다.
- 힙에 요소가 하나만 남을 때 까지 반복
- 마지막 요소가 제일 크거나 제일 작은 요소로 자동 정렬
- (루트 노드에 있는 원소를 제거하여 다른 곳에 저장한다.)
- 시간복잡도: O(nlogn)
- heapify:힙을 만들 때는 힙의 높이 만큼만 계산: logn
- heapify를 호출하는 횟수: n
[힙정렬 코드 개요]
func buildHeap(){
//힙 만들기
//인덱스 절반만 heapify호출하기
}
func heapify(A[], k){
//힙 수선하는 과정
//root가 0부터 시작
let left = 2 * k + 1
let right = 2 * k + 2
//자식노드가 2개일 때
//자식노드가 1개일 때
//자식노드가 0개일 때
//자식노드중 제일 작은 노드의 값과 루트노드(k)의 값과 비교해서 swap
//swap하고 그 자식 노드의 자식노드와 다시 heapify
}
[백준 2750 힙정렬]
func buildHeap<T: Comparable>(a: inout [T], n: Int){
var i = n / 2
while i >= 0 {
heapify(a: &a, k: i, n: input)
i -= 1
}
}
//최소힙정렬
func heapify<T: Comparable>(a: inout [T], k: Int, n: Int){
let left = 2 * k + 1
let right = 2 * k + 2
var smaller: Int!
//k가 두 자식을 가지는 경우
if right < n {
if a[left] < a[right]{
smaller = left
}else{
smaller = right
}
}
//k가 왼쪽 자식만 가지는 경우
else if left < n {
smaller = left
}
//k가 리프노드인 경우
else{
smaller = nil
return
}
//최소힙
//부모노드보다 자식노드가 더 작은 경우 swap
//swap한 후 자식노드의 자식노드도 확인해야하기 때문에 heapify
if smaller != nil && a[smaller] < a[k]{
a.swapAt(smaller, k)
heapify(a: &a, k: smaller, n: n)
}
}
func heapSort<T: Comparable>(a: inout [T], n: Int){
buildHeap(a: &a, n: n)
var size = n
var i = size - 1
//하나 남을 때 까지
for j in (1..<n).reversed(){
//마지막 리프노드와 루트 노드 교환
a.swapAt(j, 0)
heapify(a: &a, k: 0, n: j)
}
}제너릭 참고: https://ksk9820.tistory.com/107
7. 기수정렬: 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교하는 정렬
- 입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에(자연수가 아닌 제한된 종류를 가진 알파벳 등도 해당) 사용할 수 있는 방법
- 값을 비교하지 않는 특이한 정렬
- 해당 자릿수를 비교한다는 뜻은
- 432 와 123 → 4와 1, 3과 2, 2와 3을 비교
- 10개의 공간이 필요하고, 각 공간은 0부터 9까지 값을 대표
- 일의 자릿수를 기준으로 데이터를 저장 → 십의 자릿수를 기준으로 데이터를 저장 → 백 → 천 → ...
- 자릿수를 얻는 방법 예) 432
- 432에서 2는
- 432 / 1 = 432
- 432 % 10 = 2 - 나머지 연산 활용
- 432에서 3은
- 432 / 10 = 43
- 43 % 10 = 3
- 432에서 2는
- 해당 자릿수를 비교한다는 뜻은
- 안정성을 유지하는 정렬
- 값이 같은 원소끼리는 정렬 후에 원래의 순서가 바뀌지 않는 성질
- 데이터를 담는 자료구조가 FIFO(First In First Out) 형태를 취하기 때문에 원래의 순서를 유지할 수 있다.
- 값이 같은 원소끼리는 정렬 후에 원래의 순서가 바뀌지 않는 성질
- 시간복잡도: O(kn)
- k는 데이터의 자릿수
- 기수정렬은 시간복잡도가 가장 짧은 정렬이다. 정렬해야하는 데이터의 개수가 너무 많으면 기수정렬 알고리즘을 활용
[기수정렬 코드 개요] - 백준 2750에서는 런타임에러
func radixSort(arr: inout [Int]){
var done = false //루프종료를 알릴 벼
var index: Int //각 자릿수의 숫자
var digit = 1 //자릿수 - 매 루프마다 * 10
while !done {
done = true
var buckets: [[Int]] = [[Int]](repeating: [], count: 10)
for num in arr{
index = num / digit
buckets[index % 10].append(num)
//done은 루프를 돌 때 마다 true,
//index > 0은 digit의 자릿수보다 num의 자릿수가 클 경우로
//계속해서 비교할 수 있는 경우를 말함
//done이 계속해서 true이고 index가 계속해서 0이하가 나오고 끝나는 경우에 종료
if done && index > 0 {
done = false
}
}
//정렬된 buckets을 arr로 copy
var i = 0
for j in 0..<10{
let bucket = buckets[j]
for k in bucket{
arr[i] = k
i += 1
}
}
//그 다음 자릿수
digit *= 10
}
}[백준 10814 기수정렬]
func radixSort(arr: inout [Int], name: inout [String]){
var done = false
var index: Int
var digit = 1
while !done {
done = true
var buckets: [[Int]] = [[Int]](repeating: [], count: 10)
var buckets_name: [[String]] = [[String]](repeating: [], count: 10)
for num in 0..<arr.count{
index = arr[num] / digit
buckets[index % 10].append(arr[num])
buckets_name[index % 10].append(name[num])
if done && index > 0 {
done = false
}
}
var i = 0
for j in 0..<10{
let bucket = buckets[j]
let bucket_name = buckets_name[j]
for k in 0..<bucket.count{
arr[i] = bucket[k]
name[i] = bucket_name[k]
i += 1
}
}
digit *= 10
}
}8. 계수정렬: 한정된 범위에서 갯수를 세어 정렬하는 알고리즘
- 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우에(= 한정된 범위를 갖는 경우) 사용할 수 있다.
- 배열 A[1...n]의 원소들이 k를 넘지 않는 자연수일 경우
- 1부터 k까지의 자연수가 각각 몇 번 나타나는지를 샌다
- A[1...n]의 각 원소가 몇 번째에 놓이면 되는지를 계산할 수 있다.
- 1부터 k까지의 자연수가 각각 몇 번 나타나는지를 샌다
- 정렬할 원소가 꼭 양수일 필요가 없다. 원소들이 모두 -k와 k사이의 정수이고 k가 O(n)일 경우에도 여전히 계수정렬을 사용하여 선형시간에 정렬할 수 있다.
- 시간복잡도: O(n)
- k가 O(n)을 초과하면 시간은 O(k)가 된다.
- 만약 k가 O(nlogn)을 초과하면 계수정렬은 병합, 퀵, 힙정렬보다 매력이 없어진다.
- 그래서 일반적으로 계수정렬은 k가 O(n)을 초과하지 않는 경우에 선형시간에 정렬하기 위해 사용하는 것
[계수정렬 코드 개요]
func countingSort(arr: inout [Int]){
var max = arr.max()
var count = [Int](repeating: 0, count: max! + 1)
for i in 0..<input{
count[arr[i]] += 1
}
for i in 0...max!{
if count[i] != 0{
for j in 0..<count[i] {
print(i)
}
}
}
}
참고하였습니다. 감사합니다.
https://m.blog.naver.com/ndb796/221228361368
https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221228342808
https://joycestudios.tistory.com/61
Do it! 알고리즘 코딩 테스트 자바 편
728x90
'Swift 코딩테스트 > Swift 알고리즘' 카테고리의 다른 글
| [Swift 알고리즘] 탐색 알고리즘 (1) | 2022.09.02 |
|---|---|
| [Swift 알고리즘] 그래프의 표현 (0) | 2022.06.15 |