CIS 3020 Part 8

Sequential Search

• Suppose that we have an unsorted array of numbers
• We know that a particular number is in the array
• We want the position of that number

Code

public int seqSearch(int[] a, int value, int index) {
  int result;
  if (index >= a.length) {
    result = -1;
  } else if (value == a[index]) {
    result = index;
  } else {
    result = seqSearch(a, value, index + 1);
  }
  return result;
}

Binary Search

• The binary search algorithm takes advantage of the fact that a set of values in an array are ordered
• We probe into the middle of the array and if we do not find the value that we are looking for, we throw 1/2 of the values away

Code

public int binSearch(int[] a, int target, int first, int last) {
  int result;
  int middle;
  middle = (first + last) / 2;
  if (last < first) {
    result = -1;
  } else if (a[middle] == target) {
    result = middle;
  } else if (a[middle] < target) {
    result = binSearch(a, target, middle + 1, last);
  } else {
    result = binSearch(a, target, first, middle - 1);
  }
  return result;
}

Problem

• Note that binary search is fast
• But, to use it we must have the values sorted and sorting can be expensive to do
• If we are only going to make one or two searches, it might not be worth sorting the values
• If we are going to make repeated searches (student records, bank records, inventory), sorting the values will have great benefit

for loop

• The structure of a for loop is:

for (<init>; <bool expr>; <incre>)
     <statement>;

Which should you use?

• Is the number of times you will perform some action fixed and will not change?
• Will you need to perform an action a variable number of times including possibly zero times?
• Will you need to perform an action a variable number of times including at least once?

Selection Sort

Algorithm

1. For all positions, k, in the array from n down to one
2. Find the largest element in the subarray 0..k
   1. Save k as the position of the largest so far
   2. For all values of j from k-1 down to 0
   3. If the element at j is bigger than the largest so far, save j as the position of the largest so far
3. If the largest element is not in position k then switch the largest element with the one at position k

Code

public void selectSort(int[] val) {
  int k, j, indexOfMax, temp;
  for (k=val.length-1; k>=1; k--) {
    indexOfMax = k;
    for (j=k-1; j>=0; j--) {
      if (val[j] > val[indexOfMax]) {
        indexOfMax = j;
      }
    }
    if (indexOfMax != k) {
      temp = val[k];
      val[k] = val[indexOfMax];
      val[indexOfMax] = temp;
    }
  }
}

Bubble Sort

Algorithm

1. Repeat
2. For each pair of adjacent array elements do
   1. Initialize noExchanges to True
   2. For each pair of adjacent array elements do
3. If the values of the pair are out of order then
   1. Exchange the values
   2. Set noExchanges to False

Code

public void bubbleSort(int[] val) {
  boolean noExchanges;
  int first, pass, temp;
  pass = 1;
  do {
    noExchanges = true;
    for (first = 0; first <= val.length - 1 - pass; first++) {
      if (val[first] > val[first + 1]) {
        temp = val[first];
        val[first] = val[first + 1];
        val[first + 1] = temp;
        noExchanges = false;
      }
    }
    pass = pass + 1;
  } while (! noExchanges);
}