I implemented some common searching and sorting algorithms in Python to improve my understanding of them in preparation for an algorithms exam. They may not be perfect implementations (unoptimised etc.) but they may help a Python-minded individual understand how they work…

Note: The selection sort and bubble sort algorithms take one argument, a list, and modify it in place as it is a mutable type. The merge sort and quicksort algorithms sorted versions of the provided lists; they don’t modify the lists in place. The search algorithms take two arguments - a list (l), and an element to be found(k). The both return the index of the found element.

Selection Sort

def selection_sort(l):
    n = len(l)
    for i in xrange(n-1):
        mini = i
        for j in xrange(i+1, n):
            if l[j] < l[mini]:
                mini = j
        l[i], l[mini] = l[mini], l[i]

Bubble Sort

def bubble_sort(l):
    n = len(l)
    for i in xrange(n-1):
        for j in xrange(n-1-i):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]

Merge Sort

def merge_sort(l):
    n = len(l)
    if n > 1:
        mid = n/2
        l1 = merge_sort(l[:mid])
        l2 = merge_sort(l[mid:])
        return merge(l1, l2)
    return l
 
def merge(l1, l2):
    result = []
    p = len(l1)
    q = len(l2)
    i = j = 0
    while i < p and j < q:
        if l1[i] <= l2[j]:
            result.append(l1[i])
            i += 1
        else:
            result.append(l2[j])
            j += 1
    result.extend(l1[i:])
    result.extend(l2[j:])
    return result

QuickSort

def quick_sort(l):
    if l == []:
        return []
    else:
        p = l[0]
        left = quick_sort([x for x in l[1:] if x < p])
        right = quick_sort([x for x in l[1:] if x >= p])
        return left + [p] + right

Sequential Search

def sequential_search(l, k):
    for i in xrange(len(l)):
        if l[i] == k:
            return i

Binary Search

def binary_search(a, k):
    count = 0
    l, r = 0, len(a)-1
    while l <= r:
        count += 1
        mid = (l+r)/2
        if k == a[mid]:
            print count
            return mid
        else:
            if k < a[mid]:
                r = mid
            else:
                l = mid+1