# tree search/sorting algorithms & analysis

Tree Search/Sorting Algorithms & Analysis Objectives from the Unit Outline  Apply complexity theory to algorithms;  Discuss the relative merits of sort techniques using various abstract data types;  Discuss the relative merits of search techniques using various abstract data types; General Information:  Tree sorting algorithms are of the most important sorting algorithm type. The principles of tree sorting algorithms are, theoretically/conceptually, easy to understand. Yet they are practically harder to implement than those of the array-based ones, due to natures of the tree data structures. ————————————————- The Tasks: 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. Data set You’re allocated a 10-element array of alphabetic characters, which will be used for illustrative hand testing of the algorithms. Notes and awards: Although not required, you are encouraged to implement the abovementioned algorithms in Java if you can. Here is your dataset: KIMZUTONLV