Question

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: • Count the number of key comparisons, COMPCOUNT. To obtain this count, it is suggeted that you write a function COMPARE(X,Y), which will perform a comparison between X and Y and increment COMPCOUNT. Then, wherever you need to perform a key comparison in your algorithms. you simply make a call to this function. • Use the actual measured CLOCK time. You need to carry out the experiment in two parts.

Answer 1

The assignment is to implement Mergesort, Heapsort, and Quicksort, and measure performance by counting key comparisons using a COMPARE function and by measuring actual clock time. Analyzing the performance involves comparing these measurements across different data sets.

Step-by-step explanation:

Implementation of Sorting Algorithms and Performance Measurements

The assignment is focused on implementing three sorting algorithms: Mergesort, Heapsort, and Quicksort. After coding these algorithms, the student needs to assess their performance based on two measures: the number of key comparisons (COMPCOUNT) and the actual clock time. To accurately count key comparisons, the student should implement a function called COMPARE that will increase COMPCOUNT whenever a comparison is made between two elements. Measuring the actual clock time would typically involve capturing a timestamp before and after the sort operation, then calculating the difference.

Performance analysis will include noting the time efficiency and resource usage of each algorithm with respect to the given metrics under various data conditions. Each sorting algorithm has a typical best, average, and worst-case complexity which might influence the time it takes to run the algorithm on different data sets. Therefore, thorough testing should involve sorting arrays of different sizes and characteristics (e.g., already sorted, reverse-sorted, random elements) to get a full range of performance data.