Lecture Notes for Computer Algorithms I

18 September 2003 - Array Algorithms

• arrays have a regular structure

  • an value followed by an array

  • an array followed by a value

  • a value between two arrays

  • in general, a single value and smaller arrays

    • note the smaller arrays have the same structure

• array algorithms can have a structure similar to arrays

  • an algorithm is a recipe for performing a calculation

  • do_something(a[1..n])
      if do_something(a[1]) is o.k. return
      do_something(a[2..n])
    

  • do_something(a[1..n])
      do_something(a[2..n])
      if do_something(a[1]) is o.k. return
    

  • array pictures are helpful in understanding these algorithms

• example - linear search

  • the problem - given an array a and a value x, return the index of x in a or -1 if x doesn't appear in a.

  • which algorithm form to use

    • the value doesn't interact with the array - use the first form.

  • int find(a[1..n], x)
      if a[1] == x return i
      if 1 == n return -1
      return find(a[2..n], x)
    

    See the C++ implementation.

  • what's the array picture?

• example - star strings

  • problem - return the leftmost index of the longest sequence of stars in a string

  • which algorithm form to use

    • the value does interact with the array, use the second form

  • int star_string(a[1..n])
      i = star_string(a[2..n])
      if a[1..n] forms a new longer star string
        set i properly
      return i
    

    See the C++ implementation.

  • what's the array picture?

• what is sorting?

  • re-arranging the elements of an array

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

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

• remember the two array algorithms

  • element-first

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

  • array-first

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

• take array-first first

  • the do-something is sort the array

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

  • 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
    

  • 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]
    

  • 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;
        }
      }
    

• now take element-first

  • the do-something is sort the array

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

  • 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])
    

  • 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 3 December 2003.