[정렬 알고리즘] 퀵 정렬

합병정렬처럼 분할 정복 알고리즘이다.

피벗으로 사용할 원소를 선택하고 주어진 배열을 피벗을 기준으로 분할한다.

피벗을 선택하는 방법에 따른 여러가지 버전의 퀵정렬이 있다.

 

1. 첫번째 원소를 피벗으로 하는 경우
2. 마지막 원소를 피벗으로 하는 경우
3. 랜덤으로 피벗을 선택하는 경우
4. 중앙값을 피벗으로 하는 경우

주요 프로세스는 partition()이다.

주어진 배열과 피벗x 로 분할한다.

x를 정렬되었을 때의 올바른 위치에 두고, 피벗보다 작은 값의 원소들을 피벗보다 앞에 위치시키고 피벗보다 큰 원소들은 뒤에 위치시킨다.

 

퀵정렬(arr[], low, high)

{

    if(low< high){

        partition_index = 분할(arr, low, high);

 

        퀵정렬(arr, low, partition_index - 1);

        //partition_index 는 피벗 원소가 정렬이 된 위치기 때문에 건드리지 않는다.

        퀵정렬(arr, partition_index , high);

    }

}

 

분할(arr[], low, high)

{

    pivot = arr[high];

    i = low;

 

   for(j = low; j < high; j++)

   {

       if(arr[j] < pivot )

       {

             swap arr[i] and arr[j];

             i++;

       }

    }

    swap arr[i] and arr[high];

    return i;

}

 

#include <bits/stdc++.h> 
using namespace std; 

void swap(int* a, int* b) 
{ 
	int t = *a; 
	*a = *b; 
	*b = t; 
} 


int partition (int arr[], int low, int high) 
{ 
	int pivot = arr[high];
	int i = low;

	for (int j = low; j <= high - 1; j++) 
	{ 
		if (arr[j] < pivot) 
		{ 
			swap(&arr[i], &arr[j]); 
			i++;
		} 
	} 
	swap(&arr[i], &arr[high]); 
	return i; 
} 

void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 

		int pi = partition(arr, low, high); 

		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

void printArray(int arr[], int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr) / sizeof(int); 
	quickSort(arr, 0, n - 1); 
	cout << "Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
} 

 시간복잡도

최악 - O(n^2)

최고,평균 - O(n log(n))

 

안정정렬이 아니며 제자리 정렬입니다.

 

"피벗값을 정한뒤 그보다 작은 값은 그앞에 배치, 그보다 큰 값은 뒤에 배치한 후 배치된 서브 배열에서 또다시 피벗을 정하고 반복한다."