컴퓨터 알고리즘 초급 #7 ( 계수정렬, 기수정렬 ) 선형 정렬 알고리즘

 

비교를 이용하는 정렬

 

지금까지 소개한 모든 정렬들은 비교연산으로 정렬 하였다.

 

비교 연산이란 둘중 누가더 큰지를 비교하여 연산하는 것이다.

 

- 비교정렬의 하한값 

   : 비교연산으로 정렬하는 방법은 아무리 빨라도 오메가(n lg n)보다 느리다.

 

 

1. 계수 정렬

 - 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다.

 

 

0이 몇갠지 세고, 1이 몇갠지 세서

 

3개의 0을 앞에두고 5개의 1을 뒤에 둔다.

 

 

입력된 배열 A에 가장 작은 숫자가 무엇이고, 가장 큰 숫자가 무엇인지를 확인해 보고, 그 배열안에 0이 몇개 1이 몇개 2가 몇개 3이 몇개 를 세야한다.

 

A에서 가장 작은값이 0이고, 가장 큰 값이 5 이므로 6개의 cell 을 가지는 배열을 만들어서, 각 숫자가 몇개인지 세어 배열에 넣어준다.

 

 

 

이런식으로 배열 A의 앞에서부터 세면서 해당하는 숫자를 카운트 해준 값을 배열 c에 넣어준다.

 

 

 

 

결국 작은 숫자부터 큰 수까지 각 숫자가 들어가게 됨.

 

0이 2개 1 : 0개 2 : 2개 3: 3개 4: 0개 5 : 1개

 

이걸 순서대로 풀어주면

 

00223335 --> 정렬 완료.

 

계수 정렬의 특징은 입력 배열의 순서가 정렬 후에도 유지된다.

 -stable 하다 라고 말한다.

 

 

앞에 있던 2가 정렬 후에도 앞에 있다는 뜻

 

 

 

c` 는 배열 c에 있는 값들을 누적해서 만든 것

 

c` = { 2, 0+2 , 2+2, 2+2+3 , 2+2+3+0 , 2+2+3+0+1 }

 

c`[5] = 8 즉 8개의 숫자를 입력받았다는 것을 알 수 있다.

 

 

해당하는 숫자는 정렬 후의 인덱스 값에 해당한다.

 

A배열의 맨 뒤 숫자부터 시작한다. 3 ( 7번째 인덱스에 넣는다. -1)

 

0 ( 2번째 인덱스에 넣는다 -1)

 

3 ( 6번째 인덱스에 넣는다 -1)

 

2 ( 4번째 인덱스에 넣는다 -1)

 

0 ( 1번째 인덱스에 넣는다 -1) == 0

 

3 ( 5번째 인덱스에 넣는다 -1)

 

5 ( 8번째 인덱스에 넣는다 -1)

 

2 ( 3번째 인덱스에 넣는다 -1)

 

최종 결과

배열 B = {

0 0 2 2 3 3 3 5

}

 

정렬완료.

 

k는 입력되는 정수의 범위이다.

전체 수행시간 = O(n+k) 즉 O(n) 

 

서로 비교하지 않고 숫자를 세는 작업만을 해서 선형시간안에 해결할 수 있다. ( 선형배열 )

 

 

계수 정렬이 유리한 경우는, 범위가 좁은 동일한 숫자가 많은 배열일 때 효율적이다.

 

범위가 넓은데 카운터배열에 빈 공간이 많으면 많을수록 불리하다.

 

 

2. 기수정렬 

 

큰 자리에서 작은자리로 이동

 

백의 자리끼리 정렬하고, 십의 자리끼리 정렬하고, 일의 자리끼리 정렬하기

.

 

작은자리에서 큰 자리로 이동

일의 자리끼리 정렬하고, 십의 자리끼리 정렬하고, 백의 자리끼리 정렬하기

 

 

일의 자리가 작은 순서대로 위로 올린다. (0,1,3,4,5,5,6,8)

1. 일의 자리가 작은 순서대로 위로 올린다. (0,1,3,4,5,5,6,8)

 

2. 십의 자리가 작은 순서대로 위로 올린다. (0,0,2,3,3,5,5,9)

 

3. 백의 자리가 작은 순서대로 위로 올린다. (3,4,4,6,6,7,7,8)

 

이렇게하면 정렬된 형태로 재배열 된다.

 

기수 정렬의 특징 stable 하다.

 

시간 복잡도 : (d(n+k))  //  d = 숫자의 자리 수, n = 입력된 숫자 수  k = 각 자리수에서 최대 k값을 가질 수 있다고 가정

 

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

 

 

선형시간 정렬 알고리즘

 

- 계수정렬 알고리즘

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

- 기수정렬 알고리즘

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