Home CPSC 340

Searching and Sorting

 

Overview

Searching and sorting are two of the most common sorts of algorithms there are. Most decent-sized programs will need to search and/or sort some place in them. They are also a key idea in many algorithms. For instance, data structures like hash tables and binary search trees are designed with search in mind. And heaps maintain a sorted order internally.


 

Linear Search

The simplest search algorithm is called "linear search". It works by starting at the beginning of the things we are searching through and examining them, one by one, until we find the one we are looking for. The algorithm is given below:

  1. Set index to 0.
  2. While index is less than the length of the array:
    1. If the item at index is the one we're searching for, we're done!
    2. Set index to index + 1.
  3. If we got through the whole array without finding it, it wasn't there.

This algorithm is of course linear (hence the name), so it's $O(n)$.

A Java implementation is available in LinearSearch.java.


public static boolean linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        System.out.println("Searching at " + i);

        if (array[i] == target) {
            System.out.println("Found " + target + " in slot " + i + "\n");
            return true;
        }
    }

    System.out.println(target + " was not found.\n");
    return false;
}

 

Binary Search

If our array of items is sorted in order, we actually can do better than linear search.

To do this, we can start the search in the middle of the array. After that, we know that the item is either there (in which case we're done), or it's to the left, or it's to the right. Then we pick the middle of the left half, or the right half, and repeat the process.

We can use recursion in our binary search, coming up with an algorithm like this:

  1. If the array is empty, the item wasn't here.
  2. Find the middle item from the array.
  3. If it's the thing, we're looking for, we're done.
  4. If it's less, recursively search the left half.
  5. If it's more, recursively search the right half.

A Java implementation is available in BinarySearch.java.


public static boolean binarySearch(int[] array, int target, int left, int right) {
    if (left > right) {
        System.out.println(target + " was not found.\n");
        return false;
    }

    int middle = (left + right) / 2;
    System.out.println("Searching at " + middle);

    if (array[middle] == target) {
        System.out.println("Found " + target + " in slot " + middle + "\n");
        return true;
    } else if (array[middle] < target) {
        return binarySearch(array, target, middle + 1, right);
    } else {
        return binarySearch(array, target, left, middle - 1);
    } 
}

public static boolean binarySearch(int[] array, int target) {
    return binarySearch(array, target, 0, array.length - 1);
}

Like other recursive methods, this includes a helper method which sets the initial search parameters.


 

Binary Search Analysis

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. In general we have:

$searches = \lceil log_2(n) \rceil$

Highest NumberMax Linear Search GuessesMax Binary Search Guesses
10104
1001007
1,0001,00010
10,00010,00014
100,000100,00017
1,000,0001,000,00020
1,000,000,0001,000,000,00030

Because of this, binary search is $O(log_2 n)$.

Remember that we can only use binary search when the array is sorted. Also, we can only use binary search on arrays, not linked lists.


 

Bubble Sort

Bubble sort is a very simple sorting algorithm. It 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.

Bubble sort is so called because the large items "bubble up" to the end of the array.

The bubble sort algorithm can be expressed in pseudocode:

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

Here the algorithm is implemented in Java:


public static void bubbleSort(int[] array) {
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i <= (array.length - 2); i++) {
            if (array[i] > array[i + 1]) {
                int temp = array[i + 1];
                array[i + 1] = array[i];
                array[i] = temp;
                changed = true;
            }
        }
    }
}

To find the Big-O complexity of this algorithm, we will look at the two loops. The inner loop runs on the order of n times. The first iteration will actually run n - 2 times. Each subsequent iteration will run one fewer times. On average, it will run $\frac{1}{2} n $ times. Remembering that we ignore constant coefficients, that's $O(n)$ times.

The while loop is a bit more complicated, since we can't tell from looking at it how many iterations it will take. But if we think about it, we will see that, in the worst case scenario, we have the biggest array element in the very first position, like this:


99 4 28 16 78 36

That 99 will only move one space to the right for each pass of the algorithm. So in this case, there will be $n - 1$ iterations of the while loop. In the average case, the first item will have to go somewhere in the middle, which would take $\frac{1}{2} n$ iterations. Either way, this loop runs $O(n)$ times as well.

Because these loops are nested, the overall complexity for the algorithm is $O(n^2)$.

Other simple sorting algorithms like selection sort and insertion sort are also $O(n^2)$


 

Merge Sort

The last sort function we will look at is a little different. It uses recursion and is also, generally, much more efficient than bubble sort.

The basic approach is to split the array into two halves, a left half and a right half. Then we sort each half. Then to finish up, we merge the two sorted halve back together. We will talk about how to merge the halves in a bit.

This algorithm is recursive because, in defining how we sort an array, we sort two smaller arrays. We need to add a base case. In the case of sorting, our base case is when the array has zero or one elements (these arrays are already sorted). The algorithm can be expressed as:

  1. To Mergesort an array:
    1. If the array has 0 or 1 items, we're done.
    2. Mergesort the left half.
    3. Mergesort the right half.
    4. Merge the two halves together to make a new, sorted, array.

This can be converted into a recursive function:


public static void mergeSort(int[] array, int start, int end) {
    if (start < end) {
        int middle = (start + end) / 2;

        // sort left half
        mergeSort(array, start, middle);

        // sort right half
        mergeSort(array, middle + 1, end);

        // merge the two halves
        merge(array, start, end);
    }
}

public static void mergeSort(int[] array) {
    mergeSort(array, 0, array.length - 1);
}

Now all we need to do is figure out how to merge two arrays back together. The way we will do this is by looking at both arrays. We will take the first value from the array with the smallest number. Then we will do this again and again until one of the arrays runs out. Then we'll add the rest of the remaining array in.

The merge algorithm can be expressed as:

  1. Set the result array to empty.
  2. While both of the arrays have data:
    1. If the left array value is less than that of the right array, add the left array value to result.
    2. Otherwise, add the right array value.
  3. Add the rest of the remaining array to the result array.

In Java code, that looks like this:


public static void merge(int[] array, int start, int end) {
    int middle = (start + end) / 2;
    int temp_index = 0;

    // create a temporary array
    int[] temp = new int[end - start + 1];

    // merge in sorted data from the 2 halves
    int left = start;
    int right = middle + 1;

    // while both halves have data
    while ((left <= middle) && (right <= end)) {
        // if the left half value is less than right
        if (array[left] < array[right]) {
            // take from left
            temp[temp_index] = array[left];
            temp_index++;
            left++;
        }
        else {
            // take from right
            temp[temp_index] = array[right];
            temp_index++;
            right++;
        }
    }

    // add the remaining elements from the left half
    while (left <= middle) {
        temp[temp_index] = array[left];
        temp_index++;
        left++;
    }

    // add the remaining elements from the right half
    while (right <= end) {
        temp[temp_index] = array[right];
        temp_index++;
        right++;
    }

    // move from temp array to the original array
    for (int i = start; i <= end; i++) {
        array[i] = temp[i - start];
    }
}

With the merge function, we can complete a merge sort program.


 

Sort Efficiency

Merge sort is a little more complicated to analyze due to the recursion. The first thing to do is analyze the merge algorithm. This algorithm loops through the array from start to end, merging elements as we go along. It should be clear that this algorithm takes an amount of time proportional to the size of the array, so it's $O(n)$.

Next we have to look at the whole mergesort algorithm. The algorithm works by calling itself twice on half the input size, then merging the results with the merge algorithm. We can express the time $T$ taken by this algorithm with the following recurrence relation:

$T(n) = 2 \cdot T(\frac{n}{2}) + n$

This is saying that the time taken to mergesort an array of size $n$ is twice the time taken to sort an array half that size (the two recursive calls), plus the $n$ time needed to do the merge.

This is a recurrence relation which is a relation which is recursive, because in defining $T(n)$, we have a reference to the relation $T$. This doesn't in an of itself tell us anything helpful.

To try to make sense of this relation, we can go ahead and plug in the value of $T(\frac{n}{2})$ using the recurrence relation:

$T(n) = 2 \cdot (2T(\frac{n}{4}) + \frac{n}{2}) + n$

Simplifying gives us:

$T(n) = 4 \cdot T(\frac{n}{4}) + 2n$

Expanding again gives us:

$T(n) = 4 \cdot (2T(\frac{n}{8}) + \frac{n}{4}) + 2n$

Simplifying gives us:

$T(n) = 8 \cdot T(\frac{n}{8}) + 3n$

Expand again:

$T(n) = 8 \cdot (2T(\frac{n}{16}) + \frac{n}{8}) + 3n$

Simplify again:

$T(n) = 16 \cdot T(\frac{n}{16}) + 4n$

It should be clear that there is a pattern emerging. No matter how many times we expand this out, we will get something of the form:

$T(n) = 2^k \cdot T(\frac{n}{2^k}) + kn$

Where $k$ is the number of times we expand the formula.

The question then becomes how many times do we expand the formula? How many times does the mergesort algorithm recurse?

The answer is the number of times we can divide the array in half before we hit the base case. How many times can a number $n$ be divided by 2 until we hit 1? The answer is $log_2(n)$ times.

If we substitute $k = log_2(n)$ in our formula, we get:

$T(n) = 2^{log2(n)} \cdot T(n / 2^{log2(n)}) + log2(n) \cdot n$

Then we can use the fact that an exponent and a logarithm are opposite operations to get:

$T(n) = n\cdot T(1) + log2(n) \cdot n$

The value $T(1)$ is the time taken to mergesort an array with 1 item. This is the base case and can be done in constant time (one item is always sorted). That gives us:

$T(n) = n\cdot log2(n) + n$

When we use Big-O notation, we only care about the term that dominates. The extra "+ n" is relatively unimportant for large values of n because the other part is larger. Also the base of the logarithm is not necessary to state (it is essentially a constant factor) Thus we can say:

$T(n) = O(n\cdot log(n))$

This means that the algorithm is faster than a $O(n^2)$ one (like bubble sort), but not as fast as a linear algorithm:

A graph showing n squared, n log n, and n.  The n squared line
is the highest, then n log n, and then n is the lowest
Comparison of n log(n) to other complexities

Mergesort is significantly faster than simpler sorts like bubble sort for large input sizes. It actually turns out that $O(n \log{} n)$ is the best we can do for general purpose sorting algorithms. There are a few other sorting algorithms with this complexity including quicksort, and heapsort (which we will look at when we get to heaps).

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.