[Algorithm] 정렬: 계수 정렬, 선택 문제

+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다.

계수 정렬 (counting sort)

- 범위가 작은 수들을 빠르게 정렬할 때 사용된다.

 

1. 각 수가 나온 횟수를 센다. (자신보다 작은 원소의 개수를 센다.)

2. 1 결과를 이용하여 각 수보다 작은 숫자가 몇 개 있는지 센다. (누적합 이용)

 

ex) {5, 9, 3, 6, 9, 5, 2, 10, 1}

<각 수가 나온 횟수>, <각수보다 작은 수의 개수>, <정렬된 수>

 

< n개의 숫자를 정렬하는 데 걸리는 시간>

1. 하나의 숫자를 찾아갈 수 있는 시간을 Θ(1)이라고 가정할 때, 각 숫자가 나온 횟수를 세는데 Θ(n)

2. 다시 숫자를 정렬된 리스트에 채워넣는데 Θ(n)

=> Θ(n)

 

<숫자들의 범위가 클 때>

ex) {12387, 90123, 39735, 9012344}

- (최대값 - 최소값)의 범위 수만큼 항목이 필요하다.

=> S가 숫자가 나온 횟수를 세는 테이블이라고 하면, 이 테이블을 다시 읽어야 하기 때문에 정확한 시간 복잡도는 Θ(n + |S|) 이다.

---

선택 문제

주어진 n개의 원소 중에서, 크기 순으로 k번째 원소를 찾는 문제이다.

 

- 정렬은 모든 원소의 순서를 정하기 때문에 선택보다 어려운 문제이므로 원소를 크기 순으로 정렬하면 바로 풀 수 있다.

 

정렬에 걸리는 시간 Θ(n logn) 보다 빨리 풀 수 있는 방법은?

 

=> 퀵 정렬의 응용을 통해 풀 수 있다.

 

퀵 정렬에서 항상 한 기준의 원소의 등수가 결정된다.

 

- 기준 등수가 k등일 때: 기준이 원하는 답

- 기준 등수가 k보다 클 때: 기준보다 작은 원소들 중에서 k등을 고른다. (재귀)

- 기준 등수가 k보다 작을 때: 기준보다 작은 원소들이 a개 있다면, 기준 원소보다 큰 원소들 중에서 k - (a + 1) 등을 고른다. (재귀)

def select(arr, k):
# 배열 arr에서 k번째 값을 찾는 함수
    if len(arr) == 1:
        return arr[0]

    pivot = arr[0] # 기준 원소 설정
    left = [] # 기준 왼쪽 배열 (기준 원소보다 더 작은 수)
    right = [] # 기준 오른쪽 배열 (기준 원소보다 더 큰 수)

    for x in arr[1:]:
        if x < pivot:
            left.append(x)
        else:
            right.append(x)

    if len(left) == k - 1: # pivot이 k일 때,
        return pivot # pivot이 답

    elif len(left) >= k: # pivot이 k보다 클 때
        return select(left, k) # left에서 k번째 값을 찾는다.

    else: # pivot이 k보다 작을 때
        return select(right, k - len(left) + 1) # right에서 k - a + 1번째 값을 찾는다. (a는 left 원소 개수)

 

< 시간 복잡도 >

- 기준 값에 의해 어떻게 범위가 나누어지냐에 따라 다르다.

 

가장 좋을 때 (기준 원소가 중앙에 있는 경우)

=> T(n) = T(n/2) + n = Θ(n)

 

가장 나쁠 때 (기준 원소가 한 쪽 끝에 있는 경우)

=> T(n) = T(n-1) + n = Θ(n^2)

 

극단적인 경우 ( 1%와 99%로 왼쪽, 오른쪽이 나뉜 경우)

=> T(n)  = T((99/100)n) + n = T(1) + 100n = Θ(n) (무한 등비 급수 이용)