[C] 백준 2750번: 수 정렬하기(삽입 정렬)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

void printNumbers(int* nums, int length) {
	for (int i = 0; i < length; i++) printf("%d\n", nums[i]);
}

void swapNumbers(int* nums, int index1, int index2) {
	int tmp = nums[index1];
	nums[index1] = nums[index2];
	nums[index2] = tmp;
}

void doInsertionSort(int* nums, int length) {
	int i, j;
	for (i = 1; i < length; i++) {
		j = i;
		while (j - 1 >= 0) {
			if (nums[j - 1] > nums[j]) {
				swapNumbers(nums, j - 1, j);
				j--;
			}
			else break;
		}
	}
}

int main() {
	// Input
	int N;
	scanf("%d", &N);

	int* nums = malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
		scanf("%d", &nums[i]);

	// Solution
	doInsertionSort(nums, N);
	printNumbers(nums, N);

	// Free
	free(nums);

	return 0;
}

제자리 정렬 + 삽입 정렬이다. 배열을 [정렬된 부분 / 정렬되지 않은 부분]로 나누며, 왼쪽 부분을 배열 전체까지 확장하는 식이다. doInsertionSort() 함수에서 i번째 원소를 정렬된 부분 내에 '삽입'하는 식이다. 이를 위해, 순서가 올바를 때까지 j를 감소시키면서 swap을 진행하며, 이러한 특성 덕분에 초기 배열이 이미 어느정도 정렬되어 있을 경우 swap 작업이 줄어드는 특징을 갖게 된다.

 

시간 복잡도: O(N^2)

공간 복잡도: O(1)

안정성: 안정