How to write Algorithm in Python

Algorithms are the single most important toolbox for anyone who must solve problems by writing computer programs. Design and analysis of algorithms are a fundamental topic in computer science and engineering education.

Python represents an algorithm-oriented language. The advantages of Python include its textbook-like syntax and interactivity that encourages experimentation.

First, its indentation-based syntax is so similar to most textbooks that even students without much programming background have no trouble coding up algorithms just by following the book.

Second, Python provides the fundamental data structures such as lists, tuples, and dictionaries that can be used directly by the algorithms. Even the more complex data structures such as trees and graphs can also be expressed in Python in a concise, human-readable form, without having to reinvent those data structures.

There are several advantages: the test cases for the algorithms can be written directly in Python without having to call any data-structure-building API, and without having to rely on any custom parser. Moreover, it is infinitely extensible to arbitrary data types, as Python simply passes them along and does not interpret the data type until needed. At any time, the data structure can also be displayed in textual form that is readable to humans and by Python.

Example: Sorting

Most textbooks start with sorting as a way to introduce algorithms and complexity analysis. We use sorting algorithms to also introduce Python from the very first lesson. Our strategy is to display the algorithm side-by-side with Python code to show their similarity. We start with InsertionSort, which grows the sorted array one element at a time from the beginning of the array. Initially, A[1] (in text; A[0] in Python) is the only element in this subarray and is trivially sorted. Each iteration of the for-loop inserts the next new element into the sorted subarray so that the elements are sorted relative to each other; this is in contrast to BubbleSort, which puts a new element in its absolute sorted position per iteration.

Algorithm from textbook

Insertion-Sort(A)
1 for j <- 2 to length[A]
2      do key <- A[j]
3            i <- j – 1
4            while i > 0 and A[i] > key
5                   do A[i+1] <- A[i]
6                         i <- i – 1
7             A[i + 1] <- key

Python code

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key