# 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:

``` python
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.

<iframe width="560" height="315" src="https://www.youtube.com/embed/k4RRi_ntQc8?si=CMMTkvEeWa94VS53" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

## 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:

```python
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:

```python
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.