code a program that benchmarks QuickSort and InsertionSort by using code below . At least five different
Question:
code a program that benchmarks QuickSort and InsertionSort by using code below. At least five different datasets should be used and the performance of each algorithm should be recorded in the same set under the same conditions. put a short report comparing the two algorithms based on your results. The given code must not touched.
[I don't understand whatQ2 want me to do (however I am also having problem whith q1 please help me)]
Q2 MergeSort continuously divides the data into segments until segments of size 1 are reached. It then begins the merging phase. This is the expensive part. Improvements could be made if we could reduce the cost of merging. It turns out that InsertionSort is very efficient for small data sequences (say sequences of < 50 values) where the data is partially ordered in the correct order and the displacement is small. The idea is to combine MergeSort and InsertionSort to reduce the overhead of merging. To do this we terminate the MergeSort division when segments of some given size are reached, use InsertionSort to sort the segments and then do the merging as before. Your task is to implement this solution.
class assignment{
public static void main(String args[]){ //========================================================== //Question 1 testing //================== // Comment on benchmarking for Q1 results
//================== }
static void quickSort(int f[], int p, int q) { if (q-p <= 1); //skip else { int x; int i, j, k; // let x = middle element in f[p..q-1] x = f[(p+q) / 2]; //x = f[p]; i = p; j = p; k = q; while (j != k) { if (f[j] == x) j = j+1; else if (f[j] < x) { //swap f[j] with f[i] int temp; temp = f[j]; f[j] = f[i]; f[i] = temp; j = j+1; i = i+1; } else { // f[j] > x // swap f[j] with f[k-1] int temp; temp = f[j]; f[j] = f[k-1]; f[k-1] = temp; k = k-1; } } quickSort(f, p, i); quickSort(f, j, q); } }
//merge Sort static void mergeSort(int f[], int lb, int ub){ //termination reached when a segment of size 1 reached - lb+1 = ub if(lb+1 < ub){ int mid = (lb+ub)/2; mergeSort(f,lb,mid); mergeSort(f,mid,ub); merge(f,lb,mid,ub); } } static void merge(int f[], int p, int q, int r){ //p<=q<=r int i = p; int j = q; //use temp array to store merged sub-sequence int temp[] = new int[r-p]; int t = 0; while(i < q && j < r){ if(f[i] <= f[j]){ temp[t]=f[i];i++;t++; } else{ } } temp[t] = f[j]; j++; t++; //tag on remaining sequence while(i < q){ temp[t]=f[i];i++;t++; } while(j < r){ temp[t] = f[j]; j++; t++; } //copy temp back to f i = p; t = 0; while(t < temp.length){ f[i] = temp[t]; i++; t++; } }
static void insertionSort(int k[], int a, int b) { int j = a+1; while (j < b) { int i = j; while (i > a && k[i] < k[i-1]) {//swap k[i], k[i-1] int temp = k[i]; k[i] = k[i-1]; k[i-1] = temp; i = i-1; } j = j+1; } } }
Database Systems Design Implementation and Management
ISBN: 978-1337627900
13th edition
Authors: Carlos Coronel, Steven Morris