[Algorithm] C++ Quick Sort (퀵정렬)

퀵정렬

• List에서 하나의 피벗을 정하고 이를 기준으로 피벗보다 작은 요소들, 큰 요소들로 두개의 부분 List를 만들어(Divide 분할) 정렬 후 다시 결합(Conquer 정복)을 재귀적으로 반복하는 방법

 

퀵정렬 알고리즘

1. 리스트 안에 있는 한 요소를 피벗(Pivot)으로 설정한다.

2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값(a)을 찾고, 오른쪽에서부터는 피벗보다 작은 값(b)을 찾는다.

3. a와 b를 교한한다.

4. 왼쪽에서부터 찾은 a값의 위치와 오른쪽에서부터 찾은 b값의 위치가 엇갈리지 않을 때까지 2~3번 과정을 반복한다.

5. 엇갈린 경우에는 오른쪽에서부터 찾은 피벗보다 작은 값(b)과 피벗값을 교환한다.

6. 위의 과정에서 한 번의 분할이 이루어졌고, 두 개의 부분리스트에 대해 다시 1번으로 돌아가 과정을 반복한다.

7. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

 

예시

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheQuickSort.html

피벗(pivot) 값을 선택합니다. 

 

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheQuickSort.html

leftmark는 왼쪽 원소로 부터 피벗보다 큰값을 찾고, rightmark는 오른쪽에서 부터 왼쪽으로 이동하며,

피벗보다 작은값을 찾습니다.

이후 leftmark와 rightmark를 교환 해주고, 다시 피벗값을 기준으로 leftmark, rightmark를 찾아줍니다.

 

이 방법을 반복하다 leftmark가 rightmark보다 오른쪽에 위치할때 멈추게된다.

이 시점에서 rightmark의 위치가 분할지점이 된다.

 

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheQuickSort.html

위의 사진은 피벗인 원소 '54'를 기준으로 왼쪽 원소는 작고 오른쪽 원소는 크다는 특징을 가진다.

이후 새로운 피벗을 정해 위의 작업을 반복하는 재귀적 방법을 사용하여 정렬하면 된다.

 

아래 이미지는 퀵 정렬 알고리즘을 막대그래프로 쉽게 이해할 수 있도록 나타낸다.

출처 - https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

 

퀵정렬 특징

• 주어진 원소 이외에 다른 추가 메모리를 요구하지 않는 In-place 알고리즘이다.
• 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다.
• 분할 정복 알고리즘을 기반으로 정렬되는 방식으로, 피벗의 값에따라 하나의 리스트에 비균등하게 나뉜다.
• 일반적으로 병합 정렬(Merge Sort) 보다 빠르다.

 

시간복잡도

• 퀵정렬의 시간복잡도는 O(NlogN)의 시간복잡도를 갖는다.
• Best : O(NlogN)
• Avg  : O(NlogN)
• Worst : O(N^2)

 

관련 알고리즘 문제

https://www.acmicpc.net/problem/3322

3322번: 정렬의 시간복잡도

 

Code

#include <iostream>

using namespace std;

void quickSort(int arr[], int start, int end) {

	int pivot = start; 
	int left = pivot + 1; 
	int right = end; 

	cout << '\t';
	for (int i = 0; i < 9; i++) {
		cout << arr[i] << ' ';
	}
	cout << '\n';
	//더 이상 리스트를 분할할 수 없으면 종료
	if (start >= end)
		return;
	//left와 right가 엇갈릴 때까지 반복
	while (left <= right) {
		for (; left <= end; left++) {
			// 피벗 다음 원소부터(왼쪽부터) 큰값 하나씩 찾기
			if (arr[left] > arr[pivot]) 
				break;
		}
		for (; right > pivot; right--) {
			// 오른쪽부터 시작해서 피벗보다 작은 값 찾기
			if (arr[right] < arr[pivot]) 
				break;
		}
		// 엇갈리지 않았다면 left값과 right값 교체
		if (left < right) {
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		// 엇갈렸다면 right값과 pivot교체
		else {
			int temp = arr[pivot];
			arr[pivot] = arr[right];
			arr[right] = temp;
		}
	}
	/*
	* 나뉘어진 두개의 분할 리스트 들을 재귀적으로 검색하며 실행
	*/
	quickSort(arr, start, right - 1);
	quickSort(arr, right + 1, end);



}


int main() {

	int arr[9] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };
	int arrSize = 9;

	cout << "\tresult" << '\n';
	quickSort(arr, 0, arrSize - 1);



	return 0;
}