Readable Syntax - Quicksort in Python

Quicksort Pseudocode from Wikipedia

function quicksort(array) var list less, greater if length(array) ≤ 1 return array select and remove a pivot value pivot from array for each x in array if x ≤ pivot then append x to less else append x to greater return concatenate(quicksort(less), pivot, quicksort(greater))

Here the Python implementation



In [ ]:

    
import random

# A python implementation of the Wikipedia quicksort algorithm
def my_quicksort(array):
    if len(array) < 1:
        return array
    
    pivot = array[0] # select a pivot (first element of list)
    rest = array[1:] # the array with the pivot
                     # removed
    less = [x for x in rest if x <= pivot]
    greater = [x for x in rest if x > pivot]
    
    return my_quicksort(less) + [pivot] + my_quicksort(greater)

testarr = [random.randint(-1000, 1000) for i in range(30)]
print(testarr)
print(my_quicksort(testarr))

Interactive and Batch possibilities - Munich temperatures



In [ ]:

    
# playing around with the data interactively

%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

data = np.loadtxt("data/munich_temperatures.txt")
day = data[:,0]
temp = data[:,1]



In [ ]:

    
%load code/temperature.py

Python is not slow - use vector operations

The C/Fortran paradigm to manipulate arrays by visiting each element is wrong in Python nearly always!



In [ ]:

    
import numpy as np

x = np.linspace(0.0, 2.0 * np.pi, 100)
print(x)



In [ ]:

    
%%timeit
import numpy as np

# C-like element-wise array manipulation
x = np.linspace(0.0, 2.0 * np.pi, 100)
y = np.zeros(len(x))

for i in range(len(x)):
    y[i] = np.sin(x[i])

Manipulating arrays by vector operations is typically a factor of 10 faster than the visit each element strategy!



In [ ]:

    
%%timeit
import numpy as np

# fast vector operations
x = np.linspace(0.0, 2.0 * np.pi, 100)
y = np.sin(x)



In [ ]: