User Tools

Site Tools


python:algorithms

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

python:algorithms [2013/03/16 17:41]
python:algorithms [2013/03/16 17:41] (current)
Line 1: Line 1:
 +==== Sorting algorithms implemented in python ====
 + 
  
 +=== INSERTION SORT ===
 +
 +[[http://​en.wikipedia.org/​wiki/​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:
 +
 +<code python>
 +#​!/​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)
 +</​code>​
 +
 +
 +----
 +
 +
 +=== 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.
 +
 +
 +  - If the list is of length 0 or 1, then it is already sorted. Otherwise:
 +  - Divide the unsorted list into two sublists of about half the size.
 +  - Sort each sublist recursively by re-applying merge sort.
 +  - 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.
 +<code python>
 +#​!/​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)
 +</​code>​
python/algorithms.txt ยท Last modified: 2013/03/16 17:41 (external edit)