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.