3. 분할정복 - 퀵 정렬

퀵 정렬이란?

퀵 정렬은 병합 정렬과 마찬가지로 분할정복을 이용하여 정렬을 한다. 퀵 정렬은 피벗을 이용한 정렬 방식이다. 피벗은 두 개의 집합을 나누기 위해 생성된 기준으로 피벗보다 작은 것은 왼쪽으로 피벗보다 큰 것은 오른쪽으로 정렬이 된다. 피벗은 어떤 수가 되어도 상관이 없다. 피벗을 기준으로 두 개의 집합을 나누는 분할의 과정을 거치면 다시 피벗을 기준으로 정렬을 한다.   

 

다음은 퀵  정렬을 표현한 예이다.

 

시간복잡도

퀵 정렬은 두 개의 집합으로 분할하는 것과 피벗을 기준으로 정렬하는 것으로 정렬을 수행한다. 두 개의 집합으로 분리하는 시간은 항상 O(n)을 유지한다. 피벗을 기준으로 정렬하는 시간은 자료의 배치에 따라 평균적으로 O(logn)을 유지하고 최악의 경우는 O(n2)까지 시간이 걸린다. 따라서 시간복잡도는 평균적으로 O(nlogn)을 유지하고 최악의 경우 O(n^2)을 유지한다.

 

예제

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

//swap함수 
void change(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

//피벗을 기준으로 정렬하는 과정
void partition(int low, int high, int & pivot, vector<int> &v) {
	int i, j; //i는 이터레이터, j는 피벗이 처음 존재하는 지점
	int pivot_item; //피벗의 위치에 존재하는 원소

	pivot_item = v[low]; //피벗을 제일 처음 원소로 설정
	j = low; //피벗의 처음위치는 시작점
	for (i = low + 1; i <= high; i++) { //피벗 다음 원소부터 반복문 실행
		if (v[i] < pivot_item) { //현재 원소가 피봇보다 작으면
			j++; //피봇의 위치를 한 칸 뒤로 민다.
			change(v[i], v[j]); //현재 위치와 피봇의 위치를 swap한다.
		}
	}
	pivot = j; //피봇의 위치는 j가 최종적으로 도달한 위치가 된다.
	change(v[low], v[pivot]); //제일 처음위치를 피봇으로 잡았으니까 현재 j가 있는 곳과 swap한다.
}

//퀵정렬, 피벗을 기준으로 정렬하고 피봇을 기준으로 두 개의 집합으로 나눈다.
void quicksort(vector<int> &v, int low, int high) {
	if (low < high) { //인덱스 순서는 시작 ~ 끝 지점
		int pivot; //피봇이 원래 들어갈 위치
		partition(low, high, pivot, v); //피봇을 기준으로 정렬을한다.
		quicksort(v, low, pivot - 1); //피봇 앞에 정렬된 내용을 이용하여 퀵정렬을 사용한다.
		quicksort(v, pivot + 1, high); //피봇 뒤에 정렬된 내용을 이용하여 퀵정렬을 사용한다.
	}
}

int main() {
	vector<int> v;
	v.push_back(15);
	v.push_back(22);
	v.push_back(13);
	v.push_back(27);
	v.push_back(12);
	v.push_back(10);
	v.push_back(20);
	v.push_back(25);

	quicksort(v, 0, v.size() - 1);

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
}