In this notebook, we will review the basic features of Python 2. We will not review basic programming skills, instead assuming that you are familiar with one or more programming languages. Instead, we will go over the keywords, and key language constructs which should transform you into a Pythonista in no time!
In [1]:
print 'Hello World!'
See, that was easy---the "Hello World" program in Python is simply just a single line using the built-in print. You will often see actual Python scripts have at least one extra line (on UNIX-like systems such as Linux and OS X). This line tells the host OS how to execute the content of the file:
In [2]:
#!/usr/bin/env python
print 'Hello World!'
Let's try something more complex. Python syntax approaches commonly accepted syntax for pseudo-code, so you can often easily translate algorithm descriptions from academic papers or textbooks directly into Python programs.
Checkout Wikipedia's pseudo-code description of Quicksort.
In [3]:
def quicksort(A, lo, hi):
if lo < hi:
p = partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
See, that was almost exactly the same as the pseudo-code. We've only added in the keyword def to define a function value, and the assignment operator := becomes simply = in Python.
In [4]:
def partition(A, lo, hi):
pivotIndex = lo
pivotValue = A[pivotIndex]
A[pivotIndex],A[hi] = A[hi],A[pivotIndex]
storeIndex = lo
for i in xrange(lo, hi):
if A[i] < pivotValue:
A[i],A[storeIndex] = A[storeIndex],A[i]
storeIndex = storeIndex + 1
A[storeIndex],A[hi] = A[hi],A[storeIndex]
return storeIndex
Okay, that was super easy. Now, how do we test our Quicksort implementation? Let's generate a bunch of random numbers and run our quicksort on them! We'll describe the magic xrange in a little bit. Don't worry!
In [5]:
from random import randint
In [6]:
A = [randint(0,100) for i in xrange(100)]
Wow! That's some crazy syntax. That line creates a list of 100 integers, with random values between 0 and 100 (including the endpoints, so the domain is $[0,100]$ in this case). How does it do it? This is a Python construct called a List Comprehension. There are two primary methods for iterating with a counter in a for loop: range and xrange. I tend to use xrange because range creates an entire list first which can use all of memory rather quickly, whereas xrange increments and evaluates lazily.
In [7]:
B = sorted(A)
Here we have sorted the array A using the Python built-in sorted which returns a new sorted list (using double the memory). This will be useful, as the newly created array B is properly sorted and we use it to check our Quicksort implementation.
In [8]:
print A
In [9]:
print B
As expected, array A remains unsorted, while array B is in sorted order.
In [10]:
quicksort(A, 0, len(A) - 1)
Okay, so this is how you call our simple function quicksort. The only interesting new bit is the Python len function which returns the length of a container (generally lists).
In [11]:
assert A == B