Searching & Sorting

Introduction

Searching and sorting are important problems in computer science and are used in some way in most non-trivial programs. Like most problems, there are multiple ways to do searching and sorting, with trade-offs for each.

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. This is similar to the very first guess-the-number algorithm we came up with. 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.

What is the Big-O time for linear 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 to write binary search pretty easily:

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.

How could we implement this algorithm?

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. (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

What is the Big-O of binary search?

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 not sorted:
1. for each item in the array:
1. if this item is bigger than the item to the right, swap them.

How could we implement bubble sort in C++?


template <typename type>
void bubbleSort(type* array, int size) {
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= (size-2); i++) {
if (array[i] > array[i + 1]) {
type temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
changed = true;
}
}
}
}


What is the Big-O of bubble sort?

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:


template <typename type>
void mergeSort(type* 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);
}
}


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.

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

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(n/2) + n$

The "T(n/2)" comes from the fact that we call the function recursively with half the input size. So the time to mergesort n elements is twice the time needed to mergesort (n/2) elements, plus n steps to merge the results.

We can then go ahead and plug in the value of T(n/2) using the recurrence relation:

$T(n) = 2 \cdot (2T(n/4) + n/2) + n$

Simplifying gives us:

$T(n) = 4 \cdot T(n/4) + 2n$

Expanding again gives us:

$T(n) = 4 \cdot (2T(n/8) + n/4) + 2n$

Simplifying gives us:

$T(n) = 8 \cdot T(n/8) + 3n$

Expand again:

$T(n) = 8 \cdot (2T(n/16) + n/8) + 3n$

Simplify again:

$T(n) = 16 \cdot T(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(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 base 2 of n times.

If we substitute k = log2(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. Thus we can say:

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

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

There are many more sorting algorithms, some of which can be visualized at: http://www.sorting-algorithms.com/.