알고리즘 ] 3. 퀵 정렬

1. 퀵정렬

- 기준점을 정해서 큰값과 작은 값을 차례로 찾고 옮기면서 수행하는 정렬

- N*LogN 속도로 다른 정렬과 비교해서 우월한 성능

// ConsoleApplication9.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <queue>
using namespace std;

void quickSort(int* data, int start, int end)
{
	if (start >= end) // 원소가 한개인 경우
	{
		return;
	}

	int key = start;
	int i = start + 1;
	int j = end;
	int temp;

	while (i <= j) // 엇갈릴 때까지만 반복
	{
		while (data[i] <= data[key] && i <= end) { // 피벗보다 큰 값을 만날 때까지 이동
			i++;
		}

		while (data[j] >= data[key] && j > start) // 피벗보다 작은 값을 만날 때까지 이동
		{
			j--;
		}

		if (i > j) { // 엇갈렸다면 key과 작은 값을 바꿈
			temp = data[j];
			data[j] = data[key];
			data[key] = temp;
		}
		else { // 엇갈리지 않았다면 큰값과 작은 값을 바꿈
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}

	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}


int main()
{
	int number = 10;
	int data[10] = { 1, 10, 9, 5, 3, 2, 7, 8, 4, 6 };

	quickSort(data, 0, number - 1);

	for (int idx = 0; idx < number; idx++)
	{
		cout << " " << data[idx];
	}

	return 0;
}