[알고리즘] 퀵 정렬 - C++

퀵 정렬

---

#include <iostream>

using namespace std;

int n, cnt;
int arr[] = { 4, 2, 6, 1, 5, 3 };

void quickSort(int s, int e) {
	if (s >= e)	//원소가 1개인 경우
		return;

	int pivot = s;	//피벗은 첫번째 원소
	int left = s+1, right = e;
	int temp;

	while (left <= right) {	//엇갈릴 때까지 반복
		while (arr[left] <= arr[pivot])	//피벗보다 큰 값을 만날 때까지 이동
			left++;
		while (arr[right] >= arr[pivot] && right > s)	//피벗보다 작은 값을 만날 때까지 이동
			right--;
		if (left > right) {
			temp = arr[right];
			arr[right] = arr[pivot];
			arr[pivot] = temp;
		}
		else {
			temp = arr[right];
			arr[right] = arr[left];
			arr[left] = temp;
		}
	}
	quickSort(s, right - 1);
	quickSort(right + 1, e);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	quickSort(0, 5);

	for (int i = 0; i < 6; i++)
		cout << arr[i] << ' ';

	return 0;
}

시간 복잡도

평균- O(NlongN)

최악- O(N^2)