Randomized Quick Sort in python

	from random import randint
	def inPlaceQuickSort(A,start,end):
	if start<end:
	pivot=randint(start,end)
	temp=A[end]
	A[end]=A[pivot]
	A[pivot]=temp
	p=inPlacePartition(A,start,end)
	inPlaceQuickSort(A,start,p-1)
	inPlaceQuickSort(A,p+1,end)
	def inPlacePartition(A,start,end):
	pivot=randint(start,end)
	temp=A[end]
	A[end]=A[pivot]
	A[pivot]=temp
	newPivotIndex=start-1
	for index in xrange(start,end):
	if A[index]<A[end]:#check if current val is less than pivot value
	newPivotIndex=newPivotIndex+1
	temp=A[newPivotIndex]
	A[newPivotIndex]=A[index]
	A[index]=temp
	temp=A[newPivotIndex+1]
	A[newPivotIndex+1]=A[end]
	A[end]=temp
	return newPivotIndex+1
	X=[4,5,7,4,3,6,0,4,22,45,82]
	inPlaceQuickSort(X,0,len(X)-1)
	#X=[0, 3, 4, 4, 4, 5, 6, 7, 22, 45, 82]

view raw randomizedquicksort.py hosted with ❤ by GitHub

MergeSort in python

	def mergeSort(A):
	if len(A)>1:
	[x1,x2]=divide(A)
	#print x1,x2
	x1,leftInv=mergeSort(x1)
	x2,rightInv=mergeSort(x2)
	#print leftInv,rightInv
	merged,splitInv=merge(x1,x2)
	#print splitInv
	return merged,(leftInv+rightInv+splitInv)
	else:
	return A,0
	def divide(A):
	size=len(A)
	halfSize=size/2
	x1=[]
	x2=[]
	for index in xrange(0,halfSize):
	x1.append(A[index])
	for index in xrange(halfSize,size):
	x2.append(A[index])
	return [x1,x2]
	def merge(x1,x2):
	x=[]
	x1Index=0
	x2Index=0
	invCount=0
	size1=len(x1)
	size2=len(x2)
	while ( x1Index < size1 and x2Index < size2):
	if x1[x1Index]<=x2[x2Index]:
	x.append(x1[x1Index])
	x1Index=x1Index+1
	else:
	x.append(x2[x2Index])
	x2Index=x2Index+1
	invCount += (size1-x1Index)
	for i in range(x1Index,size1):
	x.append(x1[i])
	for i in range(x2Index,size2):
	x.append(x2[i])
	return x,invCount
	a=[6,5,4,3,2,1]
	print 'before sorting',a
	x=mergeSort(a)
	print 'after sorting',x

view raw mergesort.py hosted with ❤ by GitHub

Evolution in programming Languages

The functional programming is catching up. Java's win over other language came by its developer friendly nature and its adaptation of OOPS paradigm. Following the same path, focusing on Functional Programming few new languages are trying to replace Java and also promise to lower the syntactic noise present in most of programming Languages. Below you can find few links of good write up on a comparison of these languages.

1. Digithead's Lab Notebook: Hipster programming languages
:
2. http://codemonkeyism.com/scala-vs-clojure/

Printing breadth First Levels of a graph (Or) Tree in python

Today I came across a situation where I had to handle the breadth first levels of a binary tree, each level at once.

Consider the binary tree below,

                  1
          2            3
     4       5     6     7

I had to process the nodes level by level,
1
2,3
4,5,6,7

I identified that this problem can be easily solved by considering the tree and DAG ( directed acyclic graph) and performing a bread first search or traversal  (BFS) on the tree, starting from the root. But the challenge was BFS, gives me only the path, in this case it would be [ 1,2,3,4,5,6,7]. But this wont be sufficient,  I would need to identify the level or depth of each node as I do BFS, so that I can handle the nodes level by level.

Google pointed me to a stackoverflow link http://stackoverflow.com/questions/1894846/printing-bfs-binary-tree-in-level-order-with-specific-formatting , the question exactly matched my situation but unfortunately it did not have any simple or generic solution using bfs. So i decided to write up one on my own, here is the code

This code is also posted in the python recipe of activestate.com

I Came up with another version based on Recursion, which is specific to binary tree. Obviously, this one is very simple than that of its generic graph counter part shown above.