[ Sort ] Quick Sort 퀵 정렬 <보충하기>

퀵 정렬은 평균적으로 O(nlogn)의 시간복잡도를 가지고 있다. 

퀵 정렬은 기준의 되는 피봇을 설정하고 그것을 기준으로 값들을 swap하면서 sort 하는 것이다. 

 

#include<stdio.h>
#include<iostream>
using namespace std;

int list[20] = { 0 };

void swap(int i, int j) {
	int temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}
void quick_sort(int left, int right) {
	if (left > right)return; 
	int pivot = right;
	int i = left;
	int j = right;
	while (i < j) {
		while (list[i] < list[pivot])
			i++;
		while (i<j&&list[pivot] <= list[j])
			j--;
		swap(i, j);
	}
	swap(pivot,j);
	quick_sort(left, j- 1);
	quick_sort(j + 1, right);
}

int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	char buffer = 0;
	int i = 0;
	for ( i = 0;; i++) {

		scanf("%d", &list[i]);
		scanf("%c", &buffer);
		if (buffer == '\n')
			break;
	}
	quick_sort(0, i);
	for (int j = 0; j < i; j++)
		printf("%d ", list[j]);
	return 0;
}