[알고리즘] 정렬 알고리즘 - 퀵 정렬 Quick Sort

 

퀵 정렬 (Quick Sort) 알고리즘 :

분할 정복 알고리즘 중의 하나로, 매우 빠른 속도를 자랑하는 알고리즘

 

1. 배열 안의 한 요소를 선택하여 이를 피벗이라 하고, 배열의 맨 첫번째 요소와 교환

2. 배열의 왼쪽 끝에서부터 피벗보다 큰 요소를, 오른쪽 끝에서부터 피벗보다 작은 요소를 탐색

3. 왼쪽에서 발견한 피벗보다 큰 요소와 오른쪽에서 발견한 피벗보다 작은 요소를 교환

3. 왼쪽과 오른쪽에서 탐색하던 커서가 만나면 중지, 피벗과 교환

    => 두 커서가 만난 위치 왼쪽에는 피벗보다 작은 요소가, 오른쪽에는 큰 요소가 위치하게 된다

4. 피벗을 기준으로 왼쪽 그룹과 오른쪽 그룹을 각각 다시 퀵 정렬

5. 각 그룹이 더이상 분할이 불가능할 때 까지 반복 -> 그룹 배열의 크기가 0이나 1이면 중지

 

 

int[] quick = {5, 1, 4, 3, 7, 6, 2}

1. quick 배열의 정 가운데 요소를 피벗으로 정하고 배열의 맨 앞 요소와 교환

2. 맨 왼쪽부터 L커서가 피벗보다 큰 값을 탐색, 4 발견 / 맨 오른쪽부터 R 커서가 피벗보다 작은 값을 탐색, 2 발견 / 두 값 교환

3. L커서가 5를 찾고 R커서가 2를 찾았지만, R커서가 L커서보다 왼쪽에 위치

4. 피벗과 R커서 위치의 요소 교환

5. 피벗 3을 기준으로 왼쪽 그룹과 오른쪽 그룹을 각각 퀵 정렬

 

배열 quick의 퀵 정렬 과정

 

메서드 swap() : a[idx1] 과 a[idx2] 를 교환

매개변수 : int[] a, int idx1, int idx2

 

메서드 partition() : 배열 a의 index left 부터 right 까지 요소 중 피벗을 정해 퀵 정렬 후 피벗 index 반환

매개변수 : int[] a, int left, int right

반환값 : 퀵 정렬 후 피벗의 index

 

메서드 quickSort() : 배열 a의 index left 부터 right 까지 요소를 퀵 정렬

매개변수 : int[] a, int left, int right

 

- 퀵 정렬 : 

void swap(int[] a, int idx1, int idx2) {
	int t = a[idx1];
	a[idx1] = a[idx2];
	a[idx2] = t;
}

int partition(int[] a, int left, int right) {
	int pc = (left + right)/2;
	int pivot = a[pc];
	int pl = left;
	int pr = right;
	swap(a, pl, pc);
	
	while(pl < pr) {
		while(a[pr] > pivot) pr--;
		while(a[pl] <= pivot && pl < pr) pl++;
		swap(a, pl, pr);
	}
	a[left] = a[pl];
	a[pl] = pivot;
	return pl;
}
	
void quickSort(int[] a, int left, int right) {
	if(left >= right)
		return;
	
	int pc = partition(a, left, right);
	quickSort(a, left, pc-1);
	quickSort(a, pc+1, right);	
}

 

 

 

 

퀵 정렬 Quick Sort :

최선 = O(NlogN), 평균 = O(NlogN), 최악 = O(N^2)

불안정한 정렬