Part-1
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;
------------------------------------------------- ------------------------------------------------- ------------------------------------------------- ------------------------------------------------- ------------------------------------------------- ------------------------------------------------- -------------------------------------------------
The Tasks:
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 caseanalysis if applicable);
3)conduct space complexity analysis of the algorithm;
4)Hand test your algorithm using your allocated 10-element long list of alphabetic charactersas an illustrative example (see the Data Set below, and treat them as an array),
ocount the number of comparisons;
ore-arrange your data set so as to achieve the best-case sorting of the algorithm;
ore-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 caseanalysis if applicable);
3)conducting space complexity analysis of the algorithm;
4)hand testing your algorithm using your allocated 10-element long list of alphabeticcharacters as an illustrative example (see the Data Set below, and treat them as sequentialelements of an linked list),
ocount the number of comparisons;
ore-arrange your data set so as to achieve the best-case sorting of the algorithm;
ore-arrange your data set so as to achieve the worst-case sorting of the algorithm.
Data set
Allocated a 10-element array of alphabetic characters, which will be used for his/herillustrative hand testing of the algorithms.
Find his/her Dataset (or, Individual list to be sorted), of string format, ABCDEFGHIJ, which represents an array (or linked-list of) { A, B, C, D, E, F, G, H, I, J} (marked red).
Notes and awards:
The main objective of this assignment part is of algorithm analysis. As such, it doesn't require Java implementation of individual algorithms. However you are encouraged to implement them in Java if you have time to do so. If you attempt to do so, please save your executable java code/s separately, and submit them with your main document.
Your string will be KIMZUTONLV
Part-2
(a) Bubble sort in ascending order.
1. Pseudo code:
FUNCTION BubbleSortIMPORT array EXPORT array
FOR pass ¬ 0 TO (array.length-1)-1 DO¬Need N-1 passes to guarantee sorted
FOR ii ¬ 0 TO (array.length-1 - pass)-1 DO¬NOTE: 0-based array indexing
IF (array[ii] > array[ii+1]) THEN¬Avoid >= to keep the sort stable
temp ¬ array[ii]¬Swap out-of-order elements ii and ii+1
array[ii] ¬ array[ii+1]
array[ii+1] ¬ temp
ENDIF
ENDFOR
ENDWHILE
(b) Quick sort in ascending order, with partition choosing pivot in the middle of the sub-array.
2. Pseudo code:
FUNCTION QuickSort IMPORT array, leftIdx, rightIdx EXPORT array
IF (rightIdx > leftIdx) THEN¬Check that the array is > one element in size
pivotIdx¬ (leftIdx+rightIdx) / 2¬Pivot selection strategy: middle element
newPivotIdx¬ doPartitioning(array, leftIdx, rightIdx, pivotIdx)
QuickSort(array, leftIdx, newPivotIdx-1)¬Recurse: Sort left partition
QuickSort(array, newPivotIdx+1, rightIdx)¬Recurse: Sort right partition
//ELSE
// Base case: array is 1 element or smaller in size - already sorted
ENDIF
ENDFUNCTION
FUNCTION doPartitioning IMPORT array, leftIdx, rightIdx, pivotIdx EXPORT newPivotIdx
pivotVal¬ array[pivotIdx]
array[pivotIdx] ¬ array[rightIdx]¬Swap the pivotVal with the right-most element
array[rightIdx] ¬ pivotVal
// Find all values that are smaller than the pivot
// and transfer them to the left-hand-side of the array
currIdx¬ leftIdx
FOR (ii ¬ leftIdx TO rightIdx-1)
IF (array[ii]
temp¬ array[ii]¬Put this value to the left-hand-side
array[ii] ¬ array[currIdx]
array[currIdx] ¬ temp
currIdx¬ currIdx + 1
ENDIF
ENDFOR
newPivotIdx¬ currIdx
array[rightIdx] ¬ array[newPivotIdx]¬Put the pivot into its rightful place (the value at
array[newPivotIdx] ¬ pivotVal[newPivotIdx] is >= pivotVal, so it can be put to the end)
ENDFUNCTION
(c) Shell sort in ascending order, with initial increment = n/2, then increment /=2.
3. Pseudo code:
|
FUNCTIONShellSortIMPORTsize
|
|
for (inc¬size/2 inc>0inc /= 2)
|
|
|
|
for (i¬inci< sizei++)
|
|
|
|
j¬i - inc
|
|
while (j >= 0)
|
|
|
|
if (a[j] > a[j+inc])
|
|
|
|
swap a[j] and a[j+inc]
|
|
j -¬inc
|
|
else
|
|
j¬-1
ENDFUNCTION
|