A2 - Algorithm Visualizations

In this assignment, we are going to look at three algorithms.

Selection Sort

This is the simplest method of sorting a list. You go through each item in the list to determine which value is lowest, then remove the lowest item and add it to a new list. You repeat this process until the original list is empty. The new list will then contain all the original values in sorted order.

In the visualization below, the highlighted number is the lowest one found, and therefore the next one to be transferred to the sorted list.

Bubble Sort

This is another method of sorting that does not require a second list to be created. It involves going through the list several times, and comparing each list item to its neighbour to the right. Every time the value on the right is less than the value on the left, those two values are swapped. Eventually this results in a fully sorted list.

Binary Search

This is an efficient method of searching through sorted data, such as a dictionary. You would start by looking at the value in the middle of the list. If the value you are searching for is lower than that, you would repeat the process with just the lowest half of the list. Similarly, if the value you are searching for is higher than the middle item, you would repeat the process with just the upper half of the list. You can continue in this manner, each time cutting the size of the list in half, until you have found the value you are looking for.

Your Task

You can complete this assignment either with pencil and paper (probably easiest), or as a digital document.

Create your own visualization of each of the above algorithms using the same process as the examples, but using your own data. Please choose your data according to the following guidelines:

• Selection Sort and Bubble Sort - Use a list of five numbers that are very randomized, so that your Bubble Sort will contain at least four swaps.
• Binary Search - Use a list of 15 numbers. They should be sorted, but you should skip some numbers to make it more interesting (ie, don't just use the numbers 1 through 15).