Skip to content

Instantly share code, notes, and snippets.

@recoverlee
Created October 13, 2015 15:31
Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment