퀵 정렬(quick sort) c++

정렬 알고리즘의 하나로, pivot을 이용해 해당 값보다 작으면 왼쪽 크다면 오른쪽으로 정렬해나가는 방식이다. 병합정렬과 마찬가지로 재귀함수를 이용한다.

 

 

int Partition(int a[], int start, int end)
{
}

void QuickSort(int a[], int start, int end)
{
}

 

Partition함수는 pivot를 기준으로 정렬하고 다음으로 정렬해야할 인덱스를 반환하는 함수다.

QuickSort는 게속 쪼개어 정렬될 수 있도록 도와주는 재귀함수이다.

 

 

void QuickSort(int a[], int start, int end)
{
	if (start < end)
	{
		int index = Partition(a, start, end);
		QuickSort(a, start, index - 1);
		QuickSort(a, index + 1, end);
	}
}

QuickSort는 a배열의 길이가1이 될때까지 게속 돌게 한다. (길이가 1이면 정렬할 필요 없으니 재귀 함수 탈출)

 

int Partition(int a[], int start, int end)
{
	int pivot = a[end];
	int index = start;

	int temp;
	for (int i = 0; i < end; i++)
	{
		if (a[i] <= pivot)
		{
			temp = a[i];
			a[i] = a[index];
			a[index] = temp;
			index++;
		}
	}

	temp = a[index];
	a[index] = a[end];
	a[end] = temp;

	return index;
}

pivot의 위치 end를 기준으로 정렬을 한다( 꼭 end일 필요는 없다) i번째부터 순차적으로 돌아 pivot보다 작으면 위치를 바꿔준다. index는 바꾸어야 하는 위치를 말한다.

중요한 점은 마지막엔 pivot위치와 index위치를 바꿔야 pivot보다 큰 수들이 정렬된다.

 

 

#include <iostream>
using namespace std;

int Partition(int a[], int start, int end)
{
	int pivot = a[end];
	int index = start;

	int temp;
	for (int i = 0; i < end; i++)
	{
		if (a[i] <= pivot)
		{
			temp = a[i];
			a[i] = a[index];
			a[index] = temp;
			index++;
		}
	}

	temp = a[index];
	a[index] = a[end];
	a[end] = temp;

	return index;
}

void QuickSort(int a[], int start, int end)
{
	if (start < end)
	{
		int index = Partition(a, start, end);
		QuickSort(a, start, index - 1);
		QuickSort(a, index + 1, end);
	}
}

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

	for (int i = 0; i < arrSize; i++)
	{
		cout << a[i] << ", ";
	}

	cout << "\n";

	QuickSort(a, 0, arrSize - 1);

	for (int i = 0; i < arrSize; i++)
	{
		cout << a[i] << ", ";
	}
}