퀵 정렬 알고리즘

오름차순 정렬을 가정했을 때, 피봇이라는 기준값으로 왼쪽에는 기준값보다 작은 부분집합을 형성시키고 오른쪽에는 기준값보다 큰 부분집합을 형성시킨다. 분할정복을 이용하기 때문에 lgN의 깊이만큼 재귀호출을 하고, 깊이마다 배열의 길이인 N만큼 비교하기 때문에 총 평균 시간복잡도는 NlgN만에 정렬시킬 수 있다

 

피봇을 잡는 기준은 다양하며 특정 피봇 위치를 잡았을 때 엄청 좋다라는 것은 없다. 다만 합병 정렬과 달리, 피봇에 따라 비균등하게 부분집합들이 나눠질 수 있기 때문에 unstable-sort로 분류를 한다. 만일 정렬된 배열에 대해서 퀵 소트를 한다고 하면, 퀵 정렬 알고리즘에 따라서 lgN의 깊이가 아닌 N의 깊이만큼 내려가게 된다. 따라서 최악의 시간복잡도 O(N^2)이 나오게 된다

 

1) 리스트 맨 끝 값으로 피봇을 잡았을 때

- 두 인덱스 변수를 이용해서, 피봇값보다 작다면 두 인덱스에 해당하는 값들은 switching한다

 

2) 리스트 맨 앞 값으로 피봇을 잡았을 때

- 1번과 유사하지만 끝에서부터 탐색한다는 차이점이 있다

 

	#include <vector>
	#include <iostream>
	using namespace std;
	void swap(int& a, int& b) {
	int tmp = a;
	a = b;
	b = tmp;
	}
	int partition(vector<int>& arr, int left, int right) {
	int pivot = arr[right];
	int i = left - 1;
	for (int j = left; j <= right - 1; j++) {
	if (pivot > arr[j]) {
	i++;
	swap(arr[i], arr[j]);
	}
	}
	swap(arr[i + 1], arr[right]);
	return (i + 1);
	}
	void quicksort(vector<int>& arr, int left, int right) {
	if (left < right) {
	int p = partition(arr, left, right);
	quicksort(arr, left, p - 1);
	quicksort(arr, p + 1, right);
	}
	return;
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
	cin >> arr[i];
	}
	quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++) {
	cout << arr[i] << '\n';
	}
	return 0;
	}

view raw quicksort.cpp hosted with ❤ by GitHub

	#include <vector>
	#include <iostream>
	using namespace std;
	void swap(int& a, int& b) {
	int tmp = a;
	a = b;
	b = tmp;
	}
	int partition(vector<int>& arr, int l, int r) {
	int pivot = arr[l];
	int i = r + 1;
	for (int j = r; j > l; j--) {
	if (pivot < arr[j]) {
	i--;
	swap(arr[i], arr[j]);
	}
	}
	swap(arr[i - 1], arr[l]);
	return (i - 1);
	}
	void quicksort(vector<int>& arr, int l, int r) {
	if (l < r) {
	int p = partition(arr, l, r);
	quicksort(arr, l, p - 1);
	quicksort(arr, p + 1, r);
	}
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
	cin >> a[i];
	}
	quicksort(a, 0, n - 1);
	for (int i = 0; i < n; i++) {
	cout << a[i] << '\n';
	}
	return 0;
	}

view raw quicksort2.cpp hosted with ❤ by GitHub

 

17번의 부등호 방향만 바꿔준다면 오름차순을 내림차순으로 바꿀 수 있다