[Priority Queue]27. Priority Queue Sorting(우선순위 큐 정렬)

목차

1. Priority Queue Sorting(우선순위 큐 정렬)

2. Selection Sort

3. Insertion Sort

4. In-place Insertion Sort

 

1. Priority Queue Sorting(우선순위 큐 정렬)

 Priority Queue(우선순위 큐)가 중요한 내용을 먼저 꺼내는 ADT이니 만큼, PQ ADT는 들어온 데이터들을 key 값을 기준으로 정렬을 해야합니다. 이를 Priority Queue Sorting이라고 하며, 이를 구현할 수 있는 방법은 다양합니다.

 

 

2. Selection Sort

 Selection Sort(선택정렬)은 PQ-sort의 일종으로, 해당 priority queue가 정렬되지 않는 sequence와 연결되어 있는 구조를 뜻합니다. Selection Sort가 이루어지는 과정은,

 

1) 기존 priority queue에 존재하던 값들을 새로운 sequence P에 원래의 순서대로 옮긴다.

- O(n) 소요

2) sequence P에서 removeMin을 전체 값들의 개수 n만큼 반복하고, 이 값들을 순서대로 기존의 sequence에 옮긴다.

- O(n^2) 소요

- (1+2+3+ ... +n = O(n^2))

 

따라서 총 O(n^2)의 시간이 소요됩니다.

 

 

3. Insertion Sort

 

 Insertion Sort(삽입 정렬) 또한 PQ-sort의 일종으로, 해당 priority queue가 정렬되어 있는 sequence와 연결되어 있는 구조를 뜻합니다. Insertion Sort가 이루어지는 과정은,

 

1) 기존 priority queue에 존재하던 값들을 새로운 sequence P으로 옮긴다.

- 단, sequence P는 sorted sequence, 새로운 수가 들어올때 마다 우선순위대로 해당 위치에 저장된다.

- O(n^2) 소요

- (1+2+3+ ... +n = O(n^2))

 

2) sequence P에 존재하는 값들을 순서대로 기존의 sequence에 옮긴다.

- O(n) 소요

 

 

4. In-place Insertion Sort

 

 In-place Insertion Sort(제자리 정렬 삽입정렬)은 추가적인 sequence를 사용하지 않는 방식을 뜻합니다. 이론상 In-place Insertion Sort과 In-place Selection Sort 모두 가능합니다. 또한 정의상으로는 추가적인 메모리를 아예 사용하지 않는 것이지만, 그 개수가 상수개수 이하이거나, logn일 경우에는 암묵적인 허용이 있고는 합니다.

 위의 그림에서도 알 수 있다 싶이, 기존 배열에서 swap하며 위치를 바꾸는 것이며, 최악의 경우 O(n^2)의 시간이 소요됩니다.