1. what is sorting?

   1. re-arranging the elements of an array

   2. elements with smaller indices are smaller than elements with larger indices - ascending, increasing order

   3. elements with smaller indices are larger than elements with larger indices - descending, decreasing order

2. remember the two array algorithms

   1. element-first

      1. do_something(a[1..n])
           if something a[1], return
           do_something(a[2..n])
         

   2. array-first

      1. do_something(a[1..n])
           do_something(a[2..n])
           if something a[1], return
         

3. take array-first first

   1. the do-something is sort the array

      sort(a[1..n])
        sort(a[2..n])
        if something a[1], return
      

   2. an array of less than 2 elements is already sorted

      sort(a[1..n])
        if (n > 1)
          sort(a[2..n])
          if something a[1], return
      

   3. if a[2..n] is sorted, insert a[1] in its proper place

      sort(a[1..n])
        if (n > 1)
          sort(a[2..n])
          for (i = 2; (i <= n) && (a[i - 1] > a[i]; i++)
            swap a[i - 1], a[i]
      

   4. this is the insertion sort

      static void insertion_sort(int a[], int n) {
        if (n < 2) return;
        for (int i = n - 2; i >= 0; i--) {
          int t = a[i];
          int j;
          for (j = i + 1; (j < n) && (t > a[j]); j++)
            a[j - 1] = a[j];
          a[j] = t;
          }
        }
      

4. now take element-first

   1. the do-something is sort the array

      sort(a[1..n])
        if something a[1], return
        sort(a[2..n])
      

   2. select the smallest array element to be a[1]

      sort(a[1..n])
        if (n > 1)
          smallest = 1
          for (i = 2; i <= n; i++)
            if a[smallest] > a[i], smallest = i
          swap a[smallest], a[1]
          sort(a[2..n])
      

   3. this is the selection sort

      void selection_sort(int a[], int n) {
        if (n < 2) return;
        for (int i = 0; i < n - 1; i++) {
          int smallest = i;
          for (int j = smallest + 1; j < n; j++)
            if (a[smallest] > a[j]) smallest = j;
          int t = a[i];
          a[i] = a[smallest];
          a[smallest] = t;
          }
        }
      

This page last modified on 25 June 2001.