우선순위 큐 ADT

(key, element) 쌍을 저장

주요 메소드

• insertItem(k, e)
• element removeMin() : 최소 키를 가진 원소 삭제, 반환
• integer size()
• boolean isEmpty()
• element minElement() : 최소 키를 가진 원소 반환
• element minKey() : 최소 키 반환

예외

• emptyQueueException() : 빈 큐에 삭제, 접근 시도
• fullQueueException() : 꽉 찬 큐에 삽입 시도

우선순위큐 정렬의 일반형

아래와 같이 우선순위큐 P를 활용한 정렬을 구현할 수 있다. PriorityQueueSort(L)

여기서 P는 두 가지 특징이 있다.

• 특정한 구현 방법이 정해지지 않은 것으로 가정한다.
  (즉, 큐의 구현 방법에 따라 실행시간이 달라진다.)
• key와 element가 같은 것으로 간주하고, key만을 다룬다.
  (insert, remove할 때 key만 넣고 뺀다. element는 없다고 생각)

Alg PriorityQueueSort(L)
  input list L
  output sorted list L
1. P ← 빈 우선순위 큐      # 정렬에 사용되는 제 2의 공간
2. while(!L.isEmpty())     # L에 있는거 싹 빼서 P에 넣기
     e ← L.removeFirst()
     P.insertItem(e)
3. while(!P.isEmpty())     # P에 있는거 작은순으로 싹 빼서 L에 넣기
     e ← P.removeMin()
     L.addLast(e)
4. return

리스트 기반 우선순위큐 정렬

공통 사항

리스트를 기반으로 우선순위큐를 만들고 정렬 알고리즘을 구현할 수 있다.

• 무순리스트 : 선택정렬에 사용
• 유순리스트 : 삽입정렬에 사용

각 방법으로 구현된 우선순위큐의 성능은 다음과 같다.
무순리스트는 넣을 때 빠르지만 뺄 때 느리다.
유순리스트는 넣을 때 느리지만 뺄 때 빠르다.

  메소드    insertItem   removeMin, minKey, minElement
무순리스트      O(1)                  O(n)     
유순리스트      O(n)                  O(1)            

제 2의 공간을 필요로 하는 정렬

선택정렬, 삽입정렬 모두 PriorityQueueSort로 구현한다.
insertItem, removeMin의 구현만 약간 달라지면 된다.

• 선택정렬 (무순리스트)
  • insertItem : P의 아무데나 넣으면 된다.
  • removeMin : P를 전부 살펴 가장 작은 키를 찾아야 한다.
• 삽입정렬 (유순리스트)
  • insertItem : P의 순서성을 해치지 않게 적절한 위치에 넣는다.
  • removeMin : 오름차순이면 첫 원소가 최소키다. 내림차순이면 마지막 원소가 최소키다.

제자리 정렬

정렬을 위해 O(1)의 공간만 더 사용하는 것을 '제 2의 공간을 사용하지 않는다', '제자리 정렬 한다'라고 말한다.
변수 몇 개 더 쓰는건 O(1)만큼 쓴다고 친다.

• 선택정렬 (무순리스트)

Alg inPlaceSelectionSort()
  input n개 키를 가진 배열 A
  ouput 정렬된 배열 A

1. for pass ← 0 to n-2
      minLoc ← pass
      for j ← pass+1 to n-1		# A[pass]~A[n-1] 사이에 가장 작은것 찾기
        if(A[j] < A[minLoc])
          minLoc ← j
      A[pass] ←→ A[minLoc]		# pass위치와 min위치 스왑
2. return

• 삽입정렬 (유순리스트)

Alg inPlaceInsertionSort()
  input n개 키를 가진 배열 A
  output 정렬된 배열 A
  
1. for pass ← 1 to n-1
     save ← A[pass]
     j ← pass-1
     while( (j>=0) & (A[j]>=save) )
       A[j+1] ← A[j]
       j ← j-1
     A[j+1] ← save
2. return