Data Structures Expert

Closed - This job posting has been filled.

Job Description

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),
- count the number of comparisons;
- re-arrange your data set so as to achieve the best-case sorting of the algorithm;
- re-arrange your data set so as to achieve the worst-case sorting of the algorithm.
Task 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 Task 1, analyse the algorithms by
1) providing 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 testing your algorithm using your allocated 10-element characters as an illustrative example
(see the Data Set below, and treat them as sequential elements of an linked list)
- count the number of comparisons;
- re-arrange your data set so as to achieve the best-case sorting of the algorithm;
- re-arrange your data set so as to achieve the worst-case sorting of the algorithm.
Data Set: KGJLZNEHSV

Budget - $3 per sorting algorithm
Time - 1 day