[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Friday, 03-May-2024 07:05:23 AEST Instructions:
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Under certain assumptions,
i.e. a test can only compare two elements,
e.g. a[ i ] <= a[ j ],
we cannot do better than
n . log( n ), in general, because:
There are n! permutations of n elements.
Each comparison gives you (at most) 1-bit of
information.
Stirling's
approximation:
log( n! ) ~ n . log( n ) + . . .
So, need to gather about n.log(n) bits of information
to discover the sorted permutation.
Saw Heap Sort previously.
Now, two more such fast sorts,
Merge Sort and Quick Sort . . .
How to solve a big problem? Another Strategy:
Divide it into two small sub-problems
solve each sub-problem
combine the results
- divide and conquer problem solving strategy
or paradigm- Alexander the Great.
merge b[ 1 .. 1 ] and b[ 2 .. 2 ] into a[ 1 .. 2 ]
merge sort [ 3 .. 4 ]
merge sort [ 3 .. 3 ] -- trivial
merge sort [ 4 .. 4 ] -- trivial
merge b[ 1 .. 1 ] and b[ 2 .. 2 ] into a[ 1 .. 2 ]
merge a[ 1 .. 2 ] and a[ 3 .. 4 ] into b[ 1 .. 4 ]
merge sort( [ 5 .. 8 ] )
. . . similarly . . .
merge b[ 1 .. 4 ] and b[ 5 .. 8 ] into a[ 1 .. 8 ]
[lecturer: briefly or can skip; class: study this at home!]
function mergeSort(int a[], int N) /* wrapper routine */
/* NB sorts a[1..N] */
{ int i;
int b[N]; /* -- the O(N) workspace */
for(i=1; i <= N; i++)
b[i]=a[i]; /* -- copy */
merge(b, 1, N, a); /* -- does the real work . . . */
}
[lecturer: briefly or can skip; class: study this at home!]
function merge(int inA[], int lo, int hi, int opA[])
/* sort (input) inA[lo..hi] into (output) opA[lo..hi] */
{ int i, j, k, mid;
if(hi > lo) /* at least 2 elements */
{ int mid = (lo+hi)/2; /* lo <= mid < hi */
merge(opA, lo, mid, inA); /* sort the ... */
merge(opA, mid+1, hi, inA); /* ... 2 halfs */
i = lo; j = mid+1; k = lo;
while( ... ) /* and merge them */
{
... merge the sorted inA[lo..mid] and inA[mid+1]
... into opA[lo..h]
}/*while */
}/*if */
}/*merge */
time complexity
merging n elements takes O(n)-time
there are log2(n) levels of recursion
[lecturer: draw picture]