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

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

2750번: 수 정렬하기

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

typedef struct TwoInt {
	int n1, n2;
}TwoInt;

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

TwoInt divideNumsWithPivotAndGetBoundaries(int* nums, int left, int right, int pivot) {
	int i;
	int length = right - left + 1;

	// Set newNums
	int lp = 0;
	int rp = length - 1;
	int* newNums = malloc(sizeof(int) * length);

	for (i = left; i < right + 1; i++) {
		if (nums[i] < pivot) newNums[lp++] = nums[i];
		else if (nums[i] > pivot) newNums[rp--] = nums[i];
	}

	// Set a res
	TwoInt res;
	res.n1 = left + lp;
	res.n2 = left + rp;

	// Fill newNums with a pivot
	for (i = lp; i < rp + 1; i++)
		newNums[lp] = pivot;

	// Deepcopy
	for (i = 0; i < length; i++)
		nums[left + i] = newNums[i];

	// Free a used array
	free(newNums);

	return res;
}

void doQuickSort(int *nums, int left, int right, int length) {
	if (left >= right || left < 0 || right > length-1) return;
	int pivot = nums[(left + right) / 2];

	TwoInt boundaries = divideNumsWithPivotAndGetBoundaries(nums, left, right, pivot);

	doQuickSort(nums, left, boundaries.n1 - 1, length);
	doQuickSort(nums, boundaries.n2 + 1, right, length);
}

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
	doQuickSort(nums, 0, N - 1, N);
	printNumbers(nums, N);

	// Free
	free(nums);

	return 0;
}

 

doQuickSort()에서, pivot을 정한 뒤 이것을 기준으로 배열을 (pivot 미만 / pivot과 같은 값 / pivot 초과)로 나눈다.

이것은 divideNumsWithPivotAndGetBoundaries() 함수를 통해 수행된다. nums를 순차적으로 돌면서, pivot과 비교하여, less or greater일 경우 각각 newNums의 앞부분, 뒷부분에 채워넣어준다.

이 작업을 마치고 난 뒤의 상태에서, lp와 rp의 인덱스는 pivot으로 채워져야할 start, end 인덱스가 된다. 이 값은 함수가 끝난 뒤에 반환하게 되는데, 이것을 통해 필요없는 연산을 줄일 수 있다. 가령, pivot이 5여서 3122 / 5555 / 9779가 되었을 경우에 다음 퀵정렬 함수를 3122, 9779에 적용함으로써 필요 없는 연산을 줄이게 된다.

다시 돌아와서, lp, rp의 값을 참조하여 newNums의 lp~rp의 값을 pivot으로 채워준 뒤, nums로 깊은 복사를 해주면 된다.

 

이렇게 divideNumsWithPivotAndGetBoundaries() 함수를 통해 pivot을 기준으로 배열을 나누게 되었으며, split된 배열에서 좌우의 것에 대해 각각 재귀 함수를 호출해준다.

 

시간 복잡도: O(n^2), 하지만 확률상 O(nlogn)이 평균적이다.

공간 복잡도: O(n)

안정성: 불안정, lp, rp를 각각 증가, 감소시키며 값을 넣어주는 것과 pivot값으로 채워주는 것으로 인해 안정성이 깨진다.