Searching & Sorting

Introduction

Today we will look at some common array algorithms including searching and sorting. These are commonly needed in programs, and are good algorithms to know.

Linear Search

The simplest search algorithm is called linear search and is given below:

Set index to 0.
While index is less than the length of the array:

If the item at index is the one we're searching for, we're done!
Set index to index + 1.

If we got through the whole array without finding it, it wasn't there.

How could we add a linear search function to the program below?


import java.util.Random;
import java.util.Scanner;

public class LinearSearch {
    // size of array and max value
    final static int SIZE = 20;
    final static int MAX = 50;

    // return the index of target
    public static int linearSearch(int array[], int target) {




        return 0;
    }
    
    
    public static void main(String args[]) {
        // setup an array of random numbers
        int numbers [] = new int [SIZE];
        Random generator = new Random();
        for (int i = 0; i < SIZE; i++) {
            numbers[i] = generator.nextInt(MAX);
        }

        // print them
        System.out.print("[");
        for (int i = 0; i < SIZE; i++) {
            System.out.print(numbers[i] + ", ");
        }
        System.out.print("\b\b]\n");

        // test the search function
        Scanner in = new Scanner(System.in);
        System.out.print("Search for a number (-1 to quit)\n: ");
        int target;
        do {
            target = in.nextInt();
            if (target > 0) {
                System.out.print("Result: " + linearSearch(numbers, target) + "\n: "); 
            }
        } while (target > 0);
    }
}

Binary Search

Binary search is another alternative search algorithm that is much faster, but only works when the array is in sorted order.

It is exactly equivalent to the algorithm for playing guess the number when we can tell when we are too high or too low. The algorithm is given below:

Set min to 0.
Set max to array size - 1.
While min <= max:
1. Look halfway between min and max.
2. If this is the item we're searching for, we're done!
3. If this item is less than the one we're searching for, set min to guess + 1.
4. If this item is more than the one we're searching for, set max to guess - 1.
If we didn't find it, it must not be here!

How can we replace the function above with a binary search one?

What happens if the array is not sorted?

Linear search vs. Binary search

Binary search is clearly faster than linear search, but how much faster?

With binary search, every time we make a guess, we cut the possibilities in half. If we are guessing a number from 1 to 100, how many guesses will we make in the worst case scenario?

The most number of guesses we can make is the number of times we can divide 100 in half before we hit 0. When we divide 100 by two (rounding down) repeatedly we get:


100 50 25 12 6 3 1 0

So we can guess at most 7 times before we run out of possibilities. What if we want to guess a number from 1 to 1000?


1000 500 250 125 62 31 15 7 3 1 0

So we can guess at most 10 times. (The number of guesses is also equal to the log base 2 of the maximum number.)

Highest Number	Max Linear Search Guesses	Max Binary Search Guesses
10	10	4
100	100	7
1,000	1,000	10
10,000	10,000	14
100,000	100,000	17
1,000,000	1,000,000	20

Sorting

Oftentimes we want to sort an array according to some order. There are many different algorithms for doing this. One simple one we will discuss is bubble sort.

Bubble sort works by repeatedly looping through the array. As we go, we compare adjacent elements. If we find two that are out of order, we swap them and continue on. If we scan through the whole array and don't find anything out of order, then we're done.

The algorithm is given below:

set sorted to false.
while the array is not sorted:
1. Set sorted to true.
2. for each item in the array:
  1. if this item is bigger than the item to the right:
    1. swap them
    2. set sorted to false

How can we code this algorithm for the following program:


import java.util.Random;

public class BubbleSort {
    // size of array and max value
    final static int SIZE = 20;
    final static int MAX = 50;

    // sort the array
    public static void bubbleSort(int array[]) {

        boolean sorted = false;
        
        while (!sorted) {
            sorted = true;
            
            for (int i = 0; i < (array.length - 1); i++) {
                if (array[i] > array[i + 1]) {
                    // swap them
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    sorted = false;
                }
            }            
        }
    }
    
    
    public static void main(String args[]) {
        // setup an array of random numbers
        int numbers [] = new int [SIZE];
        Random generator = new Random();
        for (int i = 0; i < SIZE; i++) {
            numbers[i] = generator.nextInt(MAX);
        }

        // print them
        System.out.print("[");
        for (int i = 0; i < SIZE; i++) {
            System.out.print(numbers[i] + ", ");
        }
        System.out.print("\b\b]\n");

        // sort them
        bubbleSort(numbers);

        // print them again
        System.out.print("[");
        for (int i = 0; i < SIZE; i++) {
            System.out.print(numbers[i] + ", ");
        }
        System.out.print("\b\b]\n");
    }
}

Bubble sort is not the fastest sorting algorithm. We will discuss better ones later.