알고리즘 이론 8강. 선형 시간(O(n))안에 정렬

 

[정렬의 Lower bounds]

: 앞에서 봐온 정렬들은 "키 비교" 기반으로 이루어진다. ( 정렬에 사용되는 키값 기준으로 비교)

: 이러한 "키 비교" 기반 형태의 정렬의 lower bound는 Θ(nlogn)이다.

 

 

 

[결정 트리 모델(Decision Tree Model)]

: 우리는 비교 정렬을 결정 트리(Decision Tree)를 사용해서 추상화하여 본다.

: 결정 트리는 특정 정렬 알고리즘을 사용해서 리스트를 정렬할때 가능한 모든 비교를 보여준다.

삽입 정렬의 결정 트리(n = 3)

 

 

 

[원소 n개의 순열(permutations)]

: n!개의 순열 존재

= 결정 트리의 가능한 결과(잎노드의 개수)가 n!개 나온다.

=> root에서 leaf까지의 가장 긴 경로가 알고리즘의 최악 케이스

=> 최악 케이스 수행력은 결정트리의 높이(height)

 

 

 

[최악 케이스의 Lower bound 증명]

- 가설 : 어떠한 비교 정렬 알고리즘은 최악 케이스에서 Ω(nlogn)을 요구한다.

- 증명 :

  이진트리의 높이 h는 최대 2^h 잎을 가진다.

  그래서 결정 트리는 최대 잎이 2^h 이하이다.

  그래서 n! <= l <= 2^h

  그래서 n! <= 2^h

  양쪽에 로그함수를 취한다.

  log(n!) <=h 

  n! > (n/e)^n 이다 (n!에 대한 stirling의 approximation 사용 결과)

  그래서 h >= log(n!) = log(n/e)^n = nlogn-nloge = Ω(nlogn)

 

 

 

[Counting Sort]

: 이제부터 비교하지 않는 정렬 방법

: 입력된 n개의 원소들이 정수고 0에서 특정 정수 k까지의 범위를 가지고 있다 가정해라.

: 각 원소 x에 대해, x이하의 원소개수(누적값)를 확인해라.

 

- 3개의 배열이 필요

  1) 입력 배열 : A[1...n]

  2) 정렬된 배열을 위한 공간 B[1...n]

  3) 각 원소에 대해 확인한 원소개수 저장용 배열 C[0...k]

 

 

 

[Counting Sort 의사코드]

CountingSort(A,B,k)
  for i <- 0 to k
    do C[i] <- 0    # 카운팅 결과 넣을 배열 초기화
  for j <- 1 to length[A]
    do C[A[j]] <- C[A[j]] + 1  # 해당 원소번째에 개수 1 카운팅 추가
  for i <- 1 to k
    do C[i] <- C[i] + C[i-1]   # 누적합
  for j <- lenght[A] downto 1
    do B[C[A[j]]] <- A[j]
      C[A[j] <- C[A[j]]-1      

: 카운팅 정렬 하는법 숙지

- 시간 복잡도 : Θ(n+k) => k = O(n)이므로 최악 케이스는 O(n).

 

 

 

[기수 정렬(Radix Sort)]

: 낮은 자리수부터 비교해서 정렬해 가는걸 기본 개념으로 한다. (카드 정렬 기계에 사용)

: stable sort 여야만 radix sort로 정렬 가능

: 숫자 자리수 다르면, 최대 숫자 크기의 자릿수에 맞추어 숫자 앞에 0넣어준다.

: 수행시간 O(d*n) or O(n) - d는 가장 큰숫자의 자릿수

: 데이터 전체 크기에 기수 테이블 크기만한 메모리 추가로 필요하다

 

- 최악 케이스일때 각 크기 n에 대해 10 bins 필요

- 최선 케이스일때 각 크기 n/10에 대해 10 bins 필요

 

 

 

[기수 정렬의 의사코드]

RADIX-SORT(A,d)
  for i <- 1 to d do
  use a stable sort to sort array A on digit i

 

 

 

[버킷 정렬(Bucket Sort)]

: 수많은 버킷에 배열 요소들을 분산시킨뒤, 각 버킷은 그 뒤로 개별 정렬된다.

 

 

 

[버킷 정렬의 의사코드]

BUCKERSORT(A)
  n <- length[A]
  for i <- 1 to n
    do insert A[i] into list B[floor(nA[i])]
  for i <- 0 to n-1
    do sort list B[i] with insertion sort
  concatenate the lists B[i]s together in order
  return the concatenated lists

: 각 버킷의 정렬 시간 O(1) => 모든 버킷 정렬 시간 O(n)

(각 버킷이 매우 적은 요소(평균 1개)가지고 있을걸 기대한다)