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:
- The relevant Wikipedia page is very good
- Knuth’s The Art of Computer Programming Volume 3: Sorting and Searching .
  
  It would be nearly impossible to overstate the importance of Donald Knuth’s contributions to Computer Science.

Let’s see some sorting in action!¶

http://www.sorting-algorithms.com/

Table Of Contents

Previous topic

Next topic

This Page

CS 2120: Class #12b¶

Sorting¶

Insertion sort¶

Selection Sort¶

Bubble Sort¶

Bogosort¶

WTF!?¶

Why are we doing this again?¶

The horrible truth¶

Let’s see some sorting in action!¶