우선 순위 큐 정렬(Priority Queue Sort)

우선 순위 큐는 엔트리의 집합을 저장한다.

일반적으로, 엔트리는 (Key , Value)의 쌍으로 구성되며, key가 우선순위를 가르킨다.

Priority Queue ADT

Main Method

-insert(e) : 엔트리 e 삽입

-removeMin() : 가장 작은 키에 해당하는 엔트리 제거

Additional Method

-min() : 가장 작은 키에 해당하는 엔트리 리턴(삭제하지않음)

-size() : 사이즈 리턴

-empty() : 큐가 비었는지 판단

 

우선 순위 큐 정렬 슈도 코드

Algorithm PQ_Sort(S,C)
	input sequence S, comparator C for the elements of S
    Output sequence S sorted in increasing order according to C
    P <- priority queue with comparator C
    while ㄱS.empty()
    	e<- S.front();  S.eraseFront()
        P.insert(e,∅)
    while ㄱP.empty()
    	e<- P.removeMin()
        S.insertBack(e)

1. 연속된 삽입 작업을 통해 요소를 하나씩 삽입한다.

2. 연속된 removeMin() 작업을 통해 정렬된 순서대로 요소를 제거한다.

 

이 정렬 알고리즘의 실행 시간은 우선 순위 큐 구현에 따라 다르다.

 

Sequenced-based Priority Queue

1. 정렬되지 않은 리스트로 구현

- insert는 시퀀스의 시작 또는 끝에 항목을 삽입할 수 있으므로 O(1) 시간이 걸린다.

- removeMin()과 min()은 가장 작은 키를 찾기 위해 전체 시퀀스를 탐색해야 하므로 O(n) 시간이 걸린다.

 

2. 정렬된 리스트로 구현

- insert는 항목을 삽입할 장소를 찾아야 하기 때문에 O(n) 시간이 걸린다.

- removeMin()과 min()은 가장 작은 키가 맨 처음 시작 위치에 존재하므로 O(1) 시간이 걸린다.

 

Selection-Sort(선택 정렬)

- 선택정렬은 우선순위 큐가 정렬되지 않은 시퀀스로 구현된 우선순위 큐 정렬의 변형 알고리즘이다.

1. 우선 순위 큐에 n개의 항목을 삽입하므로 O(n) 시간이 걸린다.

2. removeMin() 연산이 n개인 우선 순위 대기열에서 요소를 정렬된 순서대로 제거하는 데는 1+2+...n에 비례하는 시간이 걸린다.

따라서, 선택 정렬의 실행시간은 O(n^2)이다.

Insertion-Sort(삽입 정렬)

- 삽입 정렬은 우선순위 큐가 정렬된 시퀀스로 구현된 우선순위 큐 정렬의 변형 알고리즘이다.

1. 우선 순위 큐에 n개의 항목을 삽입하는 데는 n개에 비례한 시간이 걸린다.(1+2+...+n)

2. 연속된 removeMin() 작업이 있는 우선 순위큐에서 정렬된 순서대로 요소를 제거하는 데는 O(n)시간이 걸린다.

따라서, 삽입 정렬의 실행시간은 O(n^2)이다.

 

In-Place Insertion-Sort(제자리 삽입 정렬)

- 외부 데이터 구조를 사용하는 대신, 선택 정렬 및 삽입 정렬을 제자리에서 구현 할 수 있다.

- 입력 시퀀스 자체의 일부가 우선 순위 큐 역할을 한다.

- 시퀀스의 초기 부분을 계속 정렬한다.

- 시퀀스를 수정하는 대신 swap을 사용할 수 있다.