Fundamental-Algorithms Assignment 1- Analysis & Comparison of Direct Sorting Methods Solved

Assignment No. 1: Analysis & Comparison of Direct Sorting Methods

Allocated time: 2 hours Implementation

You are required to implement correctly and efficiently 3 direct sorting methods (Bubble Sort, Insertion Sort – using either linear or binary insertion and Selection Sort)

Input: sequence of numbers < 𝑎1, 𝑎2, … , 𝑎𝑛 >
Output: an ordered permutation of the input sequence < 𝑎′1 ≤ 𝑎′2 ≤ ⋯ ≤ 𝑎′𝑛 >

You may find any necessary information and pseudo-code in your Seminar no. 1 notes (Insertion Sort is also presented in the book1 – Section 2.1). Make sure that, for each of the required sorting methods, you select its efficient version (whenever more than one version has been provided to you).

Thresholds
Threshold Requirements

5

7

Implement 1 direct sorting method, exemplify correctness and evaluate it (at least in the average case) – at least 1 chart

Compare 2 direct sorting methods (best, average and worst case), i.e. implementation, exemplify correctness and analysis (charts)

Compare 3 direct sorting methods (best, average and worst case), i.e. implementation, exemplify correctness and analysis (charts)

9
10 Discussion, interpretations, efficiency, compare, stability

Evaluation

! Before you start to work on the algorithms evaluation code, make sure you have a correct algorithm! You will have to prove your algorithm(s) work, so you should also prepare a demo on a small-sized input (which may be hard-coded in your main function).

1. You are required to compare the three sorting algorithms, in the best, average and worst cases. Remember that for the average case you have to repeat the measurements m times (m=5 should suffice) and report their average; also for the average case, make sure you always use the same input sequence for all three sorting methods – to make the comparison fair; make sure you know how to generate the best/worst case input sequences for all three methods.
2. This is how the analysis should be performed for a sorting method, in any of the three cases (best, average and worst):

   – vary the dimension of the input array (n) between [100…10000], with an increment of maximum 500 (we suggest 100);
   – for each dimension, generate the appropriate input sequence for the sorting method; run the sorting method counting the operations (i.e. number of assignments, number of comparisons and their sum).

   ! Only the assignments („=”) and comparisons („<”,”==”,”>”,”!=”) which are performed on the input structure and its corresponding auxiliary variables matter.

3. For each analysis case (best, average and worst), generate charts which compare the three methods; use different charts for the number of comparisons, number of assignments and total number of operations. If one of the curves cannot be visualized correctly because the others have a larger growth rate (e.g. a linear function might seem constant when placed on the same chart with a quadratic function), place that curve on a separate chart as well. Name your charts and the curves on each chart appropriately.
4. Interpret the charts and write your observations in the header (block comments) section at the beginning of your main .cpp file.