[ALGORITHM] 20. 퀵 정렬 구현하기

퀵 정렬(Quick Sort)은 토니 호어가 1960년에 개발한 평균적으로 빠른 속도를 가지는 정렬 알고리즘으로

분할 정복(Divide and Conquer) 방법을 사용하며, 배열을 피벗 기준으로 작은 요소들과 큰 요소들로 나누어 각각을 정렬 후

최종적으로 정렬된 부분을 합치는 방식을 사용한다.

 

template<typename T>
int partition(std::vector<T>& data, int left, int right) {

	T pivot = data[left];
	int i = left + 1;
	int j = right;

	while (true) {

		while (data[i] <= pivot && i <= right) {

			i++;
		}

		while (data[j] > pivot && j > left) {

			j--;
		}

		if (i < j) {

			std::swap(data[i], data[j]);
		
		} else {

			break;
		}
	}

	std::swap(data[left], data[j]);

	return j;
}

template<typename T>
void quick_sort(std::vector<T>& data, int left, int right) {

	if (left < right) {

		int p = partition(data, left, right);
		quick_sort(data, left, p - 1);
		quick_sort(data, p + 1, right);
	}
}

 

 

특징

 

1. 불안정 정렬(Unstable Sort) : 동일한 키 값을 가진 원소의 상대적인 순서가 정렬 전후에 유지되지 않을 수 있다.

2. 원소의 이동이 적음 : 일반적으로 다른 O(n²) 알고리즘들 보다 원소의 이동이 적기 때문에 상대적으로 빠르다.

3. 평균 시간 복잡도가 좋음 : 평균적으로 O(n log n)의 시간 복잡도를 가지며, 대다수의 상황에서 좋은 성능을 보여준다.

 

 

장점

 

1. 빠른 속도 : 평균적으로 다른 정렬 알고리즘들보다 빠른 속도를 가진다.

2. 메모리를 효율적으로 활용 : 추가적인 메모리를 필요로하지 않거나 상대적으로 적은 메모리를 사용하므로 효율적이다.

3. 캐시 지역성을 활용 : 데이터를 작은 블록 단위로 정렬하므로 캐시 지역성을 활용하여 더 빠른 속도를 가질 수 있다.

 

 

단점

 

1. 최악의 경우 시간 복잡도가 높음 : 이미 정렬된 배열이나 역순으로 정렬된 배열과 같이 최악의 상황에는

O(n²)의 시간 복잡도를 가지나 요즘은 최적화 기법을 사용하여 O(n²) 시간 복잡도를 가지는 경우가 잘 없음

2. 불안정성 : 동일한 키 값을 가진 원소의 순서가 유지되지 않을 수 있다.