[ 알고리즘 ] 22. Counting sort / Radix sort / Bucket sort

Counting sort

Counting sort의 원리는 간단하다.

 

하나의 배열(A)을 Input으로 받고

하나의 배열(B)에 Result를 담고

하나의 배열(C)에 A에 원소별 갯수를 담는다.

 

 

원리는 각 숫자별로 갯수를 count하여

원소별로 자리를 지정해주는 것  

 

ex) 나보다 먼저 온 사람이 5명이면 내 자리는 6번째

 

psuedo code를 보자

 

 

 

 

1~2 :  k = 해당 array에서 가장 큰 값

            0~k까지의 index가 있는 array C를 만든다.

---

---

 

3~4 : A array를 돌면서, A array에 있는 각 숫자를 볼 때마다

         C의 Index(=A에서 읽은 값) 에 +1해준다. 

 

 

결과

A 에서 a라는 item의 갯수

= C[a] 의 값

 

5~6 : 2번째 인덱스부터 시작한다.  자기 자신의 index 앞에 몇 개의 item들이 있는지 파악하는 단계이다.

       만약 본인 앞에 6개의 item이 있으면 본인의 위치는 7번째이다.

 

 

 

7~9 : B에다가 C와 A를 참조해서 정리되도록 넣어준다.

순서가 섞이지 않도록 A의 끝에서부터 돈다. 

 

이유: 같은 key값이어도 순서가 섞이지 않게!  

 

A[a]의 값을 C[a]번 index까지 가도록 B에 담는다.

 

 

 

A의 마지막 inde에서 시작한다 =  3           (7번줄)

→ C[3]을 본다. = 7                                    (8번줄)

→ B의 7번 인덱스에 3을 넣는다.                 "  " 

→ C[3] 의 인덱스를 하나 감소시킨다.       (9번줄)   << 얘가 같은 key끼리의 순서도 지켜줌

 

---

 

Radix sort

 

Sort할 때 고려할 것이 하나가 아닌 것이다.

 

카드로 치면 

클로버 → 다이아몬드 → 하트 → 스페이드 순서가 우선이고

그 안에서 숫자 2~A인 것이다. 

 

따라서 나보다 더 높은 숫자라고 하더라도, Sort의 Significant 의 차이가 나면 우선순위에서 밀려난다.

 

 

 

 

 

어떤 Key를 가지고 먼저 Sort하느냐가 다른데

 

- MSD : 중요한 거 먼저

- LSD : 안 중요한 거 먼저

 

우리는 LSD를 사용할 거다

( * MSD는 Intermediate pile들이 늘어난다.)

( 뿐만 아니라 제대로 된 결과가 안 나온다.)

 

ex) 19 , 26, 33 을 MSD LSD로 sort해봐라 

 

세 자릿수를 LSD로 정리해보자

 

 

우선 1의 자릿수부터 정리해서 이런 결과가 나오고,

 

그 다음은 10의 자릿수까지만 보고 sort를 한다.

(그냥 나머지 숫자는 없다고 생각하고 sort해야 내가 안 헷갈릴 거 같다. 

10의 자릿수까지만 본다고 하면 100의 자리 이상은 다 지워버리고 생각해라) 

 

 

 

 

 

d = digit 숫자

 

따라서 이를 Counting sort를 적용시켜서 한다면

 

[ 1부터 k까지 n개의 숫자가 있을 때 , digit 갯수 = d ]

- Counting sort =  세타 ( n+ k )

- 세타 ( dn + dk )

 

● 특징

 

조건 : Stable해야함!

---

Bucket sort

가정 : n개의 숫자가 0과 1 사이에 있다.

 

원리 : n개의 bucket을 만들고, 각 숫자의 범위는 [0,1] 이고 이에 맞게 Input이 자기 자리를 찾아 들어간다.

 

ex) 들어오기 전부터 1이 들어올 자리 , 2가 들어올 자리, 3이 들어올 자리를 만들어두고

들어올 때마다 hash table처럼 자기 자리를 찾아서 들어가는 것이다.

 

같은 자리에 2명 혹은 자리 수보다 더 들어온 경우 = Collision

 

https://en.wikipedia.org/wiki/Bucket_sort

 

이런 느낌이라고 생각하면 된다.

 

 

 

 

하지만 Worst case는 O(n^2)이 나온다.

 

 

Worst case일 때는 Merge나 Insertion 쓰는 게 낫다.

 

 

요약▼

 

 

 

(출처)

한동대학교 용환기교수님 - 알고리즘