User Tools

Site Tools


python:algorithms

Sorting algorithms implemented in python

INSERTION SORT

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. The index j is moving starting with the second element to the n-1 element in the array to be sorted; for each iteration, we pick up the A[j] value and we start to move the elements to the right, until the right position of A[j] is found, at which point is inserted.

The script who implements the algorithm:

#!/usr/bin/env python
# -*- coding: utf8 -*-
 
# INSERTION SORT ALGORITHM
# 
# Cristian NAVALICI ncristian at lemonsoftware dot eu
 
# because first element of a list is with index=0 and not 1,
# range is starting with 1, instead of 2
# while i > -1 instead of i > 0
 
import random
 
def insertion_sort(examplelist):
    '''this is actually the algorithm'''
    for j in range(1, len(examplelist)):
        key = examplelist[j]
        i = j - 1
        while i > -1 and examplelist[i] > key:
            examplelist[i+1] = examplelist[i]
            i = i - 1
        examplelist[i+1] = key
 
    return examplelist
 
def generate_random(howmany):
    '''generates a list with random elements'''
    list = []
    for i in range(0, howmany):
        list.append(random.randint(0, howmany*10-1))
    return list
 
 
size = int(raw_input("How many elements to sort? "))
testdata = generate_random(size)
 
print "Generated a list with %s random elements" % size
print testdata
print "Sorted..."
print insertion_sort(testdata)


MERGE SORT

Merge sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945.

  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying merge sort.
  4. Merge the two sublists back into one sorted list.

Python script with DEBUG=0 (off). Turn on (DEBUG=1) to see the messages during the algorithm.

#!/usr/bin/env python
# -*- coding: utf8 -*-
 
# MERGE SORT ALGORITHM
# 
# Cristian NAVALICI ncristian at lemonsoftware dot eu
 
import random
DEBUG = 0
call = 0
 
def merge_split(list):
    n = len(list)
    global call
    call = call + 1 # just for debug
 
    if DEBUG: 
        print "merge_split: call # %d" % call
        print "merge_split: list-> %s" % list
    if n > 1:
        # go recursively
        middle = n/2
        if DEBUG: print "merge_split: middle = %d" % (n/2)
        left = merge_split(list[:middle])
        right = merge_split(list[middle:])
        return merge(left, right)
    return list
 
 
def merge(left, right):
    result = []
    p = len(left)
    q = len(right)
    i = j = 0
 
    if DEBUG: print "merge: left/right - %s/%s" % (left, right)
 
    while i < p and j < q:
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
 
    return result
 
 
 
def generate_random(howmany):
    '''generates a list with random elements'''
    list = []
    for i in range(0, howmany):
        list.append(random.randint(0, howmany*10-1))
    return list
 
 
size = int(raw_input("How many elements to sort? "))
testdata = generate_random(size)
 
print "Generated a list with %s random elements" % size
print testdata
print "Sorted..."
print merge_split(testdata)

python/algorithms.txt · Last modified: 2013/03/16 17:41 (external edit)