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.
#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]-1 and list[i]>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 list.nodes[index]) { largest = left; } else { largest = index; } if(right list.nodes[largest]) { largest = right; } if(largest != index) { exchange_temp = list.nodes[index]; list.nodes[index] = list.nodes[largest]; list.nodes[largest] = exchange_temp; max_heapify(list, largest); } } //build_max_heap turns an array into max-heap form by repeatedly calling //max_heapify void build_max_heap(heap list) { list.heap_size = list.length; for(int i = floor(list.length/2); i>=0; i--) { max_heapify(list, i); } } //Since one property of a max-heap is that the first element is the largest, //heap_sort swaps this element with the last element, then re-heapifies the //rest, recursively until the whole array is sorted void heap_sort(int list[], int size) { int exchange_temp; heap tempheap; tempheap.length = size; tempheap.nodes = list; tempheap.heap_size = size; build_max_heap(tempheap); for(int i= tempheap.length - 1; i>=1; i--) { exchange_temp = tempheap.nodes[0]; tempheap.nodes[0] = tempheap.nodes[i]; tempheap.nodes[i] = exchange_temp; tempheap.heap_size = tempheap.heap_size - 1; max_heapify(tempheap,0); } } //Quicksort works by dividing the array based upon a \'pivot\' element, everything //to the right of it are greater than or equal to the pivot, everything //smaller than the pivot are moved to the left. Then the left and right //arrays are sorted in the same way. Works great on a random array, but //data that is nearly already sorted are very slow by this method. int partition(int list[], int p, int r) { int pivot, index, exchange_temp; pivot = list[r]; index = p - 1; for(int i = p; i < r; i++) { if(list[i] <= pivot) { index++; exchange_temp = list[i]; list[i] = list[index]; list[index] = exchange_temp; } } exchange_temp = list[r]; list[r] = list[index+1]; list[index+1] = exchange_temp; return index+1; } void quicksort_aux(int list[], int p, int r) { int q; if(p(t2-t1).count(); mg_temp_timer += mgtime ; t1 = std::chrono::high_resolution_clock::now(); heap_sort(rlist2,npointsi); t2 = std::chrono::high_resolution_clock::now(); hptime = std::chrono::duration_cast(t2-t1).count(); hp_temp_timer += hptime ; t1 = std::chrono::high_resolution_clock::now(); quick_sort(rlist3,npointsi); t2 = std::chrono::high_resolution_clock::now(); qktime = std::chrono::duration_cast(t2-t1).count(); qk_temp_timer += qktime ; //I know that bubble and insertion grow as O(n^2) in the average //case, so I won\'t bother with them once the array grows too large. if(npointsi<=500) { t1 = std::chrono::high_resolution_clock::now(); bubble_sort(rlist4,npointsi); t2 = std::chrono::high_resolution_clock::now(); bbtime = std::chrono::duration_cast(t2-t1).count(); bb_temp_timer += bbtime ; t1 = std::chrono::high_resolution_clock::now(); insertion_sort(rlist5,npointsi); t2 = std::chrono::high_resolution_clock::now(); instime = std::chrono::duration_cast(t2-t1).count(); ins_temp_timer += instime ; } else { bb_temp_timer = 0.0; ins_temp_timer = 0.0; } } merge_timelist[icounter] = mg_temp_timer/nave; heap_timelist[icounter] = hp_temp_timer/nave; quick_timelist[icounter] = qk_temp_timer/nave; insertion_timelist[icounter] = ins_temp_timer/nave; bubble_timelist[icounter] = bb_temp_timer/nave; icounter++; } //Is there a better way to generate this data table? A more C++ way? FILE * resultsfile; resultsfile=fopen(\"results-comparison_sort-noBS.dat\",\"w\"); for(int j=0;j< npoints;j++) fprintf(resultsfile, \"%5e \\t %10.2f \\t %10.2f \\t %10.2f \\t %10.2f \\t %10.2f \ \",nplist[j], bubble_timelist[j], insertion_timelist[j], merge_timelist[j], heap_timelist[j], quick_timelist[j]); fclose(resultsfile); }
Homework Sourse
