Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A10 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A10 notes: Elementary Algorithms (revision)

In this lecture

• Kruse 6, 7.1, 7.2
• Standish 6, 13.5
• Langsam 6.1, 6.4, 7.1
• Deitel & Deitel 6.6, 6.8

• Takes O(n²) time in all cases.

• Takes O(n) time in the best case, and O(n²) time in the average and worse cases.
• Linear for "almost sorted arrays".
• Linear for arrays whose items are a constant distance from their final, sorted, position.

• Also called Sequential Search.
• Check each item in the list to see whether it is the target.
• Useful for unsorted lists, and small lists.
• Can be adapted to apply to linked lists.
• Takes O(n) time.

• Assumes the array is sorted.
• It is a "divide and conquer" algorithm. Divide the array into two parts, determine in which part the target lies, then concentrate on that part .
• Takes O(log(n)) time.

Code for this lecture

void selectionSort(float array[], int size)
{
  int j;
  int k;
  float tmp;
  int maxPosition;

  for (k = size-1; k > 0; k--)
  {
     /* Find the maximum in array[0],..,array[k] */
     maxPosition = 0;
     for (j = 1; j <= k; j++)
     {
        if (array[j] > array[maxPosition])
        {
        /*  Keep track of the where the maximum is. */
             maxPosition = j;
        }
     }
     /* Swap maximum value with array[k] */
     tmp = array[k];
     array[k] = array[maxPosition];
     array[maxPosition] = tmp;
  }
}

void insertionSort(int array[], int size)
{
 int j;
 int k;
 int current;

 for (k = 1; k < size; k++)
 {
    current = array[k];
    j = k;

    /* move current to correct position in */
    /* array[0],..,array[k]                */
    while (j > 0 && current < array[j-1])
    {
       array[j] = array[j-1];
       j--;
    }
    array[j] = current;
 }
}

/* If the target is in the array, its position is returned.
 * Otherwise -1 is returned.  */
int linearSearch(int array[], int size, int target)
{
   int i;

   for (i = 0; i < size; i++)
   {
      if (array[i] == target)
      {
         return i;
      }
   }
   return -1;
}

/* If the target is in the array, its position is returned.
 * Otherwise -1 is returned.
 * The array is assumed to be in increasing order.  */
int binarySearch(int array[], int size, int target)
{
   int lower = 0;
   int upper = size - 1;
   int mid;

   while (lower <= upper)
   {
      mid = (lower + upper)/2;
      if (array[mid] > target)
      {
          upper = mid - 1;
      }
      else if (array[mid] < target)
      {
          lower = mid + 1;
      }
      else
      {
          return mid;
      }
   }
   return -1;
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:04:10