퀵 정렬

 

퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 정렬 알고리즘이다.

특정한 값을 기준(pivot)으로 큰 숫자와 작은 숫자를 선택해 서로 교환한 뒤 배열을 반으로 나눈다. 일반적으로 pivot은 첫번째 원소부터 설정된다.

Ex)

pivot을 기준으로 왼쪽에선 큰값을 찾고, 오른쪽에선 작은 값을 찾는다.

 

3 7 8 1 5 9 6 10 2 4

3 2 8 1 5 9 6 10 7 4

3 2 1 8 5 9 6 10 7 4

 

(작은 값의 인덱스가 큰 값의 인덱스보다 작아 엇갈릴 때 작은 값과 pivot이 교환되어 첫번째 분할이 일어남.)

 

1 2 3 8 5 9 6 10 7 4

 

(3을 기준으로하여 왼쪽의 집합과 오른쪽의 집합에서 각각 pivot이 정해진 뒤 정렬을 수행함.)

 

위의 과정 반복

 

1 2 3 8 5 4 6 10 7 9

1 2 3 8 5 4 6 7 10 9

1 2 3 7 5 4 6 8 10 9

1 2 3 6 5 4 7 8 10 9

~

1 2 3 4 5 6 7 8 9 10

 

정렬을 수행했을 때 왼쪽과 오른쪽이 계속 나눠진다.

 

시간복잡도 : 선택, 버블, 삽입 정렬에 비해 훨씬 빠른 분할 정복 알고리즘으로 평균적인 시간복잡도는 O(N*logN)이다.데이터의 개수가 n개이고, 반씩 분할되므로 O(N*logN)이 나오게 된다.

 

그러나, 최악의 경우 O(N^2)이 나오는데 이미 정렬이 되어있는 경우 pivot을 설정하고 분할이 되지않으므로(엇갈릴 때 계속 자기 자신과 스왑하므로) 연산 횟수가 N^2/2번이 나오게 된다. 이러한 경우 삽입 정렬을 사용하는 것이 속도가 빠르다.

 

#include <iostream>

using namespace std;

int n = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void Quick_Sort(int* data, int start, int end) {
	if(start >= end) // 원소가 1개인 경우 
		return; 
		
	int pivot = start; // pivot은 처음에 첫번째 원소로 설정됨.
	int i = start + 1; // 왼쪽 출발 지점 
	int j = end; // 오른쪽 출발 지점 
	int temp;
	
	while(i<=j) { // 엇갈릴 때까지 반복 
		while(data[i]<=data[pivot]) // 피봇 값보다 큰 값을 만날때까지 오른쪽 이동
			i++;
		while(data[j]>=data[pivot] && j > start) // 피봇 값보다 작은 값을 만날때까지 왼쪽 이동
			j--; 
		
		if(i>j) { // 현재 엇갈린 상태면 피봇 값과 교체 
			temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp; 
		}
		else {
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	// 엇갈렸을 때 스왑한 후 분할이 일어나고 다시 왼쪽과 오른쪽에서 퀵정렬이 수행된다. 
	Quick_Sort(data, start, j-1);  
	Quick_Sort(data, j+1, end);
}

int main() {
	Quick_Sort(data, 0, n-1);
	for(int i = 0; i<n; i++) {
		cout<<data[i]<<' ';
	}
}