알고 공부. 3) 퀵 정렬

2020/05/28 - [알고리즘 공부하기/정렬] - 알고 공부. 2) 삽입 정렬

알고 공부. 2) 삽입 정렬

퀵 정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN)이다.

선택, 버블, 삽입 저렬에 비해 엄청나게 빠른 시간복잡도이다.

 

퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할하는 식으로 빠르게 정렬을 한다.

쉽게 말해 특정 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

 

퀵 정렬에는 기준 값이 있다. 이를 피벗이라고 한다.

 

일반적으로 가장 앞에 있는 숫자를 피벗 값으로 설정을 한다.

문제 - 오름차순 정렬하기

문제에서 피벗값은 4이다.

4를 기준으로 1부터 오른쪽으로 이동하며 피벗 값보다 큰 값을 찾고

4를 기준으로 10부터 왼쪽으로 이동하며 피벗 값보다 작은 값을 찾는다.

큰 값은 5를 찾았고 작은 값은 3을 찾았다. 이 두 개의 값을 바꿔주면 된다.

그리고 또 다시 피벗을 기준으로 값을 찾는다.

찾고 보니 작은 값의 인덱스가 큰 값의 인덱스보다 작아졌다.

이런 상황을 엇갈렸다. 라고 말한다. 이렇게 엇갈린 상황에서는 작은 값과 피벗 값을 교환해준다.

교환된 위치에 있는 피벗 값 4를 정렬이 되었다라고 말 할 수 있다.

이렇게 되면 4보다 왼쪽에 있는 값들은 4보다 작고 오른쪽에 있는 값들은 4보다 크다는 특징을 가지게 된다

이렇게 된 것을 한번 분할이 된 것이다라고 말한다.

 

이제 왼쪽 분할과 오른쪽 분할을 따로 피벗 값을 두고 아까 했던 과정을 반복해준다.

3보다 작은 값은 2이지만 3보다 큰 값은 없다. 이런 경우도 엇갈린 것이기 때문에 2와 피벗 값을 바꿔준다.

이렇게 계속 과정을 겪다 보면 결국에는 모든 숫자가 오름차순으로 정렬이 될 것이다.

 

#include <stdio.h>

void display(int* arr, int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
}

void quickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;
	int pivot = start;
	int i = start + 1; //start보다 1 큰 인덱스에서 비교 시작하니까
	int j = end - 1;
	int tmp = 0;
	while (i <= j) {
		while (i <= end && arr[pivot] > arr[i])
		{
			i++;
		}
		while (j > start&& arr[pivot] < arr[j])
		{
			j--;
		}
		if (i > j) {
			tmp = arr[j];
			arr[j] = arr[pivot];
			arr[pivot] = tmp;
		}else{
			tmp = arr[j];
			arr[j] = arr[i];
			arr[i] = tmp;
		}
	}
	quickSort(arr, start, j);
	quickSort(arr, j + 1, end);
}

int main(void)
{
	int arr[10] = { 4,1,2,5,7,9,3,8,6,10 };
	quickSort(arr, 0, sizeof(arr)/sizeof(int));
	display(arr, 10);
	return 0;
}

 

이미 정렬이 되있는 배열에서 퀵정렬을 사용하면 시간 복잡도가 O(N^2)이 된다.