Question 1:
(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
|
(d) Heap sort in ascending order.
4. Pseudo code:
|
FUNCTIONHeapSortIMPORTsize
|
|
for (i¬ size/2 i>= 0i--)
|
|
ReHeap(size, i)
|
|
for (i¬ size-1 i> 0i--)
|
|
|
|
swap a[i] and a[0]
|
|
ReHeap(i, 0)
|
|
ENDFUNCTION
|
|
|
FUNCTIONReHeapIMPORTlen, parent
|
|
temp¬a[parent]
|
|
child¬2*parent + 1
|
|
while (child
|
|
|
|
if (child
|
|
child++
|
|
if (temp >= a[child])
break
|
|
a[parent] = a[child]
|
|
parent¬child
|
|
child ¬2*parent + 1
|
|
|
|
a[parent] ¬temp
|
ENDFUNCTIONTime Analysis of Mergesort
Assumption: N is a power of two.
For N = 1: time is a constant (denoted by 1)
Otherwise: time to mergesort N elements = time to mergesort N/2 elements plus time to merge two arrays each N/2 elements.
Time to merge two arrays each N/2 elements is linear, i.e. N
Thus we have:
(1) T(1) = 1
(2) T(N) = 2T(N/2) + N
Next we will solve this recurrence relation. First we divide (2) by N:
(3) T(N) / N = T(N/2) / (N/2) + 1
N is a power of two, so we can write
(4) T(N/2) / (N/2) = T(N/4) / (N/4) +1
(5) T(N/4) / (N/4) = T(N/8) / (N/8) +1
(6) T(N/8) / (N/8) = T(N/16) / (N/16) +1
(7) ......
(8) T(2) / 2 = T(1) / 1 + 1
Now we add equations (3) through (8) : the sum of their left-hand sides
will be equal to the sum of their right-hand sides:
T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + T(2)/2 =
T(N/2) / (N/2) + T(N/4) / (N/4) + T(2) / 2 + T(1) / 1 + LogN
(LogN is the sum of 1s in the right-hand sides)
After crossing the equal term, we get
(9) T(N)/N = T(1)/1 + LogN
T(1) is 1, hence we obtain
(10) T(N) = N + NlogN = O(NlogN)
Hence the complexity of the MergeSort algorithm is O(NlogN).