# CS 2120: Class #12b¶

Warning

We are into the domain of nontrivial algorithms. You should not expect to look at these algorithms and immediately understand how they work. (In fact, if you can do that, you should immediately enroll in grad school in Computer Science). These algorithms require careful study to make sense of. The best tool you have for understanding how they work is to carefully trace their operation, step by step. Trying to understand complex algorithms “all in one go” is a recipe for frustration. Take your time, and step through the algorithm (with pen and paper) on a small input to get a feel for what it’s doing.

## Sorting¶

• Believe it or not, there are a lot of ways to sort a list!
• Some algorithms are just plain bad.
• Some are usually pretty good.
• There is no best algorithm for any list. Just tradeoffs.
• We’re going to look at a few simple sorting algorithms now.
• At the end of the class, we’re going to learn about recursion, which will allow us to revist sorting and see some really cool (and efficient) algorithms.

## Insertion sort¶

• You give me a list called `inlist`

• I create a new, empty, list called `sortedlist`

• For each element in `inlist`
• I insert that element into `sortedlist` in the correct spot.
• e.g., if I’m asked to insert `5` into the list `[1,3,7]`, I should end up with: `[1,3,5,7]`

Activity

Do an insertion sort, with pencil and paper, on the list `[3,7,15,9,4,11,1,5,2]`. Record the value of `sortedlist` at each step.

• If our lists were huge and we didn’t want to waste space, we could make a small change and remove each element from `inlist` before we insert it into `sortedlist`.

Let’s have a look at insertion sort in Python:

```def insertion_sort(inlist):
sorted_list = []
for element in inlist:
i = 0
while i < len(sorted_list) and (element > sorted_list[i]):
i = i + 1
sorted_list.insert(i,element)
return sorted_list
```

Activity

Modify the `insertion_sort()` function above so that it prints out the value of `sorted_list` after each iteration of the for loop. Try sorting a few lists and following the output. Does it make sense to you?

• Now that we’ve got the idea down, let’s be computer science nerds about it.

Activity

How many times do I go around the for loop in `insertion_sort()` ? On each trip through the for loop, I also have to go through the inner while loop.

• How many times do I go through the while loop, on average?
• In the worst case?

Is Insertion sort the best possible sort? Can we do better?

## Selection Sort¶

• You give me a list called `inlist`
• I scan through the whole list to find the smallest element
• I swap the smallest element with the first element in the list
• I repeat the above process for the remainder of the list (excluding the first element)
• Lather, rinse, repeat.

Activity

Do a selection sort, with pencil and paper, on the list `[3,7,15,9,4,11,1,5,2]`. Record the value of your list at each step.

• Different idea than Insertion sort, but still gets the job done!

• This is a very important thing to understand:
• Sorting is a problem, not an algorithm
• There are (infinitely) many algorithms to solve any (solvable) problem
• Some algorithms will always solve the problem more efficiently than others
• Some will solve the problem more efficiently only for certain conditions
• For some problems we can prove that a particular algorithm is the best (in the sense that any other algorithm can, at best, be equally efficient)
• For many problems, we still don’t know how to do this!
• Fortunately, for sorting we do know how to do this analysis... and both Insertion Sort and Selection sort kinda suck.

Let’s see Selection sort in action:

```def selection_sort(inlist):
for i in range(len(inlist)):

# Find the smallest remaining element
min_index = i
min_val = inlist[i]
for j in range(i+1,len(inlist)):
if inlist[j] < min_val:
min_val = inlist[j]
min_index = j

# Swap it to the left side of the list
inlist[min_index] = inlist[i]
inlist[i] = min_val

return inlist
```

Activity

Modify the `selection_sort()` function above so that it prints out the value of `inlist` after each iteration of the outer for loop. Try sorting a few lists and following the output.

Activity

How many times do I go around the outer for loop in `selection_sort()` ? How about the inner for loop?

## Bubble Sort¶

• Maybe you find Insertion sort or Selection sort ugly or offensive?
• No problem. Remember: there are many algorithms to solve any one problem.
• You give me a list called `inlist`
• I scan through the list, looking at adjacent pairs of values.
• If I see a pair that is “out of order” (e.g., `[17, 9]` ), I swap the two values to be in order ( `[9,17]` ).
• I keep doing that until the list is sorted.

Activity

Do a bubble sort, with pencil and paper, on the list `[3,7,15,9,4,11,1,5,2]`. Record the value of your list at each step.

• It’s called “bubble sort” because the smaller values seem to “bubble up to the top”.

• Kinda cool because:
• We end up effecting a global change on the list (it goes from unsorted to sorted)...
• ... but we only use local information about the elements (we only ever compare neighbours in the list)

Let’s see Bubble sort in Python:

```def bubble_sort(inlist):
swapped_something = True
while swapped_something:
swapped_something = False

for i in range(len(inlist)-1):
if inlist[i] > inlist[i+1]:
tmp = inlist[i]
inlist[i]=inlist[i+1]
inlist[i+1]=tmp
swapped_something = True
return inlist
```
• Ugh... Wouldn’t the above code be better if there were comments?

Activity

Modify the `bubble_sort()` function above so that it prints out the value of `inlist` after each iteration of the outer while loop. Try sorting a few lists and following the output.

Activity

How many times do I go around the outer while loop ? How about the inner for loop?

Activity

When I swapped elements, I used a third, temporary, variable called `tmp`. Could I have done the swap without `tmp`? Was using `tmp` wasteful?

## Bogosort¶

Here’s another attempt at a sorting algorithm:

```import random

def is_sorted(inlist):
last = inlist[0]
for element in inlist[1:]:
if last > element:
return False
last = element
return True

def bogosort(inlist):
while not is_sorted(inlist):
random.shuffle(inlist)

return inlist
```

Activity

How does this sorting algorithm work? We’re “working backwards” this time. Starting from the code, come up with an English explanation for how the algorithm works. You might want to add a `print` statement after the `random.shuffle(inlist)` line to get some intuition. If you aren’t sure what `random.shuffle()` does... look it up, or just try it on some sample lists. Likewise, you’ll have to figure out what `is_sorted()` is doing (though the name should help).

Activity

Is this a good sorting algorithm? How many times do I have to go through the `while` loop in `bogosort`? How about the `for` loop in `is_sorted()`?

## WTF!?¶

• With respect to SEARCHING, why would someone want to sort a list in order to search it slightly faster when sorting is so slow?

• Well, we might want to search the same list many times.
• We only need to sort it once.
• We might want to sort something without the end goal of searching.

• BUT, actually there are better sorting algorithms...

## Why are we doing this again?¶

• In your day-to-day life as a research programmer, you won’t write your own sorting routines. You’ll rely on routines written by others, like Python’s built-in `sort()` (which, by the way, uses the Timsort algorithm )
• BUT... even if you don’t build the tools yourself, you should understand how they work
• More importantly: you may need to develop your own algorithms for some task that is much less well-studied than sorting.
• You’re learning fundamentals of algorithm development here... not just the details of sorting.

## The horrible truth¶

• All three of Insertion, Selection, and Bubble sort generally suck as sorting algorithms.

• BUT... they are within our current means.

• Once we’ve studied recursion, we will revist sorting and see two very good sorting algorithms (Quicksort and Mergesort).

• If you want to geek out on sorting right now: