Quick Sort 퀵소트, 퀵정렬

Quick Sort

• 개념

피봇값을 기준으로 피봇값보다 작은 값들을 왼쪽으로 보내고, 큰 값들을 오른쪽으로 보낸다.

그리고 피봇을 기준으로 왼쪽은 그 중에서 피봇을 새로 뽑아서 위를 반복하고, 

오른쪽도 그 중에서 피봇을 새로 뽑아서 위를 반복한다. 

(재귀적인 방법으로 문제를 해결함.)

즉, 데이터를 기준값(pivot)을 중심으로 좌, 우 2개의 부분집합으로 나누고

부분집합의 원소들 중에서 기준값(pivot)보다 작은 원소는 왼쪽, 큰 원소는 오른쪽 부분집합으로 정렬한다.

부분집합의 크기가 더 이상 나눌 수 없을 때까지(부분집합의 원소가 1개 이하) 위를 반복한다.

퀵소트에서 최고의 성능을 발휘하기 위해서는 중간값이 pivot으로 선정되어야한다.

퀵소트에서 pivot이 최솟값이나 최댓값으로 잡히면 최악의 성능을 보인다.

• 시간복잡도

퀵소트는 1회전에서 pivot을 중심으로 작은 값은 좌, 큰 값은 우로 모두 배치해야하기 때문에

전체 원소의 개수 n개를 모두 비교해줘야한다. 따라서 n-1번의 비교가 이루어지지만 간단히 n번의 비교가 이루어진다고 계산해보자.

2회전에서 pivot을 중심으로 좌의 부분집합이 n/2개, 우의 부분집합이 n/2개로 나누어졌다고 가정하였을 때,

좌에 n/2-1번의 비교, 우에 n/2-1번의 비교가 이루어진다. 

다시 n/2, n/2번의 비교가 이루어졌다고 계산하자. 따라서 총 n/2 + n/2 = n 번의 비교가 이루어진다.

3회전에서는 n/4 + n/4 + n/4 + n/4 = n번의 비교가,

4회전에서는 n/8 + n/8 + ... + n/8 = n/8 * 8 = n 번의 비교가 이루어진다. 

이를 몇 회 반복할까?

부분집합 내에 데이터의 갯수가 1개일 때 정렬은 완료된다. 

전체 데이터가 n개일 때 몇 번을 반복해야 각 부분집합의 사이즈가 1이 남을 수 있을까?

=> log_2_n 번! ( log_2_n * n = 1이기때문)

따라서 퀵소트의 시간복잡도는 n * log_2_n 으로 계산된다. O(nlog(n))

그러나 위의 계산은 이상적인 상황이고, 만약 pivot이 중간값이 아닌 전체 데이터의 최솟값 혹은 최댓값으로 잡힐 때는 어떨까?

그럴 경우, pivot을 기준으로 부분집합이 좌로 0개, 우로 n-1개가 배치되고 

전체 데이터의 1/2씩 나눠지지 않는다. 

이런 경우, 시간복잡도는 bubble sort와 동일한 O(n^2)의 결과를 보인다.

따라서 데이터가 균일하지않게 배치되있거나, pivot을 적절하게 잘 뽑아준다면 quick이 훨씬 빠르지만

데이터가 골고루 잘 들어온다는 보장이 없다면 bubble을 사용하는 것이 더 좋다. 

(quick 은 재귀 함수 호출을 여러번하기때문에)

• C언어 구현코드

// _arr : 원소가 들어있는 배열
// _sz : 배열의 크기
//
// _pivot : 피봇의 인덱스
// _left : ㅣ의 시작 위치
// _right : r의 시작 위치
void QuickSort(int *_arr, int _sz,
				int _pivot, int _left, int _right) {

	//l과 r을 변경시켜야 하기 때문에
	int l = _left;
	int r = _right;

	// 탈출조건
	// pivot, left, right가 배열의 크기를 벗어났을 경우
	if ((_pivot < 0 || _pivot>_sz) ||
		(_left < 0 || _left>_sz)||
		(_right < 0 || _right>_sz))
	{
		return;
	}
	
	// 탈출조건
	// _pivot은 _left보다 항상 왼쪽에 있어야 한다. 
	if (_pivot > _left) {
		return;
	}

	// 탈출조건
	// _left는 _right보다 항상 왼쪽에 있어야 한다.
	if (_left > _right) {
		return;
	}

	// 반복
	while (1)
	{
		// l을 이동
		while (_arr[_pivot] > _arr[l] && l < _sz) {
			l++;
		}
		// r을 이동
		while (_arr[_pivot]<_arr[r] && r>0) {
			r--;
		}

		// if (l<r),  swqp
		if (l<r) {
			int temp = _arr[l];
			_arr[l] = _arr[r];
			_arr[r] = temp;
			// 다시 while반복으로 이동
		}
		// if( r > l ), recursive한 후에 종료
		// -> while문의 탈출조건
		else {
			// pivot하고 바꾸고
			int temp = _arr[r];
			_arr[r] = _arr[_pivot];
			_arr[_pivot] = temp;

			// recursive
			// 왼쪽
			QuickSort(_arr,_sz,_pivot,_pivot+1, r-1);
			// 오른쪽
			QuickSort(_arr,_sz,r+1, r+2, _right);

			return;
		}
	}
}

• 실행결과