Please implement Insertion Sort, Bubble Sort, Merge Sort, and Quick Sort in sort.c file.

main.c

#include "stdlib.h"

#include "stdio.h"

#include "time.h"

//Local Libraries

#include "sort.h"

#include "sortTests.h"

//This Enum Type is used to easily select

//from the menu

enum TestType {

timings=0,

bubble=1,

insert=2,

merges=3,

quick=4

};

//Give the type a short name to use later

typedef enum TestType TestType;

TestType decideType();

/**

Ask the user about how to test a single sort

@param func is the function to test

@return 1 if passed and 0 for failed

*/

char testASort(void (*func)(int*, int));

/**

Make a Table of Sorts and their timings

*/

void timeAllSorts();

/**

Time a single sort

@param func is the function to time

@param size is the size of the array to time

@return time taken by the test in seconds

*/

double timeASingleSort(void (*func)(int*, int), int size);

/**

Main Asks the User What to Test using STDIN

@param argc is not used

@param argv is not used

@return is always 0

*/

int main(int argc, char** argv){

//Prepare the Random Number Generator

srand(time(NULL));

//Ask What Test to Run

TestType option = decideType();

//Run the Correct Test

switch(option){

case timings:

printf("Running Timings. ");

timeAllSorts();

break;

case bubble:

printf("Testing Bubble Sort ");

testASort(bubbleSort);

break;

case insert:

printf("Testing Insertion Sort ");

testASort(insertSort);

break;

case merges:

printf("Testing Merge Sort ");

testASort(mergeSort);

break;

case quick:

printf("Testing Quick Sort ");

testASort(quickSort);

break;

default:

printf("Unknown Command Given ");

break;

}

return 0;

}

//Ask the user what type of test to run

TestType decideType(){

printf("Select Which Test to Run: ");

printf("0.) Time All Algorithms ");

printf("1.) Test Bubble Sort ");

printf("2.) Test Insertion Sort ");

printf("3.) Test Merge Sort ");

printf("4.) Test Quick Sort ");

int result;

int success = scanf("%d",&result);

//Ask Again On Bad Inputs

if(!success || result < 0 || result > 5){

printf("Invalid Option Given. ");

return decideType();

}

return result;

}

//Ask user for size and number of tests

char testASort(void (*func)(int*, int)){

printf("Enter Size of Arrays to Test: ");

int size;

int worked = scanf("%d",&size);

//Read Failed

if(!worked){

printf("Could Not Read Input ");

return 0;

}

//Get Num Tests

printf("Enter Number of Tests to Run: ");

int tests;

worked = scanf("%d",&tests);

//Read Failed

if(!worked){

printf("Could Not Read Input ");

return 0;

}

//Run the tests!

return runMultipleTests(func,size,tests);

}

//Generate Table of Sorts

//Goal:

//| Size | Gnome | Bubble | Insert | Merge | Quick |

//....

void timeAllSorts(){

//Title Column

printf("All Times in milliseconds. ");

printf("| %7s | %10s | %10s | %10s | %10s | ",

"Size", "Bubble",

"Insert", "Merge", "Quick");

//Run Tests

int size = 8;

while(size <= 131072){

//Generate 1 Row

double b = timeASingleSort(bubbleSort,size);

double i = timeASingleSort(insertSort,size);

double m = timeASingleSort(mergeSort,size);

double q = timeASingleSort(quickSort,size);

//Print Results

printf("| %7d | %10.4f | %10.4f | %10.4f | %10.4f | ",

size, b, i, m, q);

//Get Read for next row

size = size * 2;

}

}

//Collect Timings for a single sort

double timeASingleSort(void (*func)(int*, int), int size){

//Make a Random Array

int* T = malloc(size*sizeof(int));

//Put in Numbers

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

T[i] = rand()%(size*4);

}

double before = (double)clock();

func(T,size);

double after = (double)clock();

//Release Memory

free(T);

return (after-before)/(CLOCKS_PER_SEC/1000);

}

sort.c. :-

#include "sort.h"

#include "stdlib.h"

#include "stdio.h"

//Implement this function based on lecture

void bubbleSort(int* A, int size){

return;

}

//Implement this function based on lecture

void insertSort(int* A, int size){

return;

}

//Implement this function based on lecture

void mergeSort(int* A, int size){

return;

}

//Implement this function based on lecture

void msort(int* A, int start, int stop){

return;

}

//Implement this function based on lecture

void merge(int* A, int start, int middle, int stop){

return;

}

//Implement this function based on lecture

void quickSort(int* A, int size){

return;

}

//Implement this function based on lecture

void qusort(int* A, int start, int stop){

return;

}

//Implement this function based on lecture

int partition(int* A, int start, int stop){

return 0;

}

sort.h :-

#ifndef _SORT_H_

#define _SORT_H_

/**

Implement Bubble Sort Based on Lecture

@param A is the array to sort

@param size is the number of elements in the array

*/

void bubbleSort(int* A, int size);

/**

Implement Insertion Sort Based on Lecture

@param A is the array to sort

@param size is the number of elements in the array

*/

void insertSort(int* A, int size);

/**

Implement Merge Sort Based on Lecture

@param A is the array to sort

@param size is the number of elements in the array

*/

void mergeSort(int* A, int size);

/**

Recursive Helper Function for Merge Sort

@param A is the array to sort

@param start is the first index to sort

@param stop is the last index to sort

*/

void msort(int* A, int start, int stop);

/**

Merge Function for Merge Sort

@param A is the array to Merge

@param start is the first index

@param middle is the middle index

@param stop is the last index

*/

void merge(int* A, int start, int middle, int stop);

/**

Implement Quick Sort Based on Lecture

@param A is the array to sort

@param size is the number of elements

*/

void quickSort(int* A, int size);

/**

Recursive Helper Function for Quick Sort

@param A is the array to sort

@param start is the first index to sort

@param stop is the last index to sort

*/

void qusort(int* A, int start, int stop);

/**

Partition for Quick Sort

Use Randomized Index Selection Here

You may assume srand has already been set in main.c

@param A is the array to Partition

@param start is the first index to use

@param stop is the last index to use

@return The index of the partition element

*/

int partition(int* A, int start, int stop);

#endif