(C/C++) 정렬 - 퀵 정렬(Quick Sort) - 안정성 X, O(N log N)

안녕하세요.

오늘은 퀵 정렬을 알아보도록 하겠습니다.

 

1. 퀵 정렬(Quick)이란?

병합 정렬과 비슷하게 배열을 분할 하는 방식으로 진행됩니다.

병합 정렬은 분할하여 재조립 하면서 정렬한다는 느낌이면

퀵정렬은 피벗의 위치를 찾고 분할하고 분할된 값들 중에서 다시 피벗 찾고 하면서 진행 됩니다.

둘다 분할 정복 개념이 들어가 있습니다.

또한 퀵 정렬은 이름 그대로 빠른 정렬 중 하나이며

다른 O(N log N) 정렬 알고리즘과 비교했을때 가장 빠릅니다.

 

2. 퀵 정렬의 특징

안정성 X

평균 O(N log N) 최악 O(N²)의 시간복잡도

정렬된 경우, 역순일 경우 느리고 난수일때 가장 빠릅니다.

 

정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

 

3. 퀵 정렬의 구현

 

#include <iostream>
#include <stdio.h>

void QuickSort(int arrays[], int start, int end)
{
	int startBase = start;
	int endBase = end;

	int temp;
	int pivot = arrays[endBase];		//축 값은 제일 마지막에 있는 값

	while (true)
	{
		while (pivot >= arrays[start] && start < end) start++;		//왼쪽에서 피벗보다 큰 값을 찾는다.
		while (pivot <= arrays[end] && start < end) end--;			//오른쪽에서 피벗보다 작은 값을 찾는다.

		if (start >= end)				//인덱스가 만나면 끝
			break;

		temp = arrays[start];			//위에서 찾은 피벗 기준 큰 값, 작은 값을 스왑한다.
		arrays[start] = arrays[end];	//스왑 후에는 피벗보다 작은 값은 왼쪽, 큰값은 오른쪽에 위치한다.
		arrays[end] = temp;				
	}

	temp = arrays[endBase];				//피벗의 위치를 중앙으로 옮긴다.
	arrays[endBase] = arrays[start];	//스왑 후에는 피벗보다 작은 값은 피벗의 왼쪽, 큰값은 피벗의 오른쪽에 위치한다.
	arrays[start] = temp;				//현재 피벗의 위치는 정렬된 위치

	if (startBase < start)
		QuickSort(arrays, startBase, start - 1);	//왼쪽 정렬
	if (endBase > end)
		QuickSort(arrays, start + 1, endBase);		//오른쪽 정렬
}

 

피벗의 위치는 제일 마지막 값으로 설정 하였고

피벗의 값보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 스왑을 하면서 진행합니다.

인덱스가 만나면 피벗 값 기준 왼쪽 오른쪽으로 잘 위치 되었다는 뜻이 되고

피벗의 위치를 leftIndex 위치의 값과 스왑하여 제자리를 찾아줍니다.

그 후 재귀함수로 피벗 위치를 기준으로 왼쪽 오른쪽을 나눠 배열의 크기가 1이 될때까지 

반복하여 진행하면 정렬이 완료 됩니다!

감사합니다. 

 

다른 정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)