Levels Tought:
Elementary,Middle School,High School,College,University,PHD
Teaching Since: | Apr 2017 |
Last Sign in: | 233 Weeks Ago |
Questions Answered: | 12843 |
Tutorials Posted: | 12834 |
MBA, Ph.D in Management
Harvard university
Feb-1997 - Aug-2003
Professor
Strayer University
Jan-2007 - Present
This programming assignment is to implement the following three sorting algorithms and to collect time performance measurements on them.
1. Mergesort, 2. Heapsort, 3. Quicksort.
The running time of each sorting algorithm must be measured in two ways:
1 A small array size, n = 32, to verify correctness
Run each algorithm on three sets of data:
(1) Sorted; (2) Reversely sorted; and (3) Randomly generated.
For simplicity, you may use integers. For each case, make sure the same original data is input to all three algorithms. Print both the sorted array and measured number of comparisons for each case to show the correctness of your algorithms.
2 Large array sizes to determine time complexity
Run each sorting algorithm on the following array sizes:
• n=210 =1,024
• n=215 =32,768
• n = 220 = 1,048,576
For each value of n, produce an array of n randomly generated elements only once. (For simplicity, you may use integers.) Again, make sure you provide the same randomly-generated array of data to all three sorting algorithms.
Tabulate the performace results, listing both the number of comparisons and the measured clock times. Use the tabulated number of comparisons to determine the time complexity. For example, does the data for quicksort verify O(n2) or O(nlogn) time, and what is the constant factor? Note that since you use a random sequence to sort, the running times should correspond to the average-case time complexities.
Â
-----------