# Goodies Lemonsoftare

### 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)

### Page Tools 