Assignment 02: Part I
Question 1:
Bubble sort in ascending order.
Pseudo code:
FUNCTION BubbleSort IMPORT 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
Quick sort in ascending order, with partition choosing pivot in the middle of the sub-array.
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] = pivotVal, so it can be put to the end)
ENDFUNCTION
Shell sort in ascending order, with initial increment =…