우선순위 큐(Priority Queue), 선택정렬과 삽입정렬

msung99·2022년 4월 27일
0
post-thumbnail

우선순위 큐

  • 특별한 우선순위에 따라 정렬된 큐
    정렬기준 ex) 연소자, 연장자 사전순, 오름차순

  • 각 key 값들을 비교하는 비교 연산자가 정의되어 있어야함

  • 구현방법 : unsorted sequence, sorted sequence, 힙(heap)


우선순위 큐 ADT

  • PQ 에 저장되는 데이터는 (key, value)쌍으로 구성된 entry(=item) 이다.

  • key : entry 에서 value를 대표하는 데이터.

    • 유일무이한 데이터
    • 보통은 key값은 중복되지 않는다. (But, 힙에선 중복될 수 있음)
      ex) 학과(컴퓨터공학과, 전자공학과 등)
  • value : entry 에서 key값 외에 부수적인 데이터들

  • 종류

    • min PQ (최소 우선순위 큐) : key가 작을수록 우선순위 높음
    • max PQ (최대 우선순위 큐) : key가 클수록 우선순위 높음
  • 메인 기능

    • insert(e) : 탐색

      • entry e 를 삽입
    • removeMin() : 삭제

      • 우선순위가 가장 높은 key를 가진 entry를 삭제
      • min PQ를 가정했으므로, key 값이 가장 작은 entry를 삭제한다
    • min() : 탐색

      • 우선순위가 가장 높은 key를 가진 entry를 리턴
      • min PQ 를 가정했으므로, key 값이 가장 작은 entry를 리턴
  • 부수 기능

    • size()
    • empty()

PQ를 활용한 Sorting 알고리즘

  • 정렬 기준 C에 맞게 PQ를 활용해서 시퀀스 S를 정렬하는 알고리즘
  • 과정
  1. 시퀀스 S가 빌 때까지 S요소를 우선순위 큐 PQ 에다 삽입

    • 시퀀스 S의 데이터들을 PQ 에다 옮긴다.
    • 대입, 삭제 연산을 n번 실행
    • 실행시간 : n x insert 연산 + n x erase 연산
  2. 우선순위 큐 P가 빌 때까지 P의 요소를 다시 시퀀스 S에 삽입

    • P.removeMin, S.insertBack 을 n번 실행
    • removeMin 을 n번 호출하면 데이터 n가 나오게 되고, 그 데이터들을 차례대로 뒤에다 줄만 세워주면 된다.
    • 실행시간 : n x removeMin 연산 + n x insertBack 연산
  • PQ의 삽입, 삭제(insert, removeMin) 연산의 구현에 따른 실행시간에 따라 시간복잡도가 달라짐
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)

Sequcence 기반의 PQ

  • 위에서 본 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. Selection 정렬 - unsorted list 기반의 PQ 구현

1) 시퀀스 내용을 정렬하지 않고 그대로 PQ 배열에 카피후,
2) 최솟값을 일일이 맨 앞에서부터 비교하면서 찾아내고, 찾아낸 최솟값을 PQ 에서 추출하여 시퀀스에 옮김
3) 시퀀스에는 점차적으로 차곡차곡 오름차순으로 정렬된 결과가 쌓일것임

  • PQ를 unsorted list(unsorted 배열) 로 구현했을때의 실행시간
  1. insert( ) : O(1) => n번 진행하면 O(n)
  • 시퀀스의 원소들을 정렬하지 않고 PQ 배열에다 들어오는 대로 차곡차곡 쌓는다.
    (단순히 시퀀스 원본을 그냥 배열에다 그대로 카피하는 것이다)

  • 배열 맨 끝에다 시퀀스에서 건져온 새로운 원소 삽입하면 끝이므로 O(1)

  • 하나의 원소를 insert 하는 것이 O(1) 이므로 n개의 원소를 진행하면 O(n)


  1. removeMin( ) , min( ) : O(n) => n번 진행하면 O(n^2)
  • 정렬안된 배열에서 최솟값을 찾는 과정 : 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번 필요하다고 생각해도 됨)


2. Insertion 정렬 - sorted list 기반의 PQ 구현

1) 시퀀스에서 하나하나 원소를 PQ 배열에 집어넣을 때마다 계속 정렬된 상태를 유지.
2) 정렬이 완료되면 시퀀스에 PQ 내용을 카피

  1. insert( ) : O(n) => n번 진행하면 O(n^2)
  • 새로운 원소가 들어오면 자신이 정렬될 적절한 위치를 찾아감

    • 정렬된 시퀀스에서 맨뒤의 원소 부터 시작해서 값을 비교해나가며 자리를 바꿔가며 자신이 위치할 곳을 찾아냄
  • 최악의 경우 : O(n)

    • 내가 minimum value 일때
    • 내가 최솟값이면 계속 앞으로 나아가면서 총 n번 비교해야함
  • insert연산을 총 n번 진행하면 1 + 2 + 3 + ... + (n-1) = O(n^2)

    • O(n) 을 n번 진행한다고 생각해도 됨

cf) Best case : 내가 최댓값일때
( 최초 비교시, 내가 앞 원소 값보다 크면 1번 비교하고 끝임 )


  1. removeMin( ), min( ) : O(1) => n번 진행하면 O(n)
  • PQ 에서 정렬이 끝난후 다시 시퀀스에 옮기는 과정(copy 하는 과정) : O(n)
    • removeMin : PQ의 맨 앞 원소를 삭제하는 행위가 곧 최솟값을 삭제하는 행위이다.

Selection-sort (선택정렬)

  • PQ를 unsorted list 로 구현했을 때 활용되는 알고리즘

  • 실행시간 : O(n^2)

    • 1` + 2 + 3 + ... + (n-1)

단계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 배열 방이 필요할텐데, 선택 정렬은 실제로 코딩할 때는 따로 옆 방을 이용하지 않는다.

    • 지금은 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번 비교 횟수로 적어짐.


Insertion-sort (삽입정렬)

  • PQ 를 sorted list 로 구현했을 때 활용되는 알고리즘

  • 최악의 경우 O(n^2)

    단계1)

    • insert할때 자신의 자리를 찾는 O(n)의 과정이 n번 반복
      • 정확히는 1 + 2 + 3 + ... + (n-1)

    단계2)

    • 단계1에서 정렬이 이미 완료된 것을 그대로 시퀀스에 다시 카피해주면 끝.
    • removemMin() 이 O(1) 이므로 O(1) x n = O(n)
  • 삽입 정렬은 BEST Case 일때( = 내가 최댓값일때) 비교연산을 딱 1번만 해서 insert 연산이 O(1) 이므로 삽입 정렬을 자주 사용한다!
    ( 최초 비교시, 내가 앞 원소 값보다 크면 1번 비교하고 끝임 )

  • 데이터 수가 적을때 (ex) 100개 이하일때) 효율적인 알고리즘

  • 평균적인 수행시간 : n^2 / 4

    • 1단계에서 insert 연산을 할때, 자신의 자리가 sorted array의 딱 정중앙에 있을때 insert 연산의 수행시간은 n/2 이 될것이다.

cf) 퀵정렬

시퀀스의 데이터들을 PQ 에 넣을때마다 자신의 적절한 위치를 찾아감


In-place sort (제자리 정렬 알고리즘)

  • 추가적인 메모리할당이 없는 정렬
  • 선택정렬, 삽입정렬 모두 in-place 로 구현가능

cf) 정확한 정의
In-place sort : 추가적인 공간을 O(1) 만큼만 사용하는 알고리즘 - 사실 암묵적으로 사람들은 O(logn) 까지 허용
Increase sort : 추가적인 공간을 O(1) 이상으로 사용하는 알고리즘 - 위에서 본 알고리즘
(ex. O(n), O(n^2) 만큼의 추가 공간 사용)


in-place 선택정렬

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가 최솟값이므로 위치 안옮김.)

  • 위치를 바꾸기 위해 사용하는 상수 크기의 변수 tmp 선언
    • 변수 공간 할당은 O(1) 이다!
  • 자신이 최솟값인 경우 맨 앞 데이터와 서로 위치를 바꾼다
  • 최솟값이 아닌 경우 아무곳에나 위치해도 상관x. 짜피 다음번에 최솟값 다시 찾을것이므로!
  • 그 다음으로 찾은 최솟값(2번째로 작은 값)을 2번째 인덱스에 저장된 값과 바꾼다
  • 계속 동일한 원리로 반복. 그 다음으로 찾은 최솟값을 3번째, 4번째, 5번째, ... 인덱스에 저장된 값과 바꾼다.

in-place 삽입정렬

  • 시퀀스의 앞부분의 일부를 PQ 로 취급하여 사용

  • PQ 로 취급되는 시퀀스의 앞부분의 정렬 상태를 계속 유지시켜야 함

  • 스탭이 증가할수록, PQ 로 취급되는 범위가 하나씩 늘려나가짐

    • 범위가 하나씩 늘어날때마다 새롭게 PQ 범위에 추가된 시퀀스 데이터는 자신의 적절한 위치에 정렬되어야 함.
  • i번째 스탭인 경우 앞에서부터 i개의 데이터가 정렬된 상태여야함. 즉 i개 원소를 가지는 PQ 가 취급된 상태


in-place 삽입정렬 vs 선택정렬

두가지 방법 모두 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
가 걸리므로 성능이 더 좋다고 할 수 있다.

profile
블로그 이전 : https://haon.blog

0개의 댓글