4. 퀵 정렬 (Quick Sort)

 

<PIVOT을 중간 원소로 설정한 경우>

#include <iostream>
using namespace std;
int arr[8] = { 21, 10, 12, 20, 25, 13, 15, 22 };
void quickSort(int st, int en){
    int low = st, high = en;
    if (high <= low) return;
    int pivot = arr[(st + en) / 2]; // 중간에 있는 애를 pivot으로
    while (low <= high) {               // low와 high가 교차하면 끝남
        while (pivot > arr[low]) ++low; // arr[low]가 pivot보다 크거나 같으면 멈춤
        while (pivot < arr[high]) --high; // arr[high]가 pivot보다 작거나 같으면 멈춤
        if(low <= high){
            int tmp = arr[low];
            arr[low] = arr[high];
            arr[high] = tmp;
            ++low, --high;
        }
    }
    quickSort(st, high);
    quickSort(low, en);
}
int main(){
    quickSort(0, 7);
    for (int i = 0; i < 8; i++) cout << arr[i] << " ";
    return 0;
}

 

<PIVOT을 첫 번째 원소로 설정한 경우>

#include <iostream>
using namespace std;

void quickSort(int arr[], int left, int right) { //퀵 정렬
	if (left >= right)return; //원소가 1개면 끝내기

	int pivot = left, start = left + 1, end = right, temp = 0;

	while (start <= end) { //엇갈릴 때까지 반복

		while (arr[pivot] >= arr[start]) start++; //low : pivot보다 큰 값 찾음
		while (arr[pivot] <= arr[end] && end > left) end--; //high : pivot보다 작은 값 찾음

		if (start > end) { //엇갈리는 경우엔 pivot과 high를 교환하여 pivot을 중심으로 옮긴다
			temp = arr[end];
			arr[end] = arr[pivot];
			arr[pivot] = temp;
		}
		else { //엇갈리지 않는 경우엔 low와 high를 교환한다
			temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
		}
	}

	quickSort(arr, left, end - 1);
	quickSort(arr, end + 1, right);
}

int main() {
	int arr[9] = { 5, 3, 8, 4, 9, 1, 6, 2, 7 };
	int N = 9;

	quickSort(arr, 0, N - 1);

	for (int i = 0; i < N; i++) cout << arr[i] << "\n";
    
    return 0;
}