#include #include #define N 10 //swaps the two values in the list void swap(int list[], int left, int right) { /* temp variable for swap, doesn't have to be initialized, but is good practice */ int temp = 0; //swap with aid of temp temp = list[left]; list[left] = list[right]; list[right] = temp; } //partition divides and conquer int partition(int list[], int low, int high) { //left and right values in the array int left = 0, right = 0; int pivot_item = 0; int pivot = left = low; pivot_item = list[low]; right = high; while (left < right) { // Move left while item < pivot while (list[left] <= pivot_item) { left++; } // Move right while item > pivot while (list[right] > pivot_item) { right--; } if (left < right) swap(list, left, right); } // right is final position for the pivot list[low] = list[right]; list[right] = pivot_item; return right; }//end partition void quickSort(int list[], int low, int high) { int part = 0; if (low < high) { // divide and conquer part = partition(list, low, high); quickSort(list, low, part - 1); quickSort(list, part + 1, high); } } //we use function overloading here! void quickSort(int list[]) { quickSort(list, 0, N - 1); } int main(void) { int B[N] = { 9, 5, 7, 1, 3, 2, 0, 4, 8, 6 }; int i = 0; //print unsorted array std::cout << "************** Result **************" << std::endl; std::cout << "The input array is: " << std::endl; for (i = 0; i < N; i++) { std::cout << B[i] << " "; } std::cout << std::endl; // call quick sort quickSort(B); /* print the sorted array */ std::cout << "The sorted array is: " << std::endl; for (i = 0; i < N; i++) { std::cout << B[i] << " "; } std::cout << std::endl; return 0; }