1. 우선순위 큐와 선택/삽입 정렬 (Priority Queue and Selection/Insertion Sort)

원소와 키가 존재하는 큐. 각 항목이 (키, 원소) 쌍으로 구성됨.

우선순위 큐의 주요 함수

void insertItem(e, k); // 키 k인 원소 e를 삽입
elem removeMin(); // k가 가장 낮은 원소 삭제, 반환
int size();
boolean isEmpty();

elem minElement(); // k가 가장 낮은 원소 반환
elem minKey(); // 가장 낮은 k 반환

우선순위 큐를 활용한 정렬

우선순위 큐를 이용하여 리스트를 정렬할 수 있다.

def PQ-sort(L):
	P = PriorityQueue()
    while(! L.isEmpty()):
    	e = L.pop()
        P.insertItem(e)
    while(! P.isEmpty()):
    	e = P.removeMin()
        L.append(e)
    return L

큐의 구현

큐는 순서가 있는 리스트와 순서가 없는 리스트를 활용하여 구현할 수 있다.

무순리스트

void insertItem(e); // O(1) 시간 소요. 리스트의 앞,뒤 중 아무대나 원소 추가
elem minElement(); // O(n) 시간 소요. k가 최소인 값을 찾아야 함

순서리스트

k에 따라 정렬된 리스트로 구현

void insertItem(e); // O(n) 시간, 넣을 위치를 찾아야 하므로
elem minElement(); // O(1) 시간, 이미 정렬되어 있으므로

무순리스트와 순서리스트 비교

우선순위 큐	insertItem	removeMin	minKey, minElement	정렬 방식
무순리스트	$O(1)$	$O(n)$	$O(n)$	선택 정렬
순서리스트	$O(n)$	$O(1)$	$O(1)$	삽입 정렬

큐를 이용한 정렬

선택 정렬^{Selection Sort}

무순리스트로 구현한 우선순위 큐 사용

• n회의 insertItem을 수행하여 원소를 모두 PQ에 넣는데 n 시간 소요
• n회의 removeMin을 수행하여 원소를 모두 PQ에서 꺼내는데 n에 비례한 시간 소요
  $$ n + (n-1) + (n-2) + \cdots + (1) $$
• 총 $O(n^2)$ 시간 소요

삽입 정렬^{Insertion Sort}

순서리스트로 구현한 우선순위 큐 사용

• n회의 insertItem을 수행하여 원소를 모두 PQ에 넣는데 n에 비례한 시간 소요
  $$ n + (n-1)+(n-2) + \cdots + (1) $$
• n회의 removeMin을 수행하여 원소를 모두 PQ에서 꺼내는데 n 시간 소요
• 총 $O(n^2)$ 시간 소요

제자리 정렬^{In-Place Sort}

원래 리스트 공간 (n개) 이외에 상수 크기의 메모리만을 사용하는 제자리 정렬.
정렬이 외부 우선순위 큐를 사용하는 대신, 제자리에서 정렬이 수행되도록 구현

리스트의 앞부분을 정렬 상태로 유지하며, 뒷부분을 무순 우선순위 큐로 보고 선택 정렬 수행 (Swap을 활용)

def inPlaceSelectionSort(A):
	n = len(A)
	for i in range(0, n-1):
    	minLoc = i
        for j in range(i+1, n):
        	if A[j] < A[minLoc]:
            	minLoc = j
        swap(A[i], A[minLoc])
    return A

def inPlaceInsertionSort(A):
	n = len(A)
	for i in range(1, n):
    	save = A[i]
        j = i-1
        while j >= 0 and A[j] > save: 
        	A[j+1] = A[j]
            j = j-1
        A[j+1] = save
    return A

선택 정렬 vs 삽입 정렬

• 모두 $O(n^2)$ 시간 소요.
  • 내부 반복문: $O(n)$ 선형 탐색
  • 외부 반복문: $O(n)$ 패스
  • 제자리 버전은 $O(1)$ 공간 소요
• 적은 n에 대해 유용

초기 리스트가 거의 혹은 완전히 정렬된 경우 제자리 삽입 정렬이 더 빠르다. (내부 반복문이 $O(1)$ 시간에 소요되어 전체적으로 $O(n)$ 시간이 소요되므로)

swapElements 작업이 비싼 경우에는 선택 정렬이 빠르다. (선택 정렬에서 swap이 $O(1)$ 시간 수행되는데 비해, 삽입 정렬에서는 최악의 경우 $O(n)$회 소요되므로)