Insertion Sort—Python

Insertion sorts are a common sorting technique that many computer science students are asked to learn. Here is a Python implementation of an Insertion Sort.

def insertion_sort(items):
    for i in range(2, len(items) - 1):
        item = items[i]
        j = i
        while (items[j - 1] > item) and (j >= 1):
            items[j] = items[j - 1]
            j -= 1
        items[j] = item

if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    insertion_sort(items)
    print(items)

Insertion sorts use nested loops and test if an item at the end of the list is less than an item in the front of the list. If they are, the code does a swap.

When run, we get this output:

['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Tina Belcher', 'Louise Belcher']
Advertisements

Quick Sort—Python

Quick sort is a sorting algorithm that uses recursion and nested loops to sort items. Here is an implementation in Python

def split_list(unsorted, low, high):
    # Set our temp item at the low end
    item = unsorted[low]

    # Variables for tracking left and right
    # side of the list
    left = low
    right = high

    # loop until our left side is less than right side
    while left < right:

        # Move left to the right while it's less than item
        while unsorted[left] <= item and left  item:
            right -= 1

        # Check if we need to swap elements
        if left  low:
        # Split unsorted into two lists
        index = split_list(unsorted, low, high)

        # Sort the left hand of the list using recursion
        quick_sort(unsorted, low, index - 1)

        # Sort the right hand of the list using recursion
        quick_sort(unsorted, index + 1, high)


if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    quick_sort(items, 0, len(items) - 1)
    print(items)

When run, this code will produce the following output

['Bob Belcher', 'Linda Belcher', 'Tina Belcher', 'Gene Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Louise Belcher', 'Tina Belcher']

The key in this algorithm is that we split our list into two halfs and then use recursion to sort each half. The work of swapping elements takes place in the split_list function. However, the quick_sort function is responsible for calling split_list until all items are sorted.

Selection Sort—Python

Selection sorts are a very common method of sorting. Here is a selection sort that is implemented in Python.

def selection_sort(items):
    for i in range(len(items) - 1):
        # Assume that the smallest item is located at index i
        smallest = i

        # Now loop through the rest of the list
        for j in range(i + 1, len(items)):
            # Is our item at index j smaller than our smallest item?
            if items[j] < items[smallest]:
                smallest = j

        #  Now swap elements to perform the sort
        temp = items[smallest]
        items[smallest] = items[i]
        items[i] = temp

if __name__ == '__main__':
    items = ['Bob Belcher', 'Linda Belcher', 'Gene Belcher', 'Tina Belcher', 'Louise Belcher']
    print(items, '\n')

    print('Sorting...')
    selection_sort(items)
    print(items)

Selection sorts use nested loops to iterate over a list. We check if the item at index j is less than the current smallest item. If j is smaller than smaller, we assign smaller to j.

Once we complete the nested loop, we can perform a swap. Our driver program demonstrates this with strings, but thanks to Python's duck typing system, this will sort any object that implements __lt__.

When run, we get this output

['Bob Belcher', 'Linda Belcher', 'Gene Belcher', 'Tina Belcher', 'Louise Belcher'] 

Sorting...
['Bob Belcher', 'Gene Belcher', 'Linda Belcher', 'Louise Belcher', 'Tina Belcher']

Continue—Python

The continue statement is used in Python to return program execution to the beginning of a loop. For a review of loops see for loops and while loops.

Let’s begin with a code example

names = ['Bob Belcher',
         'Linda Belcher',
         None,
         'Louise Belcher',
         'Tina Belcher',
         None,
         'Gene Belcher']

bob = ''
for name in names:
    if name is None:
        continue    # Go back to the top of the loop since
                    # since we can't do comparisons on None
    if 'Bob' in name:
        bob = name

In this situation, we have a list object that has a combination of Strings and Python’s None object. What we are doing is trying to find ‘Bob’ but to do that, we need a way to skip over the None objects or our program will crash. Lines 11 and 12 in the above code snippet do the job of checking if the elemnt name is None first. If it turns out that the element is None, line 12 uses the continue statement to return the execution to the top of the loop.

The continue keyword is useful when we process a loop of mixed types. Let’s take another example of where the keyword is also useful.

while True:
    fileName = input('Enter a file name => ')
    try:
        lines = open(fileName, 'r').readlines()
    except FileNotFoundError:
        print('Try a different file')
        continue # We can't do the next part because
                 # couldn't open the file
    for line in lines:
        print(line)

This code snippet asks the user for a file and then attempts to open the file for processing. However, if for some reason we can’t open the file, the program won’t be able to process lines 9 and 10. For this reason, we use the continue keyword to return program execution to the top of the loop and give the user an opportunity to open a different file.

Pass—Python

Python has a special pass keyword to do nothing. Here’s a code example

countdown = 15
while countdown > 0:
    if countdown > 10:
        pass # Don't do anything yet
    else:
        print('T - ', str(countdown))
    countdown -= 1
else:
    print ('We have liftoff!')

This code simulates a countdown, but we don’t actually want to print anything to the console until we get to 10. In this case, we set up an if condition that checks if countdown is greater than 10. If countdown is greater than 10, we use pass to do nothing.

In the real world, I tend to use pass when I am developing. Here is an example

def onNew():
    #TODO: Handle new file here
    pass

def onSave():
    #TODO: Handle saving a file here
    pass

def onOpen():
    #TODO: Handle opening a file here
    pass

def onError():
    #TODO: Handle user input errors here
    pass

repeat = True
while repeat:
    print('1) New...')
    print('2) Open...')
    print('3) Save...')
    print('4) Quit...')

    choice = input('Enter an option => ')
    if choice == 1:
        onNew()
    elif choice == 2:
        onOpen()
    elif choice == 3:
        onSave()
    elif choice == 4:
        repeat = False
    else:
        onError()

In this programming example, I’m in the process of developing a menu drive user interface. You can see the menu printed out in the while loop. The user is asked for a choice and then if/elif statements are used to respond to their choice. In each choice except 4, we are using function to handle the user’s choice. This keeps the user reponse code seperate from the user menu code (concept know as seperations of concerns).

Above the menu loop there are four functions: onNew(), onOpen(), onSave(), and onError(). Every single one of these functions has the pass keyword. Eventually the pass statements will get replaced with actual code to handle each event, but for now, I only want to test the menu code. Using pass in this fashion lets me run the program and make sure the menu is working properly before I continue developing the rest of the program.

Break Statement—Python

I’ve done a few posts now on loops. To review, Python has two kinds of loops: while loops and for loops.

I can think of plenty of times that we want to create an infinate loop. To review, an infintate loop is a loop that never ends. Consider this code.

while True:
    pass

Should you run this code, the program will never terminate because the loop condition is always True. In many cases, infinate loops are the result of programming errors, but let’s consider a menu driven program like this:

while True:
    print('1) New File')
    print('2) Open File')
    print('3) Save File')
    print('4) Exit...')

    choice = input('Enter choice => ')
    if choice == 1:
        pass # do something with a new file
    elif choice == 2:
        pass # do something to open a file
    elif choice == 3:
        pass # do something to save a file
    elif choice == 4:
        break # exit this loop and end the application

In this case, we want the program to program to continue to repeat this main menu until the user enters 4. That’s where the magic break keyword comes into play.

The break keyword liternally means to break out of a loop. This example is a common application of the loop but it doesn’t always have to be used in infinate loops. Let’s try and example with the for loop.

names = ['Bob Belcher',
         'Linda Belcher',
         'Louise Belcher',
         'Tina Belcher',
         'Gene Belcher']

bob = ''
for name in names:
    if 'Bob' in name:
        bob = name
        break   # There's no need to keep looping through
                # the rest of the list because we have found Bob

Nested Loops

In previous posts, we covered while and for loops. Python let’s us nest loops. Let’s start with an example.

grid = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [9, 8, 7, 6, 5, 4, 3, 2, 1],
]

for row in grid:
    for cell in row:
        print(str(cell))
    print('\n', end=' ')

When run, we get the following output

1 2 3 4 5 6 7 8 9

9 8 7 6 5 4 3 2 1

So why does this work? In our example, we have data structure that can be thought of in terms of an x,y grid. Basically, it’s a list that contains two lists: one list for each row.

When we begin our loop with for row in grid: we are starting a for loop with a variable named row. Everytime this loop updates, the row variable is assigned the next list object inside of the grid variable.

Now our next line of code is also a for loop: for cell in row. Remeber that row is a list object that corresponds to a row in the grid list. Each item inside of row is a number, so when this loop runs, the variable cell gets updated with a number inside of the list that is currently assigned to the row variable.

We can mix our loops also

grid = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9],
    [9, 8, 7, 6, 5, 4, 3, 2, 1],
]

for row in grid:
    index = 0
    while index < len(row):
        print(str(row[index]))
        index += 1

This code delivers the same output as the first example. The differnce is that this time, we have a while loop as our nested loop rather than a for loop. As you can see, this code is a little more complex than the first example, but the point of it was to demonstrate that it's possible to mix and match loops.

Also keep in mind that you can have loops that are infintely nested as long as your hardware can handle it. However, if you find that you are nesting loops deeper than two loops, then consider restructing your code since nesting loops that deep will impact the code's reability and make it difficult to debug.