[알고리즘] 비교기반 정렬의 한계/비교에 기반하지 않은 정렬

비교 기반 정렬의 시간복잡도 한계

위 트리는 이진 트리이다. (크기 비교에 따른 두 가지 경우의 수)

트리의 리프 수 L은 n개의 값을 정렬하는 모든 경우를 포함한다.

• L = n! ≤ 2^h
• h ≥ log L = log(n!)
• (n/2)^(n/2) ≤ n! ≤ n^n
• log(n!) = Ω(n log n)

따라서 두 원소의 비교에 기반한 정렬 알고리즘은 Ω(n log n)보다 빠를 수 없다.

 

 

비교에 기반하지 않은 정렬 1 : 버킷 정렬

• 정렬될 데이터가 자릿수 개념이 있다면, 이를 이용한다.
• 예를 들어 정렬될 데이터가 택배 주소(~시 ~구 ~동)라면, 처음 위치(~시)만 보고도 데이터 분류가 가능.
  • 분류한 데이터를 각각 정렬하고, 이를 이으면 정렬 완료
• 시간 복잡도 :
  • Best = c개의 버킷으로 모든 원소가 균등하게 배분되어 각각 n/c개가 들어갔을 때,
  • n/c개를 O(n/c log (n/c)) 시간에 정렬, 이 c개의 버킷을 다시 합치면 c(n/c) log(n/c) = n(log n/c) = n(log n - log c)
  • Worst = 하나의 버킷으로 모든 원소가 몰렸을 때, 이 경우는 버킷을 사용하지 않은 것과 동일하다.

 

# stable sorting

• 둘 이상의 키로 이루어진 데이터를 정렬할 때 발생하는 문제.
• 순서쌍 (a, b)의 앞 기준 정렬 vs 뒤 기준 정렬
• 앞/뒤 기준 정렬 모두 수행 시, 순서가 바뀔수도 있고 안바뀔수도 있음

ex) 2차원 좌표계의 점들을 다음 기준에 따라 정렬하자.

1. x좌표에 따라 오름차순으로
2. 만약 x좌표가 같다면 y좌표에 따라 오름차순으로 정렬하여라.

# 정렬 방법과 stable 여부

• 퀵 정렬
  • 정렬 기준이 맨 처음 원소라면 stable
  • 아니라면 정렬 기준과 원래 원소의 위치를 고려해야 함
• 버블 정렬
  • stable. 두 키 값이 같을 때 위치를 바꾸지 않음
• 삽입 정렬
  • stable
• 병합 정렬
  • stable
• 힙 정렬
  • not stable. 순서 정보가 힙에 들어갈때 파괴됨.
• 기수 정렬
  • stable

 

비교에 기반하지 않은 정렬 2 : 기수 정렬 (radix sort)

완전히 비교를 제외한 정렬.

낮은 자리에서 높은 자리로 기준을 바꾸어가면서 정렬함.

• 실제 정렬이라기 보다는, 0~9까지의 버킷에 숫자를 넣어간다는 개념
• 리스트를 차례로 읽어나가면서 순서를 지키므로 stable
• 시간 복잡도 : 숫자가 r 자릿수이고 정렬될 수가 n개일 때 → O(rn)

 

비교에 기반하지 않은 정렬 3 : 계수 정렬 (counting sort)

범위가 작은 수들을 빠르게 정렬.

1. 각 수가 나온 횟수를 센다.
2. 1의 결과를 이용하여 각 수보다 작은 숫자가 몇 개 있는지 센다.
3. 2의 결과로, 특정한 수가 시작하는 위치를 알 수 있다.

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

• 시간 복잡도 : n개의 숫자를 정렬하는데 걸리는 시간은 O(n)
  • 각 숫자가 나온 횟수를 세는데 O(n)
  • 이는 숫자들의 범위가 좁아서 O(1) 시간에 찾아갈 수 있기 때문
  • 다시 숫자를 정렬될 리스트에 채워넣는데에 O(n)
• 만약 숫자들의 범위가 크다면?
  • (최댓값 - 최솟값)의 범위 수마다 항목 하나가 필요
  • S가 숫자 나온 횟수를 세는 테이블이라면, 이 테이블을 다시 읽어야하므로 정확한 시간 복잡도는 O( n+|S| )

 

 

선택 문제

• 주어진 n개의 원소 중에서, 크기 순으로 k번째 원소를 찾는 문제
• 해법 : 원소를 크기 순으로 정렬하면 바로 풀 수 있다.
• 정렬은 선택보다 어려운 문제.(모든 원소의 순서를 정하기 때문이다.) 정렬에 걸리는 시간 O(n log n)보다 빨리 풀 수 있는가?

1. 퀵 정렬의 응용
   • 기준 등수가 k등 일때, 기준이 원하는 답.
   • 기준 등수가 k보다 클 때, 기준보다 작은 원소들 중에서 k등을 고르면 된다.
   • 기준 등수가 k보다 작을 때, 기준보다 작은 원소들이 a개 있다면, 기준보다 큰 원소들 중에서 k-(a+1)등을 고르면 됨 (이 원소의 왼쪽에 a+1개의 원소 존재)
2. 퀵 정렬에서, 항상 한 기준 원소의 등수가 결정됨.

• 시간 복잡도 : 기준값에 의해서 어떻게 범위가 나누어지는지에 따라 다름
  • Best : T(n) = T(n/2) + n = O(n)
  • Worst : T(n) = T(n-1) + n = O(n^2)
• 극단적인 경우 T(n) = T((99/100)n + n) = O(n)