9강. 선형시간 정렬 알고리즘

[ 목차 ]

1. 비교정렬

2. 비교정렬의 하한값

3. 계수정렬

4. 계수정렬의 특징

5. 수행시간

6. 기수정렬

7. 기수정렬의 Pseudo Code

8. 기수정렬의 수행시간

 

1. 비교정렬

1) 이전까지의 정렬 알고리즘은 비교연산으로 정렬

2) 비교연산은 두 개의 원소의 관계를 다음 중 하나로 판단하는 것

 

2. 비교정렬의 하한값

1) 비교연산의 정렬방법은 아무리 빨라도 Ω(n log n)보다 느림

 

3. 계수정렬

1) 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록

2) x라는 입력은 x보다 작은 원소의 개수가 i-1개라면 정렬 후에 i번째에 위치해야 함

3) x보다 작은 원소의 개수는 원소의 개수를 세어서 확인할 수 있음

4) 입력 받은 배열에 있는 숫자의 범위를 확인하고 몇 개가 잇는지를 세어보고 정렬하는 알고리즘

5) 시간복잡도 

 

4. 계수정렬의 특징

1) 입력 배열의 순서가 정렬 후에도 유지 = stable

 

5. 수행시간

1) 전체 수행시간

2) k는 입력되는 정수의 범위

3) 만약 k=O(n)이라면 수행시간은

 

6. 기수정렬

1) 입력받은 배열에 있는 숫자를 가 자리끼리 비교하여 정렬하는 알고리즘

2) 자릿수가 큰 자릿수에서 작은 자릿수로 가며 세는 방법

3) 작은 자릿수에서 큰 자리수로 가며 세는 방법

 

7. 기수정렬의 Pseudo Code

 

8. 기수정렬의 수행시간

1) d 자리 수 숫자 n개가 주어졌을 때 각 자리 수에서 최대 k값을 가질 수 있다고 가정

2) d가 상수이고 k=O(n)이므로 기수 정렬은 선형시간에 수행

3) 시간복잡도