[백준] 2750 && Inplace QuickSort구현

퀵소트를 인플레이스로 구현해봤습니다.

퀵소트란  비교연산 기반의 Sorting으로서 Randomized Sorting알고리즘이고 또한 분할 정복이기도합니다.

퀵소트에는 주요한 원소가있는데 Pivot이라는 원소입니다.

이 원소는 퀵소트를 수행시 소팅의 기준이 된다고 할수있는 원소입니다.

퀵소트를 정렬시 피벗의 왼쪽에는 피벗보다 작은값 오른쪽에는 피벗보다 크거나 같은값들로 정렬합니다.

L은 피벗의 왼쪽 리스트 : 피벗보다 작은 원소들의 집합

P는 피벗(원소)

R은 피벗의 오른쪽 리스트 : 피벗보다 크거나 같은 원소들의 집합

InplacePartion을 실행하면

L

P

R

이런식으로 정렬이 되게됩니다.

제 코드에서 Inplace_Partion의 수행방식은

1. 먼저 임의의 피벗을 잡고 맨오른쪽 위치로 보냄 (저는 중간값으로 잡았습니다.)

2. 왼쪽 인덱스에서는 피벗보다 크거 같은값을 만나면 정지

3. 오른쪽 인덱스에서는 피벗보다 작은값을 만나면 정지

4. 오른쪽 인덱스원소와 왼쪽 인덱스원소를 swap

5. 이 과정을 왼쪽인덱스 = 오른쪽인덱스가 될때까지 반복후

6. Pivot보다 작거나 같으면 왼쪽 인덱스를 1증가

7. 맨 오른쪽으로 보냈던 피벗과 왼쪽인덱스를 스왑합니다.

8. 피벗 인덱스를 return

Inplace Partion이이 끝나게되면 배열 내부에서 Pivot의 위치가 정해지게됩니다. (최소한 Pivot은 자기위치를 찾음)

예를 들면 5 4 2 1 3의 경우 파티션을 한번 실행하면 (피벗 = 2)

1 2 3 5 4 이 됩니다 즉  피벗인 2는 자기위치를 찾게됩니다.

그리고 QuickSort함수에서는 분할 정복을 이용해서

L리스트와 R리스트를 각각 정렬시키게 됩니다.

Time Complexity 분석

퀵소트의 최악수행시간 = O(n^2)입니다.

그러나 퀵소트의 평균수행시간 = O(nlogn)입니다.

퀵소트의 경우 대부분 평균수행시간 근처가 나오긴하지만 최악수행시간은 O(n^2)입니다.

코드는 아래 있습니다.

#include 
using namespace std;

void swap(int* a, int* b) {
	int t = *a;
	*a = *b;
	*b = t;

	return;
}

int choosPivot(int left, int right) { // Pivot을  최고 인덱스와 최저인덱스의 중간값으로 잡음
	return left + (right - left) / 2;
}

int InPlace_Partition(int* arr, int left, int right) {
	if (right <= left) return left;

	int Pivot_pos = choosPivot(left,right);
	int Pivot = arr[Pivot_pos]; 

	swap(&arr[Pivot_pos], &arr[right]); // Pivot을 맨오른쪽으로 보냄

	int nright = right - 1;

	while (left < nright) {
		while (left < nright && Pivot >= arr[left]) left++;
		
		while (left < nright && Pivot < arr[nright]) nright--;

		if (left < nright) {
			swap(&arr[left], &arr[nright]);
		}
	}

	if (arr[left] <= Pivot) left++;

	swap(&arr[left], &arr[right]); // 피벗과 low를 바꿈
	for (int i = 0; i <= 4; ++i) cout << arr[i] << " ";
	cout << endl;

	return left;
}

void QuickSort(int* arr, int left, int right) {
	if (left < right) {
		int Pivot = InPlace_Partition(arr, left, right);
		QuickSort(arr, left, Pivot - 1);
		QuickSort(arr, Pivot + 1, right);
	}

	return;
}

int main() {
	std::ios::sync_with_stdio(false);
	int C;

	cin >> C;
	
	int* arr = new int[C + 1];

	for (int i = 0; i < C; ++i) {
		cin >> arr[i];
	}

	QuickSort(arr, 0, C - 1);

	for (int i = 0; i < C; ++i) {
		cout << arr[i] << endl;
	}

	delete[] arr;

	return 0;
}