You are provided with a C program that implements and tests 4 common sorting algorithms. The sorting algorithms themselves have been removed. You are required to re-implement them so the program works. You will implement the four sort algorithms from the lecture/readings. Implement the algorithms as described in the lecture notes or your will not receive full credit. The following files are provided: main.c containing the main program. DO NOT EDIT THIS FILE sortTests.c a file containing tests to verify the sorts work correctly. DO NOT EDIT THIS FILE sortTests.h The function prototypes for the sorting tests. DO NOT EDIT THIS FILE sort.h The function prototypes for the sort functions. You may add to this file but not remove/edit anything provided. sort.c The sort functions are implemented here. You will make changes to this file The sort.c file has no working code. You will implement Insertion Sort, Bubble Sort, Merge Sort, and Quick Sort in this file. If you complete your implementations correctly, the main program will work with no changes needed. Example Execution You can run the code and it will provide a menu. You can collect timings or test one of the sorts. If one of your algorithms fails, information about what went wrong will be printed. Example 1 Select Which Test to Run: 0.) Time All Algorithms 1.) Test Bubble Sort 2.) Test Insertion Sort 3.) Test Merge Sort 4.) Test Quick Sort 1 Testing Bubble Sort Enter Size of Arrays to Test: 100 Enter Number of Tests to Run: 50 Passed 50 out of 50 tests. Example 2 Select Which Test to Run: 0.) Time All Algorithms 1.) Test Bubble Sort 2.) Test Insertion Sort 3.) Test Merge Sort 4.) Test Quick Sort 2 Testing Insertion Sort Enter Size of Arrays to Test: 10 Enter Number of Tests to Run: 3 Passed 3 out of 3 tests. Example 3 Select Which Test to Run: 0.) Time All Algorithms 1.) Test Bubble Sort 2.) Test Insertion Sort 3.) Test Merge Sort 4.) Test Quick Sort 4 Testing Quick Sort Enter Size of Arrays to Test: 9 Enter Number of Tests to Run: 11 Passed 11 out of 11 tests. Timings Once all your algorithms work correctly, run the program and select 0 to collect timings. Place the output of the program in a file readme.txt You must also make a chart timings.png comparing all the timings for all 4 algorithms. The y axis should be time and the x axis should be log2(size). Since the sizes grow so fast, the chart will be easier to read if you use the log2 of the size along the x axis. Below the timings answer the following questions in readme.txt: What was the fastest algorithm? What was the slowest algorithm? Did the timings match the analysis from class? What was the hardest part of this assignment? Template Table Size Bubble Insert Merge Quick 8 ? ? ? ? 16 ? ? ? ? 32 ? ? ? ? 64 ? ? ? ? 128 ? ? ? ? 256 ? ? ? ? 512 ? ? ? ? 1024 ? ? ? ? 2048 ? ? ? ? 4096 ? ? ? ? 8192 ? ? ? ? 16384 ? ? ? ? 32768 ? ? ? ? 65536 ? ? ? ? 131072 ? ? ? ? Rubric Bubble Sort (17 points) 5 points - Bubble Replit Test 01 5 points - Bubble Replit Test 02 5 points - Bubble Replit Test 03 2 points - Design, Comments, Implemenation review Insertion Sort (17 points) 5 points - Insert Replit Test 01 5 points - Insert Replit Test 02 5 points - Insert Replit Test 03 2 points - Design, Comments, Implemenation review Merge Sort (25 points) 5 points - Merge Replit Test 01 5 points - Merge Replit Test 02 5 points - Merge Replit Test 03 5 points - Merge Replit Test 04 5 points - Design, Comments, Implemenation review Quick Sort (25 points) 5 points - Quick Replit Test 01 5 points - Quick Replit Test 02 5 points - Quick Replit Test 03 5 points - Quick Replit Test 04 5 points - Design, Comments, Implemenation review readme.txt (10 points) 2 points - Table Results 2 points - Question 1 Answer 2 points - Question 2 Answer 2 points - Question 3 Answer 2 points - Question 4 Answer 6 points - Chart timings.png

#include "sortTests.h" #include "stdlib.h" #include "stdio.h"

//Run many tests char runMultipleTests(void (*func)(int*, int), int size, int numTests){ int passed=0; for(int i=0; i < numTests; i++){ passed+=testSort(func,size); } printf("Passed %d out of %d tests. ",passed,numTests); return (passed==numTests); }

//Run a single test char testSort(void (*func)(int*, int), int size){ //Make a Random Array int* Original = malloc(sizeof(int)*size); //Put Random Numbers into the Array for(int i=0; i < size; i++){ Original[i] = rand()%(size*4); } //Make a Copy to Sort int* After = copyArray(Original,size); //Run the sort function func(After,size); //Check Sort Worked if(!isSorted(Original,After,size)){ printf("SORT FAILED!! "); printf("Array Before Sort: "); printArray(Original,size); printf("Array After Sort: "); printArray(After,size); return 0; } //Release The Memory free(Original); free(After); //Success return 1; }

//Print Out An Array void printArray(int* A, int size){ printf("["); for(int i=0; i < size; i++){ printf("%d",A[i]); if(i+1

//Copy An Array int* copyArray(int* A, int size){ int* T = malloc(size*sizeof(int)); for(int i=0; i < size; i++){ T[i] = A[i]; } return T; }

//sorted is the sorted version of old if //it is in order and contains all elements char isSorted(int* old, int* sorted, int size){ //Elements Must Be In Order if(!inOrder(sorted,size)){ return 0; } //All Elements Must Appear in Both Arrays if(!containsSame(old, sorted, size)){ return 0; } //Nothing Failed return 1; }

//Check if all elements are in order char inOrder(int* A, int size){ for(int i=1; i < size; i++){ //Not In Order if(A[i-1] > A[i]){ return 0; } } return 1; }

//For each item, check they appear the same number //of times char containsSame(int* A, int* B, int size){ for(int i=0; i < size; i++){ int left = countAppearances(A,size,A[i]); int right = countAppearances(B,size,A[i]); //Some Number Doesn't Match if(left!=right){ return 0; } } //Everything Matches return 1; }

//Loop over the array and count appearances of target int countAppearances(int* A, int size, int target){ int count = 0; for(int i=0; i < size; i++){ if(A[i]==target){ count++; } } return count; }