퀵 정렬이란?

• sorting 성능에서 구현이 간단한 버블정렬과 선택정렬은 $O(n^2)$의 시간복잡도를 가진다.
  성능 면에서 퀵 정렬은 $n*log(n)$ 의 시간 복잡도를 가지며 최악의 경우에는 $O(n^2)$ 의 시간복잡도를 가진다.

정렬 방법

• 먼저 피봇(pivot)을 설정한다
• 피봇을 기준으로 피봇값보다 작은 값은 피봇 왼쪽, 피봇값보다 큰 값은 피봇 오른쪽으로 정렬
• 새로운 피봇값을 설정하고 위 과정을 반복한다.
• 리스트를 더 이상 분할 할 수 없을 때까지 수행 (리스트의 크기가 0또는 1이 될때까지)

-> 위 방법이 분할 정복 (divide and conquer) 방법
: 큰 문제를 작은 문제로 나누어 작은 문제들의 해결을 토대로 큰 문제의 답을 도출해내는 방법
, 보통 순환호출 방법을 이용해 알고리즘을 작성한다.

구체적 구현 방법

리스트를 분할하는 방법
1) 5,3,2,1,4,9,7,8 의 리스트가 있을 때
2) 피봇을 리스트의 첫번째 값이라고 지정하고 (pivot = 5)
3) low 와 high 값을 설정한다.
4) low 값을 1씩 증가시키면서 피봇값보다 큰 데이터 값을 찾으면 멈춘다.
5) high 값을 1씩 감소시키면서 피봇값보다 작은 데이터 값을 찾으면 멈춘다.
6) high와 low 데이터 값을 교환
-> 3)~6) 과정은 low, high 값이 엇갈릴때까지 반복
7) 피봇을 리스트의 가운데로 옮기기 (pivot 과 high 값을 바꿔준다.)

-> 1번 과정을 진행하면 피봇값이 제자리로 돌아간다. 따라서, 총 n번 반복하면 리스트를 정렬할 수 있다.

특징

• 정렬 시간이 빠르다.
• 불균형 정렬이 이뤄지면 오히려 수행시간이 길어진다.
  -> list의 중간 값을 pivot 으로 지정해주면 불균형 정렬을 방지할 수 있다.

구현코드

#include <stdio.h>
//2750번 수 정렬하기 브2

int arr[1000000];

void SWAP(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void quick_sort(int start, int end){
	if (start>=end)	return ;
	int key = start, i = start+1, j=end;
	while(i<=j){
		while(i<=end && arr[i]<=arr[key])	i++;
		while(j>start && arr[j]>=arr[key])	j--;
		if (i>j)	SWAP(&arr[key],&arr[j]);
		else	SWAP(&arr[i],&arr[j]);
	}
	quick_sort(start,i-1);
	quick_sort(i,end);
}

int main(){
	int n;
	scanf("%d",&n);
	for (int i=0; i<n; i++){
		scanf("%d",&arr[i]);
	}
	
	//퀵 정렬
	quick_sort(0,n-1);
	
	for (int i=0; i<n; i++){
		printf("%d\n",arr[i]);
	}
	
}