Question 1:

You are required to create a detailed analysis for each of the following array-based sorting algorithms:

(a) bubble sort in ascending order;
(b) quick_sort in ascending order, with partition choosing pivot in the middle of the sub-array;
(c) shell_sort in ascending order, with initial increment = n/2, then increment /=2;
(d) heap_sort in ascending order;

To analyse each of the abovementioned algorithms, please

1) provide a description of the algorithm in pseudocode;

2) conduct time complexity analysis of the algorithm (and also mention best case and worst case analysis if applicable);

3) conduct space complexity analysis of the algorithm;

4) Hand test your algorithm using your allocated 10-element long list of alphabetic characters as an illustrative example (see the Data Set below, and treat them as an array),

o count the number of comparisons;

o re-arrange your data set so as to achieve the best-case sorting of the algorithm;

o re-arrange your data set so as to achieve the worst-case sorting of the algorithm.

Question 2:

You are required to provide a detailed analysis of the following sorting algorithm applied to sorting linked list-based data structures.

merge_sort in ascending order Similar to the case of Question 1, analyse the algorithms by

1) providing a description of the algorithm in pseudocode;

2) conducting time complexity analysis of the algorithm (and also mention best and worst case analysis if applicable);

3) conducting space complexity analysis of the algorithm;

4) hand testing your algorithm using your allocated 10-element long list of alphabetic characters as an illustrative example (see the Data Set below, and treat them as sequential elements of an linked list),

o count the number of comparisons;
o re-arrange your data set so as to achieve the best-case sorting of the algorithm;
o re-arrange your data set so as to achieve the worst-case sorting of the algorithm.