quicksort.cpp

#include <iostream>

using namespace std;


void swap(int arr[], int a, int b) {
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
}

int partition(int arr[], int low, int high) {
	int pivot = arr[high]; // last element를 pivot으로 설정
	int index = low;	//index에는 low를 시작점으로 설정

	// low -> high로 이동하면서 pivot과 보다 작은 값이 존재한다면 왼쪽으로 하나씩 보낸다.
	for (int i = low; i < high; i++) {
		if (arr[i] <= pivot) {
			swap(arr, i, index);
			index++;
		}
	}
	//index-1까지는 pivot보다 작은 값들로 구성이 되었고
	//index 위치는 pivot값(high)이 위치해야될 자리이다
	swap(arr, index, high);

	//정확히 중간자리인 index를 전달하고 이에 대한 왼쪽과 오른쪽에 대해서 정렬을 재시도 한다.
	return index;
}

/* Lumuto-Partition algorithm */
void quickSortLumuto(int arr[], int low, int high) {

	if (high > low) {
		int pivot = partition(arr, low, high);
		quickSortLumuto(arr, low, pivot - 1);
		quickSortLumuto(arr, pivot + 1, high);
	}
}


/* Hoare-Partition algorithm */
void quickSortHoare(int arr[], int low, int high) {

	int i = low, j = high;
	int pivot = arr[(low + high) / 2];

	do {
		while (arr[i] < pivot) i++;
		while (arr[j] > pivot) j--;
		if (i <= j) {
			swap(arr, i, j);
			i++;
			j--;
		}
	} while (i <= j);

	if (low < j) {
		quickSortHoare(arr, low, j);
	}

	if (i < high) {
		quickSortHoare(arr, i, high);
	}
}

void test(void(*qsort)(int*, int, int))
{
	int a[] = { 1, 4, 4, 3, 8, 9, 12, 5, 2 };
	int count = sizeof a / sizeof(a[0]);
	
	for (int i = 0; i < count; i++) {

		cout << a[i] << " ";
	}
	cout << endl;
		
	qsort(a, 0, count-1);
	

	for (int i = 0; i < count; i++) {

		cout << a[i] << " ";
	}
	cout << endl;

	
}
int main()
{
	cout << "quickSort - Hoare partition" << endl;
	test(quickSortHoare);
	cout << "quickSort - Lumuto partition" << endl;
	test(quickSortLumuto);
			
	return 0;
}