우선순위 큐(Priority queue)

• [ 목차 ]

• 우선순위 큐 ADT
• 우선순위 큐를 이용한 정렬
• 제자리 정렬
• 선택 정렬과 삽입 정렬 비교

• 우선순위 큐 ADT
• 우선순위 큐를 이용한 정렬
• 제자리 정렬
• 선택 정렬과 삽입 정렬 비교

• 우선순위 큐란 무엇일까 ?

• 우선순위 큐는 각 항목에 대해 ( 키, 원소 ) 쌍으로 저장되는 자료구조다.
• 일반적인 큐와 달리 들어오는 순서 (FIFO)가 아닌 일정한 키 값의 기준에따라서 큐 안에 데이터가 정렬되서 사용한다.

• 우선순위 큐 ADT 메쏘드

• 주요메쏘드
  
  • InsertItem(k,e) : 키 k인 원소 e를 큐에 삽입
  • element removeMin( ) : 큐로부터 최소 키를 가진 원소를 삭제해서 반환
    ( removeMax( ) 로 하냐 removeMin( )으로 하냐에 따라 우선순위의
    내부적인 정렬 상태가 내림차순 or 오름차순으로 결정된다. )
• 일반 메쏘드
  • integer size( ) : 큐의 항목수를 반환
  • boolean isEmpty( ) : 큐가 비어 있는지 여부를 반환
    ( 비어있으면 0(false), 그렇지 않으면 1(true) 리턴 ( 사용자 구현에 따라 이는 달라 질수 있다. )
•  접근 메쏘드
  • element minElement( ) : 큐에 최소 키를 가진 원소를 반환
  • element minKey( ) : 큐에서 최소 키를 반환
• 예외처리
  • emptyQueueException( ) : 비어 있는 큐에 대해 삭제나 원소 접근을 시도 할 경우 발생
  • fullQueueException( ) : 가득 찬 큐에 대해 삽입을 시도할 경우 발생
    ( 주로, 배열을 통한 우선순위 큐를 구현했을 경우 자주 발생한다. )

• 일반적(generic)인 우선순위 큐를 이용한 정렬

[ pseudocode ]
---------------------------------
Alg PQ-Sort(L)
	input list L
    Output sorted list L
    
P <- empty priority queue
while(!L.isEmpty())
	e <- L.removeFirst()
    P.insertItem(e)		// ★
while(!P.isEmpty())
	e<- P.removeMin()	// ★
    L.addLast(e)
return
----------------------------------
★로 표시한 부분, 외부 리스트 P 를 하나두고, 기존의 리스트 L의 요소들을 하나씩 빼내어 insertItem과
P에 들어간 요소들을 삭제하면서, 다시 원본리스트 L에 최소값을 넣어주는식의 방식 
( 이는 오름차순 정렬인 상황, 만약 내림차순으로 우선순위큐를 정렬시에는 removeMax()라는 함수가 필요할 것 )

• 여기서 일반적(generic)함수란 ?

• 함수의 인자타입,반환타입 상관없이 여려가지 타입에도 작동하는 함수

• 리스트에 기초한 우선순위 큐

• 무순리스트로 구현
  • 우선순위 큐의 항목들을 리스트에 임의 순서로 저장
  • [ 성능 ]
    • InsertItem : O(1) 시간 소요.
      => 항목을 리스트의 맨 앞 또는 맨뒤에 삽입할 수 있기 때문이다.
    • removeMin, minKey, minElement ( Max도 해당 ) : O(n) 시간 소요
      => 최소(최대) 키를 찾기 위해 전체 리스트를 순회해야 하기때문.
    • 비유하면, 시험지를 겉을 때는 막 쌓으면서 걷음.
      후에 시험지를 정리할 때 순서(ex.학번)에 맞게 정리
• 순서리스트로 구현
  • 우선순위 큐에 항목들을 리스트에 키 정렬 순서로 저장
  • [ 성능 ]
    • InsertItem : O(n) 시간 소요.
      => 항목을 삽입할 곳을 찾고 넣어야하기 때문.
    • removeMin,minKey, minElement ( Max도 해당 ) : O(1) 시간 소요
      => 최소(최대) 키가 리스트의 맨앞에 이미 정렬되어 있으므로.
    • 비유하면, 시험지를 걷을 때부터 (ex.학번)순서대로 정리하고
      후에는 이미 정리했으므로 순설대로 쓰기만 하면 된다.

• 선택 정렬 ( Selection-Sort )

• PQ-Sort의 일종
• 우선순위 큐를 "무순리스트"로 구현
• [ 실행시간 ]
  • n회 InsertItem 작업을 사용해서 원소들을 외부에 우선순위 큐에 삽입하는데 O(n) 시간 소요
  • n회의 removeMIn(Max) 작업을 사용하여 원소들을 우선순위 큐로 부터 정렬 순서로 삭제하면서 원래의 리스트에 다시 넣는다.
    n + (n-1) + (n-2) + ... + 2 + 1
  • Total : O(n^2)

• 삽입정렬 ( Inserttion Sort )

• PQ-Sort의 일종
• 우선순위 큐를 "순서리스트"로 구현
• [ 실행시간 ]
  • n회의 InsertItem 작업을 사용하여 원소들을 우선순위 큐에 삽입하는데 다음 비례하는 시간 소요. 애초에 기존 리스트에서 우선순위 큐에 넣을 때 우선순위에 맞게 넣어야하기 떄문이다.
    1 + 2 + ... + (n-2) + (n-1) + n
  • n회의 removeMin(Max) 작업을 사용하여 원소들을 우선순위 큐로부터 정렬 순서로 삭제하는데 O(n)시간 소요
  • Total : O(n^2)

 

• 제자리 정렬 ( In-Place Sort )

• 선택정렬,삽입정렬 모두 O(n) 공간을 차지하는 "외부의" 우선순위 큐를 사용하여 리스트를 정렬했다.
• 만약, 원래 리스트 자체를 위한 공간 이외에 O(1) 공간만을 사용한다면
  이를 "제자리(In-Place)"에서 수행한다고 말한다.
  = ★ 정렬 ( 리스트 내 ) 영역을 조정해 간다 생각하자.
• 일반적으로, 어떤 정렬 알고리즘이 정렬 대상 개체를 위해 필요한 메모리에 추가하여 오직 "상수 메모리"만을 사용한다면, 해당 정렬 알고리즘이 "제자리"에서 수행한다고 말한다.

• 제자리 선택 정렬 ( In-Place Selection-Sort )

• Selection-Sort가 외부 데이터구조를 사용하는 대신, "제자리"에서 수행하도록 구현 가능
• ★ 우선순위 큐 : 입력 리스트의 일부 ( 초록색 점선부분 )

• 제자리 선택정렬을 위해서는
  • 이 설명에 경우, 리스트의 앞부분을 정렬 상태로 유지
    ( 사용자 기준에 따라, 뒷부분을 정렬 상태로 유지해도 된다.
  • 리스트를 변경하는 대신에 SwapElements를 사용한다.

• 제자리 삽입 정렬 ( In-Place Insertion-Sort )

• Insertion-Sort가 외부 데이터구조를 사용하는 대신, 제자리에서 수행하도록 구현 가능
• ★ 우선순위 큐 : 입력 리스트의 일부 ( 초록색 점수부분 )

• 제자리 삽입정렬을 위해서는
  • 이 설명에 경우, 리스트의 앞부분을 정렬 상태로 유지
    ( 사용자 기준에 따라, 뒷부분을 정렬 상태로 유지해도 된다.
  • 리스트를 변경하는 대신 SwapElements를 사용한다.

• 제자리 선택정렬 vs 제자리 삽입정렬

[ pseudocode ]
---------------------------

Alg InPlaceSelectionSort(A)
	input array A of n Keys
    output sorted array A

for pass <- 0 to n - 2
	minLoc <- pass
    for j <- (pass + 1) to n -1
    	if(A[j] < A[minLoc]
        	minLoc <- j
        A[pass] <-> A[minLoc]
    A[pass] <-> A[minLoc]
return

---------------------------

Alg InPlaceInsertionSort(A)
	input array A of n Keys
    output sorted array A

for pass <- 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
return

---------------------------

• C Code

// clock()을 통해 시간 측정할때 현재 코드에 쓴 QueryPerformanceFrequency() => ms 단위로측정
// 외에도, nanosec단위로도 셀수있고, window()함수에서가 아닌 다른 환경에서 측정할수있는 방법도
// 임있을 상기하자.
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <time.h>

int* InPlaceSelectionSort(int* arr, int N);
int* InPlaceInsertionSort(int* arr, int N);
void SwapElement(int* a, int* b);
int* RegularArrangement(int* arr, int N);
int* InverseArrangement(int* arr, int N);

int main()
{
	int N, elem;
	int* arr1 = NULL, * arr2 = NULL;
	LARGE_INTEGER ticksPerSec;
	LARGE_INTEGER start, end, diff;

	srand(time(NULL));
	scanf("%d", &N);
	arr1 = (int*)malloc(sizeof(int) * N);
	arr2 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++)
	{
		elem = rand() % N + 1;	// 그냥 이렇게되면 ,N이 32767이하에 수에서만 랜덤으로
		arr1[i] = elem;			// 입력하기때문에 중복이 많이 발생할 수 있다.
		arr2[i] = elem;		
	}

	// 정배열 , 역배열로 전환
	//arr1 = RegularArrangement(arr1,N);
	//arr2 = RegularArrangement(arr2,N);
	//arr1 = InverseArrangement(arr1, N);
	//arr2 = InverseArrangement(arr2, N);

	// 정렬 되었는지 확인용 출력
	/*for (int i = 0; i < N; i++)
		printf(" %d", arr1[i]);
	printf("\n");
	for (int i = 0; i < N; i++)
		printf(" %d", arr2[i]);
	printf("\n");*/

	QueryPerformanceFrequency(&ticksPerSec);
	QueryPerformanceCounter(&start);
	arr1 = InPlaceSelectionSort(arr1, N);
	QueryPerformanceCounter(&end);

	// 측정 값으로부터 실행시간 계산
	diff.QuadPart = end.QuadPart - start.QuadPart;
	printf("선택정렬 : %.9f ms\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);

	QueryPerformanceFrequency(&ticksPerSec);
	QueryPerformanceCounter(&start);
	arr2 = InPlaceInsertionSort(arr2, N);
	QueryPerformanceCounter(&end);

	diff.QuadPart = end.QuadPart - start.QuadPart;
	printf("삽입정렬 : %.9f ms\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);

	// 선택,삽입정렬결과 출력부분
	/*for (int i = 0; i < N; i++)
		printf(" %d", arr1[i]);
	printf("\n");
	for (int i = 0; i < N; i++)
		printf(" %d", arr2[i]);*/

	free(arr1);
	free(arr2);
	return 0;
}
int* InPlaceSelectionSort(int* arr, int N)	// 제자리 선택정렬
{
	int minLoc, save;
	for (int i = N - 1; i > 0; i--)
	{
		minLoc = i;
		for (int j = i - 1; j >= 0; j--)
		{
			if (arr[j] > arr[minLoc])
				minLoc = j;
		}
		SwapElement(&arr[i], &arr[minLoc]); // 쿼리 퍼포먼스사이 시간측정에 함수를 넣지않고
	}										// 원래의 형태를 넣어주는것이 시간측정에 더 정확
	return arr;
}
int* InPlaceInsertionSort(int* arr, int N)	// 제자리 삽입정렬
{
	int save, j;

	for (int i = 1; i < N; i++)
	{
		save = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > save)
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = save;
	}
	return arr;
}
void SwapElement(int* a, int* b)
{
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}
int* RegularArrangement(int* arr, int N)	// 제자리정렬전에 정배열리스트 만들기 ( by.버블정렬 )
{
	int tmp;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	return arr;
}
int* InverseArrangement(int* arr, int N)	// 제자리정렬전에 역배열리스트 만들기 ( by.버블정렬 )
{
	int tmp;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - 1; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	return arr;
}

• 선택정렬 vs 삽입정렬

• 공통점
  • 전체적으로 O(n^2) 시간
    => 내부 반복문 : O(n) 선형탐색
    => 외부 반복문 : O(n) 패스
  • 제자리 버전은 O(1) 공간소요
  • 구현이 단순
  • 작은 n에 대해 유용 ( n이 클수록 삽입정렬에 관심을 보여야한다. )
• 초기 리스트가 완전히 또는 거의 "정배열"로 정렬된 겨우
  • ★ "제자리 삽입정렬" 이  더 빠르다.
  • 내부 반복문이 O(1)시간 소요
    => 따라서 전체적으로 O(n)시간에 수행된다.
  • 기존 리스트가 "역배열"로 정렬된 경우
    => swapElements 작업이 많이 소요되는경우
  • "제자리 선택정렬" 이 더 빠르다.
    => swapElements 작업이 패스마다 O(1)시간 수행되는데 반해,
    제자리 삽입정렬은 동일한 작업이 패스마다 최악의 경우 O(n)시간
    수행되기 떄문이다. 

• 실제 실행결과 ( 삽입정렬 vs 선택정렬 )

• 분석 결과

• 참고사항

• 실행시간을 측정하는 과정이 코드안에 있다.
  아래는 이에 대한 참고사항을 정리한 내용이다.
  
  

---