Heapsort, Binsort, Radixsort

Heapsort

Heap data structure를 이용하는 sort

max heap을 이용한다면 removemax를 n번하여 정렬한다.

 

removemax의 cost가 원소가 n개 있을 때 O(logn)이 걸리므로 Heapsort의 cost는 다음과 같다.

 

O(n) (Heap을 만드는데 cost) + O(logn) + O(log(n-1)) + O(log(n-2)) + ... + O(log(1)) = O(nlogn)

 

 

Binsort

원소의 범위가 0부터 n-1까지만 있을 때 가능한 Sort.

MaxKey Value를 길이로 가진 배열을 만든다.

그 배열은 원소로 linked list를 가진다.

그러면 정렬할 permutation을 앞에서부터 보면서 해당하는 linked list에 집어넣는다.

예를 들어 permutation이 1, 5, 5, 2, 2, 8이라고 하고, linked list를 원소로 가진 배열을 B라고 하자.

1. B[1]에 있는 linked list에 1을 집어넣는다.

2. B[5]에 있는 linked list에 5를 집어넣는다.

3. B[5]에 있는 linked list의 뒤에 5를 연결한다.

4. B[2]에 있는 linked list에 2를 집어넣는다.

5. B[2]에 있는 linked list의 뒤에 2를 연결한다.

6. B[8]에 있는 linked list에 8을 집어넣는다.

 

총 Cost는 O(n + MaxKeyValue)가 든다. (n은 inputsize)

 

Binsort는 MaxKeyValue가 작다면 Space도 적게 들고 O(n)시간에 정렬할 수 있어 효과가 좋다. 그러나 MaxKeyValue가 크다면 비효율적이다.

 

 

 

Radix Sort

Binsort와 흡사하지만 binsort보다 적은 space를 사용한다.

 

자릿수가 k개인 숫자들을 정렬한다면 k개의 pass를 진행한다.

i번째 pass에서 i번째 자릿수로 정렬을 한다.

 

Radix Sort - array와 linked list 사용

위 그림은 linked list를 사용하였지만 count를 하는 array를 하나 만들어서 하는 radix sort를 구현할 수도 있다.

 

Radix Sort의 Time complexity는 다음과 같다.

O(nk + rk)

n : input size

k : length of each input key

r : radix(위에서는 10)

 

만약에 n개의 구별되는 key가 있다면 key의 길이는 최소 r을 밑으로 하는 logn이다.

따라서 일반적으로 radix sort는 O(nlogn)이다.

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업