[코딩테스트] Quick Sort(.feat C)

C언어로 하고 싶지는 않지만, 회사에서 C언어로만 코딩 테스트를 볼 수 있어서

quicksort를 C언어로 구현해보겠습니다.

 

Quicksort특징

분할정복(divide and conquer) 알고리즘의 하나로, 일반적인 경우 빠르게 정렬할 수 있는 알고리즘입니다.

일반적인 경우의 시간복잡도는 O(nlogn), 최악의 경우에는 O(n^2)입니다.

* 일반적인 경우 quicksort 진행 횟수가 logn번이며, 각 알고리즘 당 Left, Right Pointer움직이는 데 n번이 소요되므로 nlogn입니다.

* 최악의 경우는 거꾸로 배치

된 경우로, pivot에 의해서 divide되는 덩어리가 없는 경우입니다.

 

Quicksort알고리즘

pivot을 기준으로 왼쪽은 pivot보다 작은 숫자, 오른쪽은 pivot보다 큰 숫자를 배치합니다.

1. 왼쪽 pointer는 가장 왼쪽에서 시작하여 pivot보다 큰 수가 나오는 곳에서 멈추고, 

오른쪽 pointer는 가장 오른쪽에서 시작하여 pivot보다 작은 수가 나오는 곳에서 멈춥니다.

2. L<R이면 왼쪽과 오른쪽을 바꿔줍니다.

3. 왼쪽 Pointer(L)과 오른쪽 Pointer(R)이 엇갈렸을 때, R과 pivot을 바꿔줍니다.

4. 이후 pivot을 기준으로 왼쪽과 오른쪽을 나누어서 다시 quicksort를 진행합니다.

 

왼쪽 작은 덩어리 처리

L,R이 같은 곳에서 시작하지만, L은 Pivot보다 큰 수를 찾아 오른쪽으로 갑니다.

이 때, L>R이 되면서, Pivot과 R을 교환하면서 마무리 됩니다.

코드 C언어

#include <iostream>

void quicksort(int arr[], int s, int e) {
	if (s >= e) {
		return;
	}

	int pivot = s;
	int left = s + 1;
	int right = e;
	while (left <= right) {
		// left를 pivot보다 큰 수를 찾거나, 오른쪽 끝까지 이동시킨다.
		while (e > left && arr[left] <= arr[pivot]) {
			left++;
		}
		// right을 pivot보다 작은 수를 찾거나, 왼쪽 끝까지 이동시킨다.
		while (s < right && arr[right] >= arr[pivot]) {
			right--;
		}

		if (left < right) { 
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		else {
			int temp = arr[pivot];
			arr[pivot] = arr[right];
			arr[right] = temp;
		}
	}
    // 위 과정을 통해서 right위치는 확정이 되기 때문에, right기준 왼쪽, 오른쪽으로 나눠서
    // quicksort를 진행합니다.
	quicksort(arr, s, right - 1);
	quicksort(arr, right+1, e);

}

int main() {
	int arr[11] = { 21,1,4,6,5,10,79,13,14, 20, 43 };

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

	quicksort(arr, 0, 10);
	for (int i = 0; i < 11; i++) {
		printf("%d, ", arr[i]);
	}
	return 0;
}

quick sort를 구현해보았습니다.

quicksort의 start와 end를 정상적으로 잘 입력해줘야한다는 사실을 잊지 마세요~!

ㅜ 그것 때문에 시간을 허비했습니다...ㅎㅎ