[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:45:43 AEDT
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.

Recursive Sorts:   Introduction

How to solve a big problem?  Another Strategy:

- divide and conquer problem solving strategy or paradigm- Alexander the Great.

Merge Sort( a [ ] )

Top-down Merge sort, e.g. merge_sort( 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

  1. merging n elements takes O(n)-time
  2. there are log2(n) levels of recursion   [lecturer: draw picture]
  3. n elements are merged at each level
  4. therefore O( n . log(n) )-time in total, always

space complexity

Stability

Code: ..../C/List/ for linked lists, ..../C/Sort/ for arrays

There is also a bottom-up merge sort,   e.g. merge sort a[ 1 .. 8 ]

By the way:

©
L
.
A
l
l
i
s
o
n

Quick Sort

Another idea: partition the array:
  1. move all the "small" elements to the left hand and move all the "large" elements to the right hand

  2. sort the small elements

  3. sort the large elements

Beware

Partitioning:   Dutch National Flag (DNF) problem

Properties of DNF (only):

Dutch National Flag related to Quick Sort

[an efficient quick sort; class: study this at home!]
quicksort(int a[], int lo, int hi)   /* sort a[lo..hi] */
 { int left, right, median, temp;

   if( hi > lo ) /* i.e. at least 2 elements, then */
    { left=lo; right=hi;
      median=a[lo];  /* NB. just an estimate! */

      while(right >= left) /* partition a[lo..hi] */
      /*INV: a[lo..left-1] <= median & a[right+1..hi] >= median */
       { while(a[left]  < median) left++;

         while(a[right] > median) right--;

         if(left > right) break;

         temp=a[left]; a[left]=a[right]; a[right]=temp; /* swap */
         left++; right--
       }
      /* a[lo..left-1] <= median and a[right+1..hi] >= median
         and left > right */

      quicksort(a, lo, right); /* divide and */
      quicksort(a, left,  hi); /* conquer */
    }
 }/*quicksort*/

Properties of Quick Sort

Recursive Sorting Summary

Prepare

© L.Allison, Sunday, 28-Nov-2021 04:45:43 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/06sort3.shtml
Computer Science, Software Engineering, Science (Computer Science).