[컴퓨터 알고리즘 기초] 8. 선형 시간 정렬 알고리즘

오늘의 핵심 내용

비교 정렬의 하한값을 이해하기

비교 정렬을 하지 않는 계수정렬과 기수정렬을 이해하고 선형 수행시간을 확인하기

 

1. 비교 정렬의 하한 값

비교 정렬을 이용하는 정렬

•  지금까지 소개한 정렬 알고리즘은 비교연산으로 정렬을 하였다.
•  비교연산은 두 개의 원소의 관계를 다음 중 하나로 판단하는 것이다.

 

비교 정렬의 하한값(Lower bounds)

•  비교 연산으로 정렬방법은 아무리 빨라도 nlogn보다 느리다.

 

2. 계수 정렬 알고리즘

계수 정렬

• 계수를 이용하여 정렬 - 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다.
• x라는 입력은 x보다 작은 원소의 개수가 i-1개라면 정렬 후에 i 번째에 위치해야한다.
  •  x보다 작은 원소의 개수는 원소의 개수를 세어서 확인할 수 있다.

 

계수 정렬의 특징

• 입력 배열의 순서가 정렬 후에도 유지 된다.
• 이것을 "stable 하다" 라고 한다.

 

퀵 정렬의 pseudo code

 

수행시간

전체 수행시간은 Θ(k+n)

• k는 입력 되는 정수의 범위이다.
• 만약 k=O(n)이라면, 수행시간은 Θ(n)이 된다.

 

기수 정렬

기수 정렬의 예 (MSB -> LSB 큰수에서 작은 자리수로 이동) 

한자리수를 보고 정리를 하고 이후 다음 자리수를 보고 정리하고 하는 방식

 

기수 정렬의 pseudo code

 

기수 정렬의 수행시간은 Θ(d(n+k))

• d 자리 수 숫자 n개가 주어졌을 때 각 자리수에서 최대 k값을 가질 수 있다고 가정
• d가 상수이고 k=O(n)이르모 기수 정렬은 선형시간에 수행