Question 1:
You are required to undertake a detailed analysis of the AVL tree sorting algorithm for avl_sort.
To do this, consider to
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 scenarios);
3) Hand test your algorithm using your allocated 10-element long list of alphabetic characters as an illustrative/working example (see the Data Set below),
o count the number of comparisons;
o estimate the algorithm's storage requirement;
o re-arrange your data set so as to achieve the best-case sorting of the algorithm; and
o re-arrange your data set so as to achieve the worst-case sorting of the algorithm.
Question 2:
You are required to undertake a detailed analysis of the following sorting algorithm applied to sorting the multiway tree (of order 4 type) data structure:
- m_tree_sort
- b_tree_sort
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/scenarios if applicable);
3) hand testing your algorithm using your allocated 10-element long list of alphabetic characters as an illustrative/working example (see the Data Set below),
o count the number of comparisons;
o estimate the algorithm's storage requirement;
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.