49. 퀵 정렬

퀵 정렬이란?

퀵 정렬은 평균적으로 가장 빠른 알고리즘 중 하나로 알려져 있다.

이 알고리즘은 분할 정복 방법을 사용하여 리스트를 정렬한다.

 

동작 방식

1. 리스트에서 하나의 요소를 선택한다. (이를 피벗이라 한다)

2. 피벗을 기준으로 리스트를 두 개의 부분으로 분할한다. 피벗보다 작은 값은 왼쪽, 피벗보다 큰 값은 오른쪽에 위치한다.

3. 분할된 두 개의 부분 리스트에 대해 재귀적으로 위 과정을 반복한다.

4. 재귀 호출이 완료되면, 부분리스트들이 결합된다.

 

퀵 정렬은 분할과 정복 과정을 반복하면서 리스트를 작은 부분으로 나누어 정렬하기 때문에 효율적이다.

평균 시간복잡도는 O(n log n)이며, 최악의 경우에도 O(n^2)이다.

퀵 정렬은 대부분의 경우에서 빠른 정렬 알고리즘으로 사용되며, 일반적으로 다른 정렬 알고리즘보다 빠른 실행 속도를 보인다.

---

#define SWAP(a,b,t) ((t=a), (a=b), (b=t))

void quicksort(int User_Data[], int left, int right, int n) {
	int i, j, pivot, temp;
	
	// left, right의 위치가 교차하게 되면 정렬을 종료한다. 
	if(left<right){
		i=left, j=right+1;
		// 피벗은 가장 왼쪽 데이터로 선정한다.  
		pivot=User_Data[left];
		
		// i, j가 교차하게 되면 해당 부분의 pivot을 기준으로 [작은값 pivot 큰값] 으로 정렬이 된것이다. 
		do{
			do i++; while(User_Data[i] < pivot);
			do j--; while(User_Data[j] > pivot);
			if(i<j) SWAP(User_Data[i], User_Data[j], temp);
		}while(i<j);
		SWAP(User_Data[left], User_Data[j], temp);
		
		// 재귀함수를 통해 정렬을 계속 진행한다. 
		quicksort(User_Data, left, j-1, n);
		quicksort(User_Data, j+1, right, n);
	}
}