우선순위 큐) 삽입정렬(Insertion Sort) & 선택정렬(Selection Sort)

두 정렬 알고리즘 모두 Priority Queue의 개념을 이용합니다.

§ Priority Queue ADT란?

데이터 항목이 자유롭게 삽입될 수 있는 저장소, 삭제는 키 값에 의해 결정된다.

여기서 키란 가장 작은것 혹은 큰것 과 같이 기준을 제시해줌.

두 정렬을 요약하자면 아래와 같습니다.

-    삽입 정렬은 리스트의 값이 자신의 위치를 찾아서 들어가는 것.

-    선택 정렬은 주어진 위치에 알맞은 값을 찾아서 넣는 것.

§ 분석

-    두 정렬 모두 O()의 전체적인 수행시간을 갖는다.

-    기존의 리스트를 제외하면 O(1)의 추가 상수공간만 있으면 된다.

§ 간단한 C 구현 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE	100

void selection(int *arr);
void insertion(int *arr);

int main(void) {
	int *testArr, *testArr2;	// 정렬되지 않은 리스트

	testArr = (int *)malloc(sizeof(int)*SIZE);
	testArr2 = (int *)malloc(sizeof(int)*SIZE);

	// 시간 세팅 널값
	srand(time(NULL));

	// 1~100 사이의 값으로 초기화
	for (int i = 0; i < SIZE; i++) {
		testArr[i] = (int)(((double)rand() / (double)RAND_MAX * 100 + 1));
		testArr2[i] = (int)(((double)rand() / (double)RAND_MAX * 100 + 1));
	}

	printf("** 삽입 정렬 테스트\n");

	// 초기화된 리스트 (랜덤 리스트)
	printf("* 정렬 전의 리스트\n");
	for (int i = 0; i < SIZE; i++)
		printf(" %d", testArr[i]);

	// 삽입 정렬 (오름차순)
	printf("\n* 정렬 후의 리스트 (오름차순) \n");
	insertion(testArr);
	for (int i = 0; i < SIZE; i++)
		printf(" %d", testArr[i]);



	printf("\n\n** 선택 정렬 테스트\n");

	// 초기화된 리스트 (랜덤 리스트)
	printf("* 정렬 전의 리스트\n");
	for (int i = 0; i < SIZE; i++)
		printf(" %d", testArr2[i]);

	// 선택 정렬 (내림차순)
	printf("\n* 정렬 후의 리스트 (내림차순) \n");
	selection(testArr2);
	for (int i = 0; i < SIZE; i++)
		printf(" %d", testArr2[i]);


	free(testArr);
	free(testArr2);
	return 0;
}


void insertion(int *arr) {
	int save;	// 이번 턴의 체크할 값
	int i, j;

	for (i = 1; i < SIZE; i++) {
		save = arr[i];
		j = i - 1;
		
		// 기존의 체크한 값들을 비교
		// save 보다 크면 하나씩 뒤로 민다
		// => save가 들어갈 위치를 찾는 과정
		while (j >= 0 && arr[j] > save) {
			arr[j + 1] = arr[j];
			--j;
		}
		arr[j + 1] = save;
	}
}

void selection(int *arr) {
	int maxLoc;	// 가장 큰 값의 위치
	int i, j;
	int tmp;

	// 하나 남은 경우는 더 실행할 필요가 없다.
	for (i = 0; i < SIZE - 1; i++) {
		maxLoc = i;

		for (j = i + 1; j < SIZE; j++) {
			if (arr[j] > arr[maxLoc]) maxLoc = j;
		}

		// swap
		tmp = arr[i];
		arr[i] = arr[maxLoc];
		arr[maxLoc] = tmp;
	}
}

§ 실행 화면