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: