[우선순위 큐] 제자리 정렬(선택정렬, 삽입정렬)

우선순위 큐를 이용한 정렬

: 비교 가능한 원소 집합을 정렬하는데 우선순위 큐 이용 가능

 

 

1. 선택 정렬

- 우선순위 큐를 무순리스트로 구현 (우선순위 큐의 항목들을 리스트에 임의 순서로 저장)

- 실행시간 : O(n^2) (우선순위 큐에 삽입하는데 O(n)시간 소요 + 정렬순서로 삭제하는데 n+(n-1)+(N-2)+... 시간 소요)

 

2. 삽입 정렬

- 우선순위 큐를 순서리스트로 구현 (우선순위 큐의 항목들을 리스트에 키 정렬 순서로 저장)

- 실행시간 : O(n^2) (우선순위 큐에 삽입하는데 n+(n-1)+(N-2)+... 시간 소요 + 정렬순서로 삭제하는데 O(n)시간 소요)

 

3. 제자리 정렬

-리스트 자체를 위한 공간 이외에 O(1) 공간 만을 사용한다면, 이를 "제자리(in-place)"에서 수행한다고 말함

n하고 상관없는 상수 공간이냐 vs n에 따라 달라지는 공간이냐

 

 

제자리 선택 정렬 알고리즘

 

문제: n개의 양의 정수(중복 가능)를 입력받아, 선택 정렬을 이용하여 정렬하는 프로그램을 작성

1. 크기 n인 배열 동적할당

2. 입력 값 저장을 위한 배열 이외에 O(1)의 추가 공간만 사용

3. 배열의 뒷 부분을 정렬 상태로 유지, 매 반복마다 최대 한 번의 교환 연산만 사용

입력 예시 1
8 ↦ n
8 31 48 73 3 65 20 29

출력 예시 1
□3 8 20 29 31 48 65 73 ↦ 정렬 결과

입력 예시 2출력 예시 2
8 ↦ n
73 65 48 31 29 20 8 3

출력 예시 2
□3 8 20 29 31 48 65 73 ↦ 정렬 결과

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void inPlaceSelectionSort(int *A, int n) {// 제자리 선택 정렬
	int j, max, tmp = 0;

	for (int i = n-1; i >= 1; i--) {
		max = i;
		for (j = i - 1; j >= 0; j--) {
			if (A[j] > A[max]) {
				max = j;
			}
		}
		tmp = A[i];
		A[i] = A[max];
		A[max] = tmp;
	}
}

int main() {
	int n;
	int* A;

	scanf("%d", &n);

	A = (int*)malloc(sizeof(int) * n);
	if (A == NULL) {
		printf("Not enough memory!");
		return -1;
	}

	for (int i = 0; i < n; i++) {
		scanf("%d", &A[i]);
		getchar();
	}

	inPlaceSelectionSort(A, n);

	for (int i = 0; i < n; i++) {
		printf(" %d", A[i]);
	}
	free(A);

	return 0;
}

 

 

제자리 삽입 정렬 알고리즘

 

문제: n개의 양의 정수(중복 가능)를 입력받아, 선택 정렬을 이용하여 정렬하는 프로그램을 작성

1. 크기 n인 배열 동적할당

2. 입력 값 저장을 위한 배열 이외에 O(1)의 추가 공간만 사용

3. 배열의 앞 부분을 정렬 상태로 유지, 매 반복마다 최대 한 번의 교환 연산만 사용

입력 예시 1
7 ↦ n
3 73 48 31 8 11 20

출력 예시 1
□3 8 11 20 31 48 73 ↦ 정렬 결과

입력 예시 2
8 ↦ n
73 65 48 31 29 20 8 3

출력 예시 2
□3 8 20 29 31 48 65 73 ↦ 정렬 결과

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void inPlaceInsertionSort(int *A, int n) {
	int j, save, tmp = 0;

	for (int i = 1; i <= n-1; i++) {
		save = A[i];
		j = i - 1;
		while ((j >= 0) && (A[j] > save)) {
			A[j + 1] = A[j];
			j -= 1;
		}
		A[j + 1] = save;
	}
}

int main() {
	int n;
	int* A;

	scanf("%d", &n);

	A = (int*)malloc(sizeof(int) * n);
	if (A == NULL) {
		printf("Not enough memory!");
		return -1;
	}

	for (int i = 0; i < n; i++) {
		scanf("%d", &A[i]);
		getchar();
	}

	inPlaceInsertionSort(A, n);

	for (int i = 0; i < n; i++) {
		printf(" %d", A[i]);
	}
	free(A);

	return 0;
}