C++ 퀵 소트 (빠른 정렬) 구현해보기

퀵 소트 (QuickSort)

 

시간 복잡도 : O(n log n)

최선 : O(n log n)

최악 : O(n log n)

 

정렬이 이미 돼있을 때 최악의 시간 복잡도가 나옴

 

머지 소트와 달리 추가적인 메모리가 필요하지 않음

 

퀵 소트는 동일한 값이 있을 때 순서가 보장되지 않는 unstable sort임

 

머지 소트와 같은 O(n log n)의 시간 복잡도지만 실제 시간은 머지 소트보다 빠름

 

#include "stdafx.h"
#include <iostream>

int const ARRAY_COUNT = 8;

void PrintArray(int arr[], int start, int end, int pivot, int i, int j) {
	for (int k = 0; k < ARRAY_COUNT; k++) {
		std::cout << arr[k] << " ";
	}
	std::cout << "                 s:" << start << " e:" << end << " p:" << arr[pivot] << " i:" << i << " j:" << j << std::endl;
}

void QuickSort(int arr[], int start, int end) {
	int pivot = end - 1;

	if (pivot <= start) {
		return;
	}
	int i = start, j = pivot - 1;
	while (i <= j) {
		if (arr[i] > arr[pivot] && arr[j] < arr[pivot]) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			PrintArray(arr, start, end, pivot, i, j);
		}
		if (arr[i] <= arr[pivot]) {
			i++;
		}
		if (arr[j] >= arr[pivot]) {
			j--;
		}
	}

	if (i != pivot) {
		int temp = arr[i];
		arr[i] = arr[pivot];
		arr[pivot] = temp;
		pivot = i;
	}

	PrintArray(arr, start, end, pivot, i, j);

	QuickSort(arr, start, pivot);
	QuickSort(arr, pivot, end);
}

int main()
{
	std::cout << "QuickSort" << std::endl;
	int arr[ARRAY_COUNT] = { 7, 5, 3, 8, 1, 10, 2, 4, /*9, 6 */ };
	QuickSort(arr, 0, ARRAY_COUNT);
	std::cout << "-------------------------------------------------------" << std::endl;
	for (int k = 0; k < ARRAY_COUNT; k++) {
		std::cout << arr[k] << " ";
	}
	return 0;
}

 

 

결과