컴퓨터알고리즘#6

LeeMir, 24 March 2021

우선순위 큐

우선순위 큐 ADT
  • 항목들을 저장
  • 각 항목 : (키, 원소) 쌍
  • 응용
    • 탑승 대기자
    • 옥션
    • 주식시장
  • 주요 메쏘드
    • insertItem(k, e) : 키 k인 원소 e를 큐에 삽입
    • element removeMin() : 큐로부터 최소 키를 가진 원소를 삭제하여 반환
  • 비교 가능한 원소 집합을 정렬하는데 우선순위 큐 이용 가능
  • 배열로 구현할 경우
    • 정렬이 안되어 있는 상태
      • 삽입 : O(1)
      • 삭제 : O(n)
    • 정렬이 되어있는 상태
      • 삽입 : O(n)
      • 삭제 : O(1)
제자리 정렬

  • 원래 리스트 자체를 위한 공간 이외에 O(1) 공간만을 사용한다면 제자리에서 수행한다고 말함

  • 제자리 선택 정렬 알고리즘
    • 원소들을 순차적으로 탐색하면서 최솟값의 위치와 swap해서 정렬함
  • 제자리 삽입 정렬 알고리즘
    • 원소들을 순차적으로 탐색하면서 적절한 위치에 삽입해서 정렬함