A4 - Search and Sort Algorithms

Part 1 - 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.

Selection Sort

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.

Bubble Sort

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.

Task #1

You can complete this task 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).

Part 2 - Implementing an Algorithm from Pseudocode

Pseudocode can be considered a compromise between human readable language and computer readable language. It is structured the same way as computer code, but instead of being written in any specific programming language each step is described in a human language (in our case, English). Normally, it is reasonably easy for a programmer to translate a program written in pseudocode into a computer programming language of their choosing.

Your main task in this assignment will be to implement one of the more advanced algorithms we looked at, given its pseudocode. You will be able to choose between Selection Sort, Bubble Sort and Binary Search.

The pseudocode for each algorithm, along with a few hints, are below:

Selection Sort

unsorted = [5, 3, 8, 12, 3, 8, 9, 10, 15, 4]
sorted = []

repeat for as long as the length of the unsorted list is more than zero:
    min = the first item in the unsorted list
    min_pos = 0
    for each item in the unsorted list:
        if the current item is less than min:
            min = the current item
            min_pos = the position of the current item
    add min to the end of the sorted list
    remove min from the unsorted list
print the contents of the sorted list

Hints

To add an item to the sorted list:

sorted.append(min)

To remove an items from the unsorted list:

unsorted.pop(position)

Bubble Sort

data = [5, 3, 8, 12, 3, 8, 9, 10, 15, 4]

for each item in the list:
    for each item in the list minus 1:
        if the next list item is less than the current list item:
            swap the current list item and the next list item
print the contents of the data list

Hints

The outer loop is only there because this process needs to be repeated a number of times. The inner loop is the one where you will be comparing the two values and swapping them if necessary.
Swapping two a value in the list with it's neighbour will require the following three lines of code:
```
temp = data[i]
data[i] = data[i+1]
data[i+1] = temp
```

Binary Search

data = [1, 3, 4, 6, 7, 9, 13, 16, 18, 20, 27, 33, 42, 45, 60]

search_for = 45
lower_bound = 0
upper_bound = the position of the last item in the list
repeat as long as upper_bound is greater than or equal to the lower_bound:
    pos = the average of lower_bound and upper_bound, rounded down if necessary
    if data[pos] is equal to search_for:
        print the value of pos
        exit the loop
    if data[pos] is less than search_for:
        lower_bound = pos+1
    if data[pos] is greater than search_for:
        upper_bound = pos-1

Hints

The // operator (integer division) is used to divide and always round down. Therefore, the line where you need to average lower_bound and upper_bound should look like this:

pos = (upper_bound + lower_bound) // 2

To exit a loop in Python, use the break command (with no brackets at the end of it).

Hints on choosing a looping structure

The pseudocode should give you a good sense of when you need to use a while loop and when you need to use for loop. What might be less obvious is deciding which style of for loop to use:

Style #1:

for current_item in data:
    do something with currentItem

Style #2:

for i in range(len(data)):
    do something with i and data[i]

Style #1 is simpler, and can be used under the following conditions:

you only need to see the current item in the list (not any of its neighbours)
you don't need to know what position in the list you are at

If the above conditions are not met and you need to go with Style #2, remember that

i represents your current position in the list, starting at zero
data[i] represents the list item at the current position. You can also access list items at other positions, for example, using data[i+1] to get the list item in the next position.

Task #2

Choose ONE of the advanced algorithms described above and implement it in a file called a4.py.