Analysis of bubblesort and binary search

Bubblesort

When we’re learning about algorithms, it’s very common to use sorting a list as a problem to investigate. The reasons are, (a) the purpose of sorting is easy and doesn’t require any overhead, (b) we sort things all the time, and (c) there is a large variety of sorting algorithms - whatever you’re wanting to talk about in your algorithms class, there’s a sorting algorithm that uses it.

When people try to solve sorting on their own, they usually write something like bubblesort. Bubblesort looks like this:

def bubblesort(L):
  for i in range(len(L)):
    for j in range(1,len(L)):
      if L[j-1]>L[j]:
        t=L[j-1]
        L[j-1]=L[j]
        L[j]=t          

When analyzing an algorithm, first run it yourself - maybe make a list of size 8, and run the algorithm by hand to understand it. Is there a clear best case? Worst case?

How long (using big O) does it take? This is probably not that difficult for you now. It should be clear it is \(O(n^2)\).

We will do better than bubblesort for searching.

Searching for an item in a sorted list

Suppose we have a list which is sorted from smallest item to largest item. We’d like to know if a particular item appears in that list. We want a function that takes in the list and an item, and returns True if that item appears in the list, and False otherwise.

The easiest way to program this is linearly:

def search(L, item):
  for elem in L:
    if elem == item:
      return True
  return False

Clean, easy, and \(O(n)\). This same algorithm works if the list is not sorted. On one hand, that’s flexible, and flexibility is good, but ont he other, maybe we’re not leveraging our advantages.

If you have a big sorted list of names (like a phonebook), and you’re looking for a particular person, you don’t start with Aaron Aardvark, and then move on to his sister Berth Aardvark. You open the phonebook to the middle, and then decide if you need to be in the first half or the second half of your book. Then you do the same with that half. Then with that half, so you’re halving the number of names you’re considering each time. In code, that looks like this:

def search(L, item):
  if len(L)==0:
    return False
  low = 0
  high = len(L)
  while high-low > 1:
    mid = int( (high+low)/2 )
    if L[mid]>item:
      high=mid
    else:
      low=mid
  return L[low]==item

What’s the runtime of this? \(O(\log(n))\). MUCH better.