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

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   

 

You may find any necessary information and pseudo-code in your Seminar no. 1 notes (Insertion Sort is also presented in the book[1] – 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
Implement 1 direct sorting method, exemplify correctness and evaluate it (at least in the average case) – at least 1 chart
7
Compare 2 direct sorting methods (best, average and worst case), i.e.

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

implementation, exemplify correctness and analysis (charts)
10
Discussion, interpretations, efficiency, compare, stability
 

 

 

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.