[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]);
}

int findMinStartingAt(int* nums, int length, int start) {
	int minIndex = start;
	int	minValue = nums[start];

	for (int i = start+1; i < length; i++) {
		if (nums[i] < minValue) {
			minValue = nums[i];
			minIndex = i;
		 }
	}

	return minIndex;
}

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

void doSelectionSort(int* nums, int length) {
	for (int i = 0; i < length-1; i++) {
		int index = findMinStartingAt(nums, length, i);
		swapNumbers(nums, i, index);
	 }
}

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
	doSelectionSort(nums, N);
	printNumbers(nums, N);

	// Free
	free(nums);

	return 0;
}

 

제자리 정렬을 통해 추가 공간을 사용하지 않고 배열을 정렬하는 선택 정렬 코드이다. 최솟값을 '선택'하여 순차적으로 배열의 앞부터 넣는 식이다.

 

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

공간 복잡도: O(1)

안정성: 불안정, 이에 대해선 하나의 케이스를 생각하면 도움이 된다. {2, 2, 1, 3} -> {1, 2, 2, 3}