[알고리즘] Count Sort, Binary Search

계수 정렬(Count Sort)

작은 정수인 키에 따라 객체를 수집하는 것

특징

• 정수 정렬
• 양의 정수여야 함
• 비교없이 정렬
• 실행 시간은 항목의 수, 키 값의 최대-최소 차이에 선형적 => 키의 다양성이 항목 수보다 상당히 크지 않을 때에 적절
• 기수 정렬의 서브 루틴으로 종종 사용

복잡도

• 최악: O(n+k)

방법

1. 각 숫자가 몇 개 있는지 세기 -> 계수 배열
2. 계수 배열을 누적합으로 만들기 ex) arr[i] = arr[i] + arr[i-1]
3. 정렬되지 않은 배열의 마지막 요소부터 누적합 배열의 자리를 인덱스로 하도록 새로운 배열에 넣기

코드

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)

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 방법

단점

• 정렬된 리스트에서만 사용할 수 있음

장점

• 검색이 반복될 때마다 찾을 확률이 두 배가 되어 속도가 빠름

방법

1. 중간 값을 임의 값으로 선택
2. target과 비교해 크면 오른쪽(+)에서 중간 값을 작으면 왼쪽(-)에서 중간 값을 선택해 다시 비교
3. 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
}

---

위키피디아 - 계수 정렬
Counting Sort : 계수 정렬
위키피디아 - 이진 검색 알고리즘