특별한 우선순위에 따라 정렬된 큐
정렬기준 ex) 연소자, 연장자 사전순, 오름차순
각 key 값들을 비교하는 비교 연산자가 정의되어 있어야함
구현방법 : unsorted sequence, sorted sequence, 힙(heap)
PQ 에 저장되는 데이터는 (key, value)쌍으로 구성된 entry(=item) 이다.
key : entry 에서 value를 대표하는 데이터.
value : entry 에서 key값 외에 부수적인 데이터들
종류
메인 기능
insert(e) : 탐색
removeMin() : 삭제
min() : 탐색
부수 기능
시퀀스 S가 빌 때까지 S요소를 우선순위 큐 PQ 에다 삽입
우선순위 큐 P가 빌 때까지 P의 요소를 다시 시퀀스 S에 삽입
Algorithm PQ-Sort(S,C) // S : 비교가능한 시퀀스, C : comparator => 비교자 (비교할 기준)
Input sequence S, comparator C for the elements of S
Output sequence S sorted in increasing order according to C // 출력 : 기준 C에 따라 오름차순으로 정렬된 시퀀스 C
P <- priority queue with comparator C
while ㄱS.empty() // 시퀀스 S에서 원소를 하나씩 뽑아서 우선순위 큐 P에다 넣음
e <- S.front(); // 원소가 n개라면 insert 연산을 n번 시행
S.eraseFront();
P.insert(e, ∅)
while ㄱP.empty() // 우선순위 큐 P에서 원소를 하나씩 추출해서 시퀀스에다 다시 삽입
e <- P.removeMin() // 시퀀스 s에 계속해서 그 다음으로 작은 원소들이 저장됨
S.insertBack(e)
위에서 본 sorting 알고리즘에서 PQ를 배열 또는 링크드리스트로 구현하며, 각 구현은 각각 unsorted 방식과 sorted 방식으로 구현할 수 있다.
각 구현 방법에 따라서 insert, erase 연산들의 시간복잡도가 정의된다.
unsorted list라 하면 unsotred 배열(또는 링크드리스트) 라고 생각하면 된다.
1.unsorted list 로 PQ를 구현
삽입(insert) : O(1)
탐색(min) : O(n)
삭제(removeMin) : O(n)
2.sorted list 로 PQ 를 구현
삽입(insert) : O(n)
탐색(min) : O(1)
삭제(removeMin) : O(1)
3.Selection-sort(선택정렬)
O(n^2)
4.Insertion-sort(삽입정렬)
worst : O(n^2)
best : O(n)
1) 시퀀스 내용을 정렬하지 않고 그대로 PQ 배열에 카피후,
2) 최솟값을 일일이 맨 앞에서부터 비교하면서 찾아내고, 찾아낸 최솟값을 PQ 에서 추출하여 시퀀스에 옮김
3) 시퀀스에는 점차적으로 차곡차곡 오름차순으로 정렬된 결과가 쌓일것임
시퀀스의 원소들을 정렬하지 않고 PQ 배열에다 들어오는 대로 차곡차곡 쌓는다.
(단순히 시퀀스 원본을 그냥 배열에다 그대로 카피하는 것이다)
배열 맨 끝에다 시퀀스에서 건져온 새로운 원소 삽입하면 끝이므로 O(1)
하나의 원소를 insert 하는 것이 O(1) 이므로 n개의 원소를 진행하면 O(n)
정렬안된 배열에서 최솟값을 찾는 과정 : O(n)
맨 처음 원소는 비교를 n-1번 진행
arrayMax 수도코드처럼 currentMin <- arr[0] 해놓고 for문을 돌린다.
2번째 원소는 (n-2)번, 3번째 원소는 (n-3)번, ... 마지막 원소는 1번 진행
1 + 2 + 3 + ... + (n-2) + (n-1) = O(n^2)
(O(n)이 n번 필요하다고 생각해도 됨)
1) 시퀀스에서 하나하나 원소를 PQ 배열에 집어넣을 때마다 계속 정렬된 상태를 유지.
2) 정렬이 완료되면 시퀀스에 PQ 내용을 카피
새로운 원소가 들어오면 자신이 정렬될 적절한 위치를 찾아감
최악의 경우 : O(n)
insert연산을 총 n번 진행하면 1 + 2 + 3 + ... + (n-1) = O(n^2)
cf) Best case : 내가 최댓값일때
( 최초 비교시, 내가 앞 원소 값보다 크면 1번 비교하고 끝임 )
PQ를 unsorted list 로 구현했을 때 활용되는 알고리즘
실행시간 : O(n^2)
단계1) O(n)
- insert 연산 활용 => PQ 배열방에다 카피함
단계2) O(n^2)- O(n^2) 시간에 정렬하면서 동시에 output 으로 출력
- 정렬안된 배열에서 O(n) 시간동안 최솟값을 찾아내고 맨앞에 배치하는 과정을 n번 반복 (정확히는 1+2+3+..(n-1) )
best, average, worst case 모두 O(n^2) 이 걸림
인풋이 시퀀스 방에 있을때 정렬을 위해 PQ 배열 방이 필요할텐데, 선택 정렬은 실제로 코딩할 때는 따로 옆 방을 이용하지 않는다.
단계2를 보면,
PQ 배열 (7, 4, 8, 2, 5, 4, 9) 에서 최솟값 변수 currentMin 에 7을 저장한다.
그러고 7을 계속 비교해 나간다. 7이 4보다 작으므로 4가 최솟값이 된다.
4를 계속 비교해 나가다가 2가 최솟값이 되고, 계속 또 비교해 나가면 최종적으로 최솟값은 2가 되며, 이 값을 시퀀스 S에 삽입한다.
점점 비교횟수가 적어진다.
5번->4번->3번->2번->1번 비교 횟수로 적어짐.
PQ 를 sorted list 로 구현했을 때 활용되는 알고리즘
최악의 경우 O(n^2)
단계1)
단계2)
삽입 정렬은 BEST Case 일때( = 내가 최댓값일때) 비교연산을 딱 1번만 해서 insert 연산이 O(1) 이므로 삽입 정렬을 자주 사용한다!
( 최초 비교시, 내가 앞 원소 값보다 크면 1번 비교하고 끝임 )
데이터 수가 적을때 (ex) 100개 이하일때) 효율적인 알고리즘
평균적인 수행시간 : n^2 / 4
cf) 퀵정렬
시퀀스의 데이터들을 PQ 에 넣을때마다 자신의 적절한 위치를 찾아감
cf) 정확한 정의
In-place sort : 추가적인 공간을 O(1) 만큼만 사용하는 알고리즘 - 사실 암묵적으로 사람들은 O(logn) 까지 허용
Increase sort : 추가적인 공간을 O(1) 이상으로 사용하는 알고리즘 - 위에서 본 알고리즘
(ex. O(n), O(n^2) 만큼의 추가 공간 사용)
PQ 에서 최솟값을 찾아서 시퀀스에 삽입하는 것
- 최솟값을 찾아 맨앞과 자리바꿈, 2번째로 작은 최솟값을 찾아 앞에서 2번째와 자리바꿈, ... 을 반복한다.
ex) PQ : 5-4-2-3-1 일때
과정1) 1-"4-2-3-5" (5-4-2-3-1에서 최솟값을 찾아보니 1이므로, 1과 5를 바꿔줌)
과정2) 1-2-"4-3-5" (4-2-3-5 에서 최솟값을 찾아보니 2이므로, 2와 4를 바꿔줌)
과정3) 1-2-3-"4-5" (4-3-5 에서 최솟값을 찾아보니 3이므로, 3과 4를 바꿔줌)
과정4) 1-2-3-4-5 (변경사항 없음. 4-5에서 4가 최솟값이므로 위치 안옮김.)
시퀀스의 앞부분의 일부를 PQ 로 취급하여 사용
PQ 로 취급되는 시퀀스의 앞부분의 정렬 상태를 계속 유지시켜야 함
스탭이 증가할수록, PQ 로 취급되는 범위가 하나씩 늘려나가짐
i번째 스탭인 경우 앞에서부터 i개의 데이터가 정렬된 상태여야함. 즉 i개 원소를 가지는 PQ 가 취급된 상태
두가지 방법 모두 O(n^2) 시간이 걸리지만, 선택정렬은 항상 (n+1)n/2 시간이 걸리는데에 비해,
(가장 작은 값을 찾기 위해 n번 → n-1 번 → n-2 번 ... 을 무조건 조사해야 하므로)
삽입정렬은
worst : n(n+1)/2 ==> ex) 5-4-3-2-1
best : n ==> ex) 1-2-3-4-5
average : n^2/4
가 걸리므로 성능이 더 좋다고 할 수 있다.