#include #include #include #define N 50000 //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); } //bubblesort int bubblesort(int *array) { int temp = 0; int iter = 0; int i = 0; for (iter = 0; iter < (N - 1); iter++) { for (i = 0; i array[i + 1]) { temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } } return 0; } int main(void) { int A[N], B[N]; int i = 0; clock_t begin; clock_t end; double seconds; srand(time(NULL)); for (i = 0; i < N; i++) { A[i] = B[i] = rand() % N; } // call quick sort begin = clock(); quickSort(A); end = clock(); seconds = double(end - begin) / CLOCKS_PER_SEC; std::cout << "Time taken to sort for quicksort: " << seconds << std::endl; // call bubble sort begin = clock(); bubblesort(A); end = clock(); seconds = double(end - begin) / CLOCKS_PER_SEC; std::cout << "Time taken to sort for bubblesort: " << seconds << std::endl; return 0; }