computer programming
practical -6 sorting
Level 1: Basic sorts
Implement the selectionSort and insertionSort functions. Note that you can base your code on the sample code
used in lectures, although you will need to modify it from passing the data using an array and two indexes to passing it
using two pointers. The program will check that the final list is sorted correctly.
Level 2: Quicksort
Implement the quickSort function. The real work of quicksort happens in the partition operation, so it is probably best
to define a separate function to do the partitioning.
Level 3: Profiling
Gather data on the number of times that each algorithm compares and swaps items. A simple strategy is to use variables
to count the comparisons and swaps. The skeleton code declares comparisons and swaps variables for just this purpose.
To make use of them, modify your code to increment each variable where appropriate and then uncomment the output
statements to display their final values.
When you have profiling working, run the program and record the number of compares and swaps for each combination
of algorithm (-i, -s, and -q) and dataset organisation (-a, -v, and -r). Use dataset sizes of 1000, 2000, 5000, 10,000,
50000, and 100000. In the worst case, execution should not take much longer than 30 seconds.
For each run, compute a normalised execution count by dividing the actual count by the dataset size. For example, if
quicksort with a random dataset containing 10000 elements performed 161619 comparisons, the normalised count
would be 161619/10000 or about 16.2.
Finally, plot the comparison results (for the options -ia, -iv, -ir, -sa, -sv, -sr, -qa, -qv, and -qr) as separate lines on
a single set of axes with dataset size on the horizontal axis and execution count on the vertical axis. Repeat for swaps.
Choose scales so that the full range of values can be displayed and label the lines so you know which one is which. You
may find that using a log-log plot shows the values over the full range better.
Level 4: Improving quicksort
A simple implementation of quicksort is likely to perform badly for certain datasets. For example, the implementation
used as an example in lectures performs very poorly if the dataset is in reverse-sorted order.
The poor performance can be avoided by choosing a better pivot for the partitioning step. Common strategies include
selecting a random element or using the median of the first, middle, and last elements. In any case, the chosen pivot is
swapped with the last element before proceeding to do the partition as before.
Read about and implement one of the improvements to quicksort and show (by adding its profile data to the graphs of
Level 3) how much improvement you have achieved. Include a brief description of the method you implemented to
improve quicksort’s performance.
i want to need one coding program match to level 1 to level 4 submit code in Clion software . word file ..