/* This program compares the following five sort algorithms: * Heapsort, mergesort, quick sort, select sort, and insert sort * Author: Your Name * Date: */ #include // Provides swap #include // Provides EXIT_SUCCESS, size_t #include // Provides cout #include // provide clock function. using namespace std; const size_t ARRAY_SIZE = 10000; // PROTOTYPES of the sorting functions used in this test program: // Each of these functions has the same precondition and postcondition: // Precondition: data is an array with at least n components. // Postcondition: The elements of data have been rearranged so // that data[0] <= data[1] <= ... <= data[n-1]. void heapsort(int data[ ], size_t n); void mergesort(int data[ ], size_t n); void quicksort(int data[], size_t n); void selectionsort(int data[ ], size_t n); void insertionsort(int data[], size_t n); // PROTOTYPE of a function that will test one of the sorting functions: void testsort(void sorter(int data[], size_t n), const char* name); int main( ) { cout << "This program will generate arrays with ARRAY_SIZE elements" < data[i]) { cout << "Incorrect sort at index " << i << endl; return; } --count[data[i]]; } for (i = 0; i < (size_t) LIMIT; ++i) { if (count[i] != 0) { cout << "Incorrect numbers in the data array after sorting." << endl; return; } } cout << "Sorting completed correctly "; cout << "in " << (ending - beginning)/1000.0 << " seconds " << endl; } //************************************************************************* // HEAPSORT IMPLEMENTATION: // Assume that the heap data stored in array. i.e. we view the array as heap size_t parent(size_t k) { } size_t left_child(size_t k) { } size_t right_child(size_t k) { } // make a heap based on given data array void make_heap(int data[ ], size_t n) { } void reheapify_down(int data[ ], size_t n) { } void heapsort(int data[ ], size_t n) { } //************************************************************************* //************************************************************************* // MERGESORT IMPLEMENTATION: // void merge(int data[ ], size_t n1, size_t n2) // Precondition: data is an array (or subarray) with at least n1 + n2 elements. // The first n1 elements (from data[0] to data[n1 - 1]) are sorted from // smallest to largest, and the last n2 (from data[n1] to data[n1 + n2 - 1]) // also are sorted from smallest to largest. // Postcondition: The first n1 + n2 elements of data have been rearranged to be // sorted from smallest to largest. // NOTE: If there is insufficient dynamic memory, then bad_alloc is thrown. // Library facilities used: cstdlib { } void mergesort(int data[ ], size_t n) // Precondition: data is an array with at least n components. // Postcondition: The elements of data have been rearranged so // that data[0] <= data[1] <= ... <= data[n-1]. // NOTE: If there is insufficient dynamic memory, thenbad_alloc is thrown. // Library facilities used: cstdlib { } //************************************************************************* //************************************************************************* // QUICKSORT IMPLEMENTATION: // //************************************************************************* size_t partition(int data[], size_t n) { } void quicksort(int data[], size_t n) { } //************************************************************************* // SELECTIONSORT IMPLEMENTATION: // void selectionsort(int data[ ], size_t n) // Library facilities used: algorithm, cstdlib { } //************************************************************************* //************************************************************************* // INSERTION SORT IMPLEMENTATION // void insertionsort(int data[], size_t n) // { } Project Description: In this project, the students are required to implement the following algorithms: Insert Sort, Select Sort, Quick Sort, and Merge Sort. One file is given: CSCI251ProjOne.java. Please study this file to understand what is going on. This file shall not be modified. One file is to implement: MySort.java. In this file, the students must provide the following public interface: public static void insertSort(int [] arr); public static void selectSort(int [] arr); public static void quickSort(int [] arr); public static void mergeSort(int [] arr); The quick sort and merge sort must be implemented by using recursive thinking. So the students may provide the following private static methods: // merge method // merge two sorted portions of given array arr, namely, from start to middle // and from middle + 1 to end into one sorted portion, namely, from start to end private static void merge(int [] arr, int start, int middle, int end); // merge sort recursive version // sort the portion of giving array arr, from begin to end private static void mergeSortRecursive(int [] arr, int begin, int end); // find pivot point for quick sort private static int pivot(int [] arr, int begin, int end); // quick sort recursive version // sort the portion of giving array arr, from begin to end private static void quickSortRecursive(int [] arr, int begin, int end); The student need to have and only have the above public and private static methods in his/her implementation of MySort class. Run Demo: ProjectOne.jar is available for students to download and run on their computer. The students may run to demo in the terminal window to see how program should run.