write a program to display the running time of the different sorts. Test the sor

Question

write a program to display the running time of the different sorts. Test the sorts on arrays of various sizes. Arrays of the same size should contain identical entries Use the function clock from <ctime> to time each sort.

Explanation and specifics:

You are to compare the relative performance of different sorting algorithms on the same data set and the same algorithm on different data sets.

Choose a sorting algorithm from each of the O(n^2) (i.e., selection, insertion and buble), O(n logn) (i.e., merge and quick), and O(n) (i.e., counting, bucket and radix) categories.

Randomly generate (1000, 10000, and 100000) integer values (in the range of 0 to 1000000) to be inserted into the data structures. Note that the list (i.e., the input values) itself should not be sorted and all algorithms should use the same input file when the input size is same.

Also, test the speed of algorithms when the input array is already sorted (for the same input data).

The following output should be provided for an average of 10 sorts of each algorithm and input size:

1. the CPU time (note that generation processes should not affect these values)

2. the number of comparisons

3. the number of swaps

/**Then run the algorithms with 1000000 values.

*

*You can run 2 instances of algorithms that take more than one hour.

Explanation / Answer

#include #include #include //Is this less offensive than using the entire std namespace? using std::cout; using std::endl; //These little functions are used by the heap-sort algorithm #define PARENT(i) ((i - 1) / 2) #define LEFT(i) (2 * i + 1) #define RIGHT(i) (2 * i + 2) //First comes bubble-sort, the most brute-force sorting method. //Bubble-sort is a simple sorting algorithm that repeatedly steps //through the list to be sorted, compares each pair of adjacent items //and swaps them if they are in the wrong order void bubble_sort(int list[], int size) { int temp; for(int i=0; ii; j--) { if(list[j]key) { list[i+1]=list[i]; i=i-1; } list[i+1]=key; } } //Merge-sort is much faster than insertion-sort in general, and works by //dividing the array successively into smaller arrays, sorting them, and then //merging the results. merge_sort is written as two functions, `merge` which takes two //pre-sorted lists and merges them to a single sorted list. This is called on by merge_sort, //which also recursively calls itself. void merge(int list[], int p, int q, int r) { //n1 and n2 are the lengths of the pre-sorted sublists, list[p..q] and list[q+1..r] int n1=q-p+1; int n2=r-q; //copy these pre-sorted lists to L and R int L[n1+1]; int R[n2+1]; for(int i=0;i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---