퀵 정렬(Quick Sort)

🟩피벗 : 보통 주어진 배열의 첫 번째 데이터로 지정

기준이 되는 수(pivot)를 수열 안에서 임의로 하나 선택하여 피봇 이외의 수를 피봇보다 작은 수, 큰 수로 나눈다.

작은 수 < 피봇 <= 큰수로 배치

그리고 두 그룹을 정렬하면 된다. 이 때도 퀵 정렬을 이용

자식이 하나만 남으면 끝

 

🟩 그룹 나누기 함수, 그 함수로 정렬을 수행하는 함수를 준비하면 퀵 정렬 프로그램 작성이 매우 간단해진다.

QuickSort(A[ ], n){
	if (n > 1) {
    	// ①피벗을 기준으로 두 부분배열로 분할
		// pivot은 제자리를 잡은 피벗의 위치(인덱스)를 표시
		pivot = Partition(A[0..n-1], n);
        
		// ②왼쪽 부분배열에 대한 퀵 정렬의 순환 호출
		QuickSort(A[0..pivot-1], pivot);
        
		// ③오른쪽 부분배열에 대한 퀵 정렬의 순환 호출
		QuickSort(A[pivot+1..n-1], n-pivot-1);
	}
}

int Partition (A[ ], n){
	Left = 1; Right = n-1;
	while (Left < Right) {
		while (Left < n && A[Left] < A[0]) Left++;
		while (Right > 0 && A[Right] >= A[0]) Right--;
		if (Left < Right)
			A[Left]와 A[Right]의 위치 교환
		else
			피벗 A[0]와 A[Right]의 위치 교환
	}
	return (Right);
}

 

 

🟩 시간 복잡도

데이터를 절반씩 분할하면서 줄여나가기 때문에 logn만큼의 분할이 이뤄지게 되고

각 분할에서 n번의 값 비교를 통해 위치를 찾아가기 때문에 O(nlogn)

 

🌟 퀵 정렬이 빠른 이유

선택 정렬 : 모든 데이터를 한 번 확인했을 때, 가장 작은 데이터의 위치가 확정될 뿐, 나머지 데이터는 그대로 내버려둔다.

 

반면에, 퀵 정렬은 모든 데이터를 한 번 확인했을 때, 기준값이 되는 데이터의 위치가 확정되고, 나머지 데이터는 2개의 그룹으로 나뉜다. 이 '나머지 데이터가 두 그룹으로 나뉘는'만큼, 이후 처리가 효율적이다. 이것이 퀵 정렬이 빠른 이유