Lecture 09: Searching and sorting

Now we're getting more into the 'numerical methods' part of the course!

Today, we will delve into the following:

  • how to write pseudo code
  • computational complexity (big-O notion).
  • search algorithms (sequential, binary)
  • sort algorithms (bubble, insertion, quick)

Search and sort algos are at the heart of computer science.
Understanding these is the first thing you get into at DIKU or DTU, so we are also going to get a taste of them.

Links to further material:
If you feel inspired by the material here, you can try your hand at solving algorithmic challenges at Project Euler.
(there are both easy and harder exercises to choose from)

[ ]
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-whitegrid')
import time
import string
import random
import sys
from IPython.display import Image

1. Algorithms - what are they even?

Technically: An unambigious specification of how to solve a class of problems.

In a nut shell: An algo is a recipe.
Even a simple cooking recipe is an algorithm..

1. Preheat the oven
2. Mix flour, sugar and eggs
3. Pour into a baking pan
etc.

Properties of an algorithm:

  1. Unambigious termination criteria
  2. Pre-defined inputs
  3. Pre-defined ouputs
  4. Guaranteed finite runtime
  5. Correct result

1.1 Simple example: max{}\max\{ \ell\}

Problem: Given a list of positive numbers, return the largest number in the list.

Inputs: A list L of positive numbers.

Outputs: A number.

Algorithm: find_max()

  1. Set maxL to 0.
  2. For each x in the list L, compare it to maxL. If x is larger, set maxL to x.
  3. maxL is now set to the largest number in the list.

Note: The above is called pseudo-code (understandable across programming languages).

Implementation in Python:

[ ]
def find_max(L):
    maxL = 0
    for x in L:
        if x > maxL:
            maxL = x
    return maxL

Question: An error might occur if L is not restricted to contain strictly positive numbers. What could happen?

Bonus info: Python, and other modern languages, actually tries to predict the result of an if statement before it is reached and prepares the following set of instructions. This is called branch prediction and is a major source of computational improvement. If you have a lot of if-statements that are not predictable, eg. because of randomized data, it may be a drag on computation time.

1.2 Algorithmic complexity

Algorithms can be characterized by the number of operations needed to perform them. This is called their complexity.

The find_max() algorithm has n = len(L) operations each making a comparison (x > max) and (perhaps) an assignment (max = x).

The number of operations increase linearily in the length of the input list (the order of the function is linear).

Mathematically we say that find_max() has linear complexity, \(O(n)\) where nn is the input size (length of L).

Other common levels of complexity are:

  1. Constant, O(1)O(1) (i.e. independent of input size)
  2. Logarithmic, O(logn)O(\log n)
  3. Linear, O(n)O(n)
  4. Log-linear, O(nlogn)O(n \log n)
  5. Quadratic, O(n2)O(n^2)
  6. Cubic, O(n3)O(n^3)
  7. Exponential, O(2n)O(2^n) (curse of dimensionality)

If the performance of an algorithm depends on the exact values of the input we differentiate between

  1. Best case
  2. Average case (across all possible inputs)
  3. Worst case

Complexity is an asymptotic measure,

  1. Only the number of operations matter (not their type or cost)
  2. Only the highest order matter
bigO

In practice however:

  • The cost of each operation matters for fixed input size.
  • The amount and flow of memory matter for speed (cache vs. RAM vs. disc).
  • Therefore, it is not guaranteed that an algorithm of lower complexity executes faster than that of higher complexity for all cases.
    Especially, there may be differences in the costs of memory allocation and deletion which are not counted into the measure of complexity. In the case above, we were not counting in the deletion of objects, that would necessarily follow.

1.3 Example of a complexity calculation

[ ]
def demo_algorithm(n):
    
    # a. 3 assignments
    a = 5
    b = 6
    c = 10
    
    # b. 3*n^2 multiplications and 3*n^2 assignments
    for i in range(n):
        for j in range(n):
            x = i * i
            y = j * j
            z = i * j
            
    # c. n multiplications, additions, and assignments
    #    + n multiplications and assignments
    for k in range(n):
        w = a*k + 45
        v = b*b
        
    # d. 1 assignment
    d = 33

The total number of operations are: T(n)=3+6n2+5n+1=6n2+5n+4T(n) = 3 + 6n^2 + 5n + 1 = 6n^2 + 5n + 4

Notice: this is an exposition of operations. There are of course also operations involved in multiplication itself, which means that the number above is not indicative of the total number of operations that the computer must handle.

In big-O notation: demo_algorithm() is O(n2)O(n^2), i.e. quadratic complexity

Question\large \color{purple}{Question}: What is the complexity of these two algoritms?

[ ]
def algorithm_a(n):
    s = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                s += 1

def algorithm_b(n):
    s = 0
    for i in range(n):
        s *= 2
    for j in range(n):
        s *= 2
    for k in range(n):
        s *= 2

1.4 The complexity of operations on data containers

1.4# How are lists and dictionaries structured?

The fact that our data containers have a certain structure in memory matters greatly for the speed of the methods (read: algos) that we apply on them.

Let's have a look at how lists and dictionaries are organized.

Lists:

  • A list is an ordered set of references to objects (eg. floats).
  • Each reference points to an address in memory where values are stored.
  • The reference variables of addresses (called pointers) of data in a list are ligned up next to each other in memory, such that they are increments of 1 apart. A bit like a train, if you will.
  • Need therefore only to keep track of the reference to the address of the first element, l[0], and the rest follows in line.
  • If by aa we denote the address of the first element of l, then looking up element l[i] means accessing the a+ia+i address in memory using its reference variable.
  • Therefore, the algorithmic complexity of looking up an element l[i] does not depend on the size of l. Which is nice.
[ ]
# A demonstration of addresses of elements in a list
x = [5, 21, 30, 35]
x_ref = [] 
x_id = []

# The addresses of x's elements
for i in x:
    x_id.append(id(i)) # Each object has its own unique id
    x_ref.append(hex(x_id[-1])) # The memory address is a hexadecimal of the id

# The addresses printed below are NOT lined up next to each other in memory. 
# Only the reference variables are lined up, but those we cannot see directly in Python.
print('Id of each element in x:')
for i in x_id:
    print(i)
print('\nMemory address of elements in x: ', x_ref)

A quick overview of list operations

OperationCodeComplexity
Index:l[i]O(1)O(1)
Store:l[i] = 0O(1)O(1)
Length:len(l)O(1)O(1)
Append:l.append(n)O(1)O(1)
Slice:l[a:b]O(ba)O(b-a)
Pop last:l.pop()O(1)O(1)
Pop i:l.pop(i)O(N)O(N)
Clear:l.clear()O(N)O(N)
check:l1 == l2O(N)O(N)
Insert:l[a:b] = ...O(N)O(N)
Delete:del l[i]O(N)O(N)
Containment:x in/not in lO(N)O(N)
Copy:l.copy()O(N)O(N)
Sort:l.sort()O(NO(NLogN)N)

A few notes:

  • Getting the length of a list is O(1)O(1) because Python keeps track of a list's size as it created and expanded. The length is stored as an attribute to the list.
  • Popping (getting the last element) is O(1)O(1) because it only requires detaching the last reference in the "train" of references that comprises a list.
  • Inserting an element into, or removing it from, the middle of a list requires moving around all the references in memory "behind" the inserted element and is therefore O(N)O(N).
  • Checking for containment of an element is O(N)O(N) because all elements in the list may have to be visited.

A beautiful solution

Question: how do you delete element i from list l in O(1)O(1)? (even when it says above that del is an O(N)O(N) operation)

Answer:

l[i] = l.pop()

The pop operation will delete the last element of l while also using it to overwrite element i in l. Hence, last element is preserved while element i disappears.

Note this won't work if i is the last element. A full implementation needs to account for this, but it will still be O(1)O(1).

Dictionaries:

  • A dictionary is a set of buckets (think lists) which can store items.
  • A dictionary with 1 element and 5 buckets: [] - [] - [] - [<key,value>] - []
  • Contrary to lists, there is no explicit indexing of a dictionary. No d[i], we can use a string instead, d[str].
  • However, the buckets of a dictionary are lined up just like a the references in a list.
  • Python therefore needs to locate a bucket, when adding a <key,value> pair.
  • Buckets are located using a hash function on the key of an element.
  • This hash function converts the key to a integer number, which can then serve as an index.
  • Obviously, a useful hash function must be very fast and work on strings as well as floats.
  • A fast hash function enables O(1)O(1) lookup in a dictionary.
  • Hashing also implies that key in dict.keys() is O(1)O(1), thus independent of dictionary size! (Very handy)
  • When an empty dictionary is created, it contains 5 buckets. As a 6th element is added to the dictionary, it is rescaled to 10 buckets. At 11 elements, rescaled to 20 buckets and so on.
  • Dictionaries thus pre-allocate memory to be efficient when adding the next element.
  • Taking up memory in favor of fast execution is a basic trade-off in algorithms!
[ ]
d = {'x': 1, 'z': 2}
print('size of md in bytes:', sys.getsizeof(d))

# Start adding elements to d and see how memory usage changes
for i in range(25):
    key = random.choice(string.ascii_letters)
    value = random.random()
    d[key] = value
    print(f"key: {key}  value: {value: 1.3f} \t  size: {i+1:2.0f}   bytes: {sys.getsizeof(d)} \t hashed key: {hash(key)}")
    
# Notice that there may be collisions as some keys are similar, and therefore get same hash value. 
# Python can handle such collisions, but they do create a drag on performance. 

A quick overview of dictionary operations

OperationCodeComplexity
Index:d[k]O(1)O(1)
Store:d[k] = vO(1)O(1)
Delete:del d[k]O(1)O(1)
Length:len(d)O(1)O(1)
Clear:d.clear()O(1)O(1)
View:d.keys()O(1)O(1)

Notice the difference in complexity for deletions. Faster in dictionaries because they are unordered.

You can checkout a comprehensive table of Python operations' complexity.

1.5 Multiplication and Karatsuba's algorithm

Ever wondered how Python multiplies two numbers? It actually depends on the size of those numbers!

Small numbers: 3rd grade algorithm. Large numbers: Karatsuba's algorithm.

1.5# Demonstration

Consider the multiplication 2275×5013=11,404,5752275 \times 5013 = 11,404,575

3rd grade algorithm
(this one we all know - although it's been a while)
The 3rd grade algorithm is O(n2)O(n^2). To see this, think of the multiplication part as nested for-loops throughout the 10s, 100s, 1000s etc. Then there is the addition part, which is also O(n2)O(n^2).

[ ]
Image(filename = "ThirdGradeMultiplication.jpg", width = 230, height = 230)

Karatsuba's algorithm

It is not super intuitive what goes on here. But basically, it's splitting the numbers to be multiplied into multiples of 10s and then performs operations on those splits.

The algorithm is only O(nlog3)O(n^{log_3}), so better than 3rd grade algorithm for large nn.

Some preparation:

x=2275x = 2275, y=5013y = 5013

Note the identities:
x=22×102+75x = 22 \times 10^2 + 75
y=50×102+13y = 50 \times 10^2 + 13

We denote:
xa=22,xb=75x_a = 22, \: x_b = 75
ya=50,yb=13y_a = 50, \: y_b = 13

The algorithm

First compute:

A=xa×yaA = x_a \times y_a
B=xb×ybB = x_b \times y_b
C=(xa+xb)×(ya+yb)ABC = (x_a + x_b) \times (y_a +y_b) - A - B

Then we have that

x×y=A×104+C×102+Bx \times y = A \times 10^4 + C\times 10^2 + B

In numbers

A=22×50=1100A = 22 \times 50 = 1100
B=75×13=975B = 75 \times 13 = 975
C=(22+75)(50+13)1100975=4036C = (22 + 75)(50 + 13) - 1100 - 975 = 4036

x×y=1100×104+4036×102+975=11,404,575x \times y = 1100 \times 10^4 + 4036\times 10^2 + 975 = 11,404,575

1.6 Linear search (also called sequential search)

Problem: Check whether element is in list. See the containment row in the list of complexity above.

Inputs: A list L and a potential element x.

Outputs: Boolean.

Algorithm: linear_search()

  1. Set variable found == False
  2. For each y in the list L, compare it to x. If x == y set found = True and break loop.
  3. found now shows whether the element is in the list or not
[ ]
L = [1, 2, 32, 8, 17, 19, 42, 13, 0] # test list

def linear_search(L,x):
    pass
    
print('found  3:',linear_search(L,3))
print('found 13:',linear_search(L,13))
[ ]
def linear_search(L,x):
    """ linear search
    
    Args:
    
        L (list): List to search in.
        x (any): Element to search for.
        
    Returns:
    
        found (bool): Boolean for whether element is in list or not.
    
    """
    
    # a. prep
    i = 0
    N = len(L)
    found = False

    # b. main
    while i < N and not found:
        if L[i] == x: # comparison
            found = True
        else:
            i += 1 # increment

    # c. return
    return found
[ ]
print('found  3:',linear_search(L,3))
print('found 13:',linear_search(L,13))

Terminology: The linear search algorithm is called a brute force algorithm (we solve the problem without any intermediate steps).

Analysis: Each operation consists of a comparision and an incremenet:

  1. Best case: O(1)O(1) (element present and first in list)
  2. Average case:
  • O(n2)=O(n)O(\frac{n}{2})=O(n) (if element present), or
  • O(n)O(n) (if element not present)
  1. Worst case: O(n)O(n) (element not present or last in list)

Note: Much faster (O(1)O(1)) on a dictionary, because we just apply the hash function to x.

1.7 Binary search ("the phonebook search")

Problem: You know that a list is sorted. Check whether an element is contained in it.

Inputs: A list L and a potential element x.

Outputs: Boolean.

Algorithm: binary_search()

  1. Set found to False,
  2. Locate the midpoint of the list part that remains to be searched.
  3. Check whether the midpoint is the one we are searching for:
    • If yes, set found=True and go to step 3.
    • If no, and the midpoint is larger, restrict attention to the left part of the list and restart step 2 if not empty.
    • If no, and the midpoint is smaller, restrict attention to the right part of the list and restart step 2 if not empty.
  4. found now shows whether the element is in the list or not

Middle element: Define the midpoint between index i and index j >= i as i + (j-i)/2, rounded down if necessary.

[ ]
for i in [0,2,4]:
    for j in [4,5,9]:
        print(f'(i,j) = {i,j} -> midpoint = {i+((j-i)//2)}') # note integer division with //
[ ]
L = [0, 1, 2, 8, 13, 17, 19, 32, 42] # test list

def binary_search(L,x):    
    pass

print('found  3:',binary_search(L,3))
print('found 13:',binary_search(L,13))
[ ]
def binary_search(L,x,do_print=False):
    """ binary search
    
    Args:
    
        L (list): List to search in.
        x (any): Element to search for.
        do_print (bool): Indicator for printing progress.
        
    Returns:
    
        found (bool): Boolean for whether element is in list or not.
    
    """
    
    # a. initialize
    found = False
    
    # b. start with whole list
    first = 0
    last = len(L)-1
    
    # c. main
    while first <= last and not found:

        # i. find midpoint
        midpoint = first + (last - first) // 2 # // is integer division
    
        if do_print:
            print(L[first:last+1],L[midpoint])
            
        # ii. check if x found or smaller or larger than midpoint
        if L[midpoint] == x:
            found = True
        else:
            if L[midpoint] > x:
                last = midpoint-1
            else:
                first = midpoint+1
    
    return found
[ ]
print('found  3:',binary_search(L,3))
print('found 13:',binary_search(L,13))
[ ]
binary_search(L,32,do_print=True)

Terminology: This is called a divide-and-conquer algorithm.

Analysis:

  • After 1 comparison there is approximately n2\frac{n}{2} elements left.
  • After 2 comparisons there is approximately n4\frac{n}{4} elements left.
  • After 3 comparisons there is approximately n8\frac{n}{8} elements left.
  • ...
  • After jj comparisons there is approximately n2j\frac{n}{2^j} number of elements left.

When is there one element left? n2j=1j=lognlog2\frac{n}{2^j} = 1 \Leftrightarrow j = \frac{\log n}{\log 2}

Result: The binary search algorithm is O(logn)O(\log n), i.e. logarithmic complexity.

2. Recursion

Problem: Sum the elements in a list.

[ ]
L = [1,3,5,7,9]

Simple: Just sum them:

[ ]
def listsum(L):
    result = 0
    for x in L:
        result += x
    return result

print(listsum(L))

Recursion: The sum of a list is the sum of the first element and the sum of the rest of the list:

[ ]
def listsum_recursive(L):
    if len(L) == 1:
        return L[0]
    else:
        return L[0] + listsum_recursive(L[1:])

print(listsum_recursive(L))

This is also a divide-and-conquor strategy. Avoids loops.

2.1 Fibonacci numbers

Definition:

F0=0F1=1Fn=Fn1+Fn2\begin{aligned} F_0 &= 0 \\ F_1 &= 1 \\ F_n &= F_{n-1} + F_{n-2} \\ \end{aligned}

Implementation:

[ ]
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci(n-1)+fibonacci(n-2)

fibonacci(5)
#for n in range(4):
#print(fibonacci(n))

Caution!

This implementation is for demonstration purposes only. It can be greatly sped up by using the @cache decorator, which stores the previous return value of a function call.

If you ever want to use recursion, you must rely on caching of function values. Because recursion on itself is sloow.

Test approximate formula:

[ ]
def fibonacci_approx(n):
    return 1/np.sqrt(5)*( ((1+np.sqrt(5))/2)**n - ((1-np.sqrt(5))/2)**n)

for n in [5,10,15,20,25]:
    print(f'n = {n:3d}: true = {fibonacci(n):6d}, approximate = {fibonacci_approx(n):20.12f}')

2.2 Advanced: Binary search with recursion

[ ]
L = [0, 1, 2, 8, 13, 17, 19, 32, 42,] # test list

def binary_search_recursive(L,x):
    pass

print('found  3:',binary_search_recursive(L,3))
print('found 13:',binary_search_recursive(L,13))
[ ]
def binary_search_recursive(L,x):
    """ recursive binary search
    
    Args:
    
        L (list): List to search in.
        x (any): Element to search for.
        
    Returns:
    
        found (bool): Boolean for whether element is in list or not.
    
    """
    
    if len(L) == 0: 
    
        return False # not found
    
    else:
        
        # a. find midpoint
        midpoint = len(L)//2
        
        # b. check if x found or smaller or larger than midpoint
        if L[midpoint] == x: # found
            return True
        else:            
            if L[midpoint] > x:
                newL = L[:midpoint]
            else:
                newL = L[midpoint+1:]
            return binary_search_recursive(newL,x)
[ ]
print('found  3:',binary_search_recursive(L,3))
print('found 13:',binary_search_recursive(L,13))

3. Sorting

Sorting is a super central task of computing. IBM invented it's first computers in the 30s to sort data.

Would be hard to keep track of data without sorting. Thus, many algorithms have been developed for this purpose.

We will look at a simple algorithm first, the bubble sort, which relies on swapping elements iteratively.

Function for swapping element L[i] with element L[j] in-place:

[ ]
def swap(L,i,j):
    temp = L[i] # save value in place holder variable
    L[i] = L[j] # overwrite value at i with value at j
    L[j] = temp # write original value at i to value at j

Example:

[ ]
L = [1, 3, 4, 9, 13] 
swap(L,i=0,j=1)
print('after swap',L)

3.1 Bubble sort

Problem: Sort a list of numbers in-place.

Inputs: List of numbers.

Outputs: None.

Algorithm: bubble_sort()

  1. Loop through the first n-1 elements in list, swap with next element if current is larger.
  2. Loop through the first n-2 elements in list, swap with next element if current is larger.
    ...
  3. Loop through the first 3 elements in list, swap with next element if current is larger.
  4. Swap the two first elements if the first is larger than the second
  5. List is sorted

[ ]
L = [54, 26, 93, 17, 77, 31, 44, 55, 20] # test list       

def bubble_sort(L):
    pass

bubble_sort(L)
print(L)
[ ]
def bubble_sort(L):
    """ bubble sort
    
    Args:
    
        L (list): List of numbers
        
    """
    
    # k starts being len(L)-1 and is decreased by 1 until hitting 0
    for k in range(len(L)-1,0,-1):
        for i in range(k):
            if L[i] > L[i+1]:
                swap(L,i,i+1)

L = [54, 26, 93, 17, 77, 31, 44, 55, 20]      
bubble_sort(L)
print('sorted L:',L)
[ ]
from IPython.display import YouTubeVideo
YouTubeVideo('lyZQPjUT5B4', width=800, height=600, start=45)

Another visualization of bubble sort
bubble

Illustration with printout:

[ ]
def bubble_sort_with_print(L):
    for k in range(len(L)-1,0,-1):
        print(f'step = {len(L)-k}')
        for i in range(k):
            if L[i] > L[i+1]:
                swap(L,i,i+1)
            print(L)                
        print('')
        
L = [54, 26, 93, 17, 77, 31, 44, 55, 20]        
print('original',L,'\n')
bubble_sort_with_print(L)

Analysis: Bubble sort is O(n2)O(n^2) - do you have an intuition?

3.2 Insertion sort

Algorithm: insertion_sort()

  1. Consider the second element. Insert it correctly in the list of the numbers before the second element.
  2. Consider the third element. Insert it correctly in the list of the numbers before the third element.
    ...
  3. Consider the n'th element. Insert it correctly in the list of the numbers before the n'th element.
  4. List is sorted

Illustration:

insertionsort
[ ]
L = [54, 26, 93, 17, 77, 31, 44, 55, 20] # test list

def insertion_sort(L):
    pass

insertion_sort(L)
print(L)
[ ]
def insertion_sort(L):
    """ insertion sort
    
    Args:
    
        L (list): List of numbers
        
    """
    
    # loop over last n-1 elements, skipping the 1st element (see range func).  
    n = len(L)
    for k in range(1,n): 
        
        # a. current value and position
        x = L[k]
        i = k
        
        # b. move left while larger: a bubble sort at heart
        while i > 0 and L[i-1] > x:         
            L[i] = L[i-1] # move
            i = i-1
        
        # c. insert current vlaue
        L[i] = x

L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertion_sort(L)
print('sorted',L)        

Analysis: Still O(n2)O(n^2)..

Benefits relative to bubble sort:

  1. Moves instead of swaps, 1 operation less.
  2. Data is often partially sorted to begin with. Insertion sort benefits from that.

3.3 Partition (+)

Intermezzo: Solving the partition problem is useful for a so-called quicksort.

Problem: Permute a list and return a splitpoint such that all elements before the point is larger than or equal to the first element in the original list, and all elements afterwards are strictly larger.

Input: List of numbers.

Output: Integer.

Algorithm:

  1. Let splitting point be first element of list.
  2. From the left find the first element larger than split point (leftmark).
  3. From the right find the first element smaller than split point (rightmark).
  4. Swap these two elements.
  5. Repeat 1-3 starting from previous leftmark and rightmark. Continue until leftmark is larger than rightmark.
  6. Swap first and rightmark element.
  7. Return the rightmark.
quicksort
[ ]
def partition(L,first,last):
    """ partition
    
    Permute a list and return a splitpoint, such that all elements before 
    is larger than or equal to the first element in the original list, 
    and all elements afterwards are strictly larger.
    
    Args:
    
        L (list): List of numbers
        first (integer): Startpoint
        last (integer): Endpoint
    
    Returns:
    
        splitpoint (integer): 
        
    """
    
    # a. initialize
    splitvalue = L[first]
    leftmark = first+1
    rightmark = last

    # b. find splitpoint
    done = False
    while not done:

        # i. find leftmark
        while leftmark <= rightmark and L[leftmark] <= splitvalue:
            leftmark = leftmark + 1
        
        # i. find rightmark
        while L[rightmark] >= splitvalue and rightmark >= leftmark:
            rightmark = rightmark -1

        # iii. check if done or swap left and right
        if rightmark < leftmark:
            done = True
        else:
            swap(L,leftmark,rightmark)

    # c. final swap
    swap(L,first,rightmark)

    return rightmark
[ ]
L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print('before',L)
splitpoint = partition(L,0,len(L)-1)
print('after',L)
print('split',L[:splitpoint+1],L[splitpoint+1:])

3.4 Quicksort (+)

Algorithm: quick_sort()

  1. Recursively partition the list and the sub-lists when splitting at the splitpoint.
  2. The list is now sorted.
[ ]
def quick_sort(L):
    _quick_sort(L,0,len(L)-1)

def _quick_sort(L,first,last):
   
    if first < last:

        splitpoint = partition(L,first,last)    
        _quick_sort(L,first,splitpoint-1) # left part
        _quick_sort(L,splitpoint+1,last) # right part
[ ]
L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quick_sort(L)
print('sorted',L)

Analysis: O(nlogn)O(n \log n) on average, but still O(n2)O(n^2) in the worst case we don't derive this, just trust me.

Visualization of quicksort
quicksort

3.5 Advanced: Comparision of performance

Lets us compare the different sorting algorithm:

  1. Bubble
  2. Insertion
  3. Quick
  4. Quick (as implemented in Numpy)
[ ]
# a. settings
n_vec = np.array([100,200,300,400,500,750,1000,1500,2000,4000,8000,16000]) # number of elements in list
K = 50 # number of repetitions when timing

# b. allocate vectors for results
bubble = np.empty(len(n_vec))
insertion = np.empty(len(n_vec))
quick = np.empty(len(n_vec))
quicknp = np.empty(len(n_vec))

# c. run time trials
np.random.seed(1999)
for i,n in enumerate(n_vec):
    
    # i. draw K random lists of lenght n
    L_bubble = []
    L_insertion = []
    L_quick = []
    L_quicknp = []
    for k in range(K):
        L = np.random.uniform(size=n)
        np.random.shuffle(L)
        L_bubble.append(L.copy())
        L_insertion.append(L.copy())
        L_quick.append(L.copy())
        L_quicknp.append(L.copy())
        
    # ii. bubble sort
    if n <= 500:
        t0 = time.time() # start timer
        for k in range(K):
            bubble_sort(L_bubble[k])
        bubble[i] = time.time()-t0 # calculate time since start
    else: 
        bubble[i] = np.nan
        
    # ii. insertion sort
    if n <= 500:
        t0 = time.time()
        for k in range(K):
            insertion_sort(L_insertion[k])
        insertion[i] = time.time()-t0
    else: 
        insertion[i] = np.nan
        
    # iii. quicksort
    if n <= 2000:
        t0 = time.time()
        for k in range(K):
            quick_sort(L_quick[k])
        quick[i] = time.time()-t0
    else: 
        quick[i] = np.nan
        
    # iii. quicksort (numpy implementation)    
    t0 = time.time()
    for k in range(K):
        L_quicknp[k].sort() # built-in numpy method
    quicknp[i] = time.time()-t0
    
    # iv. check that all sorted lists are the same
    for k in range(K):
        if n <= 500:
            assert np.all(L_bubble[k] == L_quick[k])
            assert np.all(L_insertion[k] == L_quick[k])
        if n <= 2000:
            assert np.all(L_quicknp[k] == L_quick[k])
    
# d. figure    
I = n_vec <= 2000
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.plot(n_vec[I],bubble[I],label='bubble')
ax.plot(n_vec[I],insertion[I],label='insertion')
ax.plot(n_vec[I],quick[I],label='quick')
ax.plot(n_vec[I],quicknp[I],label='quick (numpy)')
ax.set_xlabel('number of elements')
ax.set_ylabel('seconds')
ax.legend(facecolor='white',frameon=True);
[ ]
fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.plot(n_vec,quicknp,label='quick (numpy)')
ax.set_xlabel('number of elements')
ax.set_ylabel('seconds')
ax.legend(facecolor='white',frameon=True);

Take-aways:

  1. Complexity matters
  2. Implementation matter (and the built-in functions and methods are hard to beat)

4. Summary

This lecture:

  1. Algorithms and their complexity (big-O notation)
  2. Function recursion (functions calling themselves)
  3. Searching algorithms (linear, bineary)
  4. Sorting algorithm (bubble, insertion, quick)

Your work: The problem set is closely related to the algorithms presented here.

Next lecture: Solving equations (single vs. system, linear vs. non-linear, numerically vs. symbolically)