계수 정렬(Count Sort)
작은 정수인 키에 따라 객체를 수집하는 것
특징
- 정수 정렬
- 양의 정수여야 함
- 비교없이 정렬
- 실행 시간은 항목의 수, 키 값의 최대-최소 차이에 선형적 => 키의 다양성이 항목 수보다 상당히 크지 않을 때에 적절
- 기수 정렬의 서브 루틴으로 종종 사용
복잡도
- 최악: O(n+k)
방법
- 각 숫자가 몇 개 있는지 세기 -> 계수 배열
- 계수 배열을 누적합으로 만들기 ex) arr[i] = arr[i] + arr[i-1]
- 정렬되지 않은 배열의 마지막 요소부터 누적합 배열의 자리를 인덱스로 하도록 새로운 배열에 넣기
코드
func countingSort(_ array: [Int], with max: Int) -> [Int] {
var countingArray = Array(repeating: 0, count: max + 1) // 계수 배열
var sortedArray = Array(repeating: 0, count: array.count) // 정렬된 값을 넣을 배열
for element in array {
countingArray[element] += 1 // 해당 숫자인 인덱스의 값을 +1
}
for i in 1..<countingArray.count {
countingArray[i] += countingArray[i-1] // 누적합 배열로 만들기
}
for j in stride(from: array.count - 1, through: 0, by: -1) {
let sortingValue = array[j] // 정렬할 값 = 인덱스가 될 값
sortedArray[countingArray[sortingValue] - 1] = sortingValue // 정렬한 배열[누적합 배열[정렬할 값] -1]
countingArray[sortingValue] -= 1 // 정렬했으니 해당 부분의 누적합을 -1
}
return sortedArray
}이분 탐색(Binary Search)
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 방법
단점
- 정렬된 리스트에서만 사용할 수 있음
장점
- 검색이 반복될 때마다 찾을 확률이 두 배가 되어 속도가 빠름
방법
- 중간 값을 임의 값으로 선택
- target과 비교해 크면 오른쪽(+)에서 중간 값을 작으면 왼쪽(-)에서 중간 값을 선택해 다시 비교
- target과 같으면 반환
코드
func binaarySearch(_ array: [Int], target: Int) -> Int {
var start = 0
var end = array.count - 1
while start <= end {
let mid = (start + end) / 2
if array[mid] == target {
return mid
} else if array[mid] < target {
start = mid + 1
} else {
end = mid - 1
}
}
return 0
}
iOS Developer