Introduction to Algorithms

Today my copy of Introduction to Algorithms came in the mail (a gift from the family). I've decided, mostly inspired by Peteris Krumins to revisit classic algorithms as it's been a while since I've taken a look at them.

I have decided to also take a look at the MIT Intro to Algorithms course in order to revisit algorithms and concepts. I won't provide any lecture notes or anything since Peteris did a much better job of of writing lecture notes that I ever could but I did go ahead and create some python implementations of the sorting algorithms covered in the first lecture. These haven't been tested extensively so there might be bugs but I'm pretty sure they're working. I'd be interested to see how well these work with large input data, particularly the merge sort.

insertion-sort.py

#!/usr/bin/env python

def sort(array):
  for j in xrange(1, len(array)):
    i = j - 1
    key = array[j]
    while i >= 0 and key < array[i]:
      array[i+1] = array[i]
      i = i - 1
    array[i+1] = key
  return array

merge-sort.py

#!/usr/bin/env python

def sort(array):
  mergesort(array, 0, len(array))
  
def mergesort(array, start, end):
  if end > start + 1:
    pivot = (start + end) / 2
    mergesort(array, start, pivot)
    mergesort(array, pivot, end)
    merge(array, start, pivot, end)
  
def merge(array, start, pivot, end):
  l = array[start:pivot]
  lenl = pivot - start
  r = array[pivot:end]
  lenr = end - pivot
  i = j = 0
  for k in xrange(start,end):
    if j >= lenr or (i < lenl and l[i] <= r[j]):
      array[k] = l[i]
      i += 1
    else:
      array[k] = r[j]
      j += 1

	#!/usr/bin/env python

	def sort(array):
	for j in xrange(1, len(array)):
	i = j - 1
	key = array[j]
	while i >= 0 and key < array[i]:
	array[i+1] = array[i]
	i = i - 1
	array[i+1] = key
	return array

	#!/usr/bin/env python

	def sort(array):
	mergesort(array, 0, len(array))

	def mergesort(array, start, end):
	if end > start + 1:
	pivot = (start + end) / 2
	mergesort(array, start, pivot)
	mergesort(array, pivot, end)
	merge(array, start, pivot, end)

	def merge(array, start, pivot, end):
	l = array[start:pivot]
	lenl = pivot - start
	r = array[pivot:end]
	lenr = end - pivot
	i = j = 0
	for k in xrange(start,end):
	if j >= lenr or (i < lenl and l[i] <= r[j]):
	array[k] = l[i]
	i += 1
	else:
	array[k] = r[j]
	j += 1

Ian Lewis