퀵소트

• 퀵소트(Quick sort)

  퀵소트(quick sort)는 pivot을 중심으로 작거나 같은 값을 지니는 데이터는 앞으로 반대로 pivot보다 큰 값의 데이터는 뒤로 가도록 정렬한다. 정렬이 완료가 되면 pivot의 왼쪽과 오른쪽을 재귀적으로 반복하며 시간복잡도는 $O(nlogn)$이다.

---

• 예시)

  1회전 :

  3 6 1 2 4 -> pivot = 3

  1 2 3 6 4

  2회전(왼) :

  1 2 3 -> pivot = 1

  1 2 3

  2회전(오) :

  6 4 -> pivot = 6

  4 6

  최종 :

  1 2 3 4 6

---

• 코드 구현(C++)

#include <iostream>
#include <algorithm>
using namespace std;
int A[5] = { 10,6,1,3,4 };
void print_arr() {
	cout << "\n";
	for (int i = 0; i < 5; i++) cout << A[i] << " ";
	cout << "\n";
}
void quick_sort(int left, int right) {
	if (left == right) return;
	swap(A[left], A[((right - left) / 2 + left)]);
	int l = left + 1;
	int r = right - 1;
	int pivot = left;
	while (l <= r) {
		while (l <= r && A[pivot] >= A[l])
			l++;
		while (l <= r && A[r] >= A[pivot])
			r--;
		if (l <= r)
			swap(A[l], A[r]);
	}
	swap(A[pivot], A[r]);
	quick_sort(left, r);
	quick_sort(r + 1, right);
}

int main(void) {
	print_arr();
	quick_sort(0, 5);
	print_arr();
	return 0;
}

---