CS sorting analysis
For this lab I tested ten different sorting methods by comparing the time it took to sort ordered, reverse ordered, and random ordered arrays of Integer objects of different sizes. I had to write a Timer class that started the timer before the sorting method was called and stopped the timer when the method was finished sorting the array. The elapsed time was calculated by another method in the Timer class so that the actual run time could be printed once the method completed. My test program contained methods to run all of the sorting methods given the size, type of array (ordered, reverse or random), and the number times to run the sorting method (all entered by the user) before the timer was stopped. For my timing experiment I carried out tests on an array of size 1,000 run 100 times through the method before printing the time (since it would be relatively fast for one iteration), an array of size 10,000 run 10 times, an array of size 25,000 run 1 time, and an array of 50,000 run 1 time. For the arrays of 1,000, 10,000, and 25,000 I did five trials for ordered, reverse, and random arrays to get a good average of the time it took since each run varied slightly. Since the array of 50,000 took a long time to run I conduct
All of the methods tested between insertion sort and bubble sort (simple quick sort, improved quick sort, merge sort recursive, heap sort, shell sort, and non recursive merge sort) all were approximately the same for all cases, which as seen in the graph is significantly less time than selection or insertion sort. Selection Sort: As seen the first graph, "Sort Comparisons," selection sort does not really have a best-case scenario. All three types of arrays took approximately the same amount of time. This is what was expected from the theoretical results. Shell Sort: Shell sort was significantly faster than insertion sort even though the worse case is still O(n2). All cases were approximately as fast as the O(n log n) methods but started to deviate more as the size increased. This is consistent with predicted results. Radix Sort: Radix sort ran a lot slower than expected. This is probably due to having to build the heaps every time and by using a linked queue instead of an array-based queue. All of the sizes took about an equal amount of time since each element was composed of a maximum of 4 digits. Merge Sort Non Recursive: This sort performed about at the same speed as the other "middle methods". The tests on random, reverse and ordered arrays were all about the same and very comparable to the recursive merge sort. Improved Quick Sort: Improved quick sort was fastest for the ordered list by a small amount for each of the sizes. Reverse and random were roughly the same. Overall the times for improved quick sort were slightly faster than simple quick sort, especially noticeably with the random list since there was a better chance to find a pivot closer to the middle valued element. Both quick sorts performed as thought. ed only two trials for each size on the thre
Some common words found in the essay are:
, Sort Radix, Insertion Sort, Sort Improved, Quick Sort, Sort Surprisingly, Sort Shell, Bubble Sort, Merge Sort, Sort Recursive, quick sort, improved quick sort, improved quick, merge sort, insertion sort, simple quick sort, simple quick, theoretical results, reverse random, average run, heap sort, sort recursive, merge sort recursive, array 50000 run, quick sort runs,
Approximate Word count = 1212
Approximate Pages = 5 (250 words per page double spaced)
|
