User:Faridani/python

Basics of Python

1 linked list 2 Sorting Algorithms 2.1 Merging two sorted lists 2.2 Quick Sort 2.3 Merge Sort 3 Look and say algorithm linked list

A very simple implementation of a singly linked list in python is below

class node():
	def __init__(self, value, next = None):
		self.value = value
		self.next = next

if __name__=='__main__':
	mylist = node('a', node('b',node('c',node('d'))))
	print 'mylist =', mylist
	print 'mylist.next', mylist.next
	print 'mylist.next.value', mylist.next.value
	print 'mylist.next.next.value', mylist.next.next.value
	nextnode = mylist
	print 
	print 'Traversing the list' 
	while nextnode != None:
		print nextnode.value
		nextnode = nextnode.next

We can extend it to a list with a container class and add the append method

class node():
	def __init__(self, value, next = None):
		self.value = value
		self.next = next
	def __str__(self):
		return str(self.value)

class linkedList():
	def __init__(self):
		self.first = None
		self.last = None
	
	def append(self, insertedNode):
		if self.first == None:
			self.first = node(insertedNode)
			self.last = self.first
			print "inserted ", insertedNode
		elif self.first == self.last: 
			self.last = node(insertedNode)
			self.first.next = self.last
			print "inserted ", insertedNode
		else:
			current =  node(insertedNode)
			self.last.next = current
			self.last = current
			print "inserted ", insertedNode
			
	def __str__(self):
		strout = str(self.first)
		rest = self.first.next
		while rest != None:
			strout += ', '+ str(rest)
			rest = rest.next
		return strout	
	
	
if __name__=='__main__':
	mylist = linkedList()
	mylist.append(2)
	mylist.append(4)
	mylist.append(10)
	mylist.append(12)
	print 'mylist =', mylist
	

http://stackoverflow.com/questions/280243/python-linked-list

Sorting Algorithms

Merging two sorted lists

#merging two sorted lists

def merge(array1, array2):
	pointer1 = 0
	pointer2 = 0
	output = []
	while True:
		if array1[pointer1]<array2[pointer2]:
			output.append(array1[pointer1])
			pointer1 +=1
			if pointer1 >=len(array1):
				output += array2[pointer2:]
				break
		else:
			output.append(array2[pointer2])
			pointer2 +=1
			if pointer2 >=len(array2):
				output +=array1[pointer1:]
				break
	return output

print merge([1,2,4],[3,4,5,6])
Quick Sort

# Quick sort in python
def QuickSort(myarray = []):
	if len(myarray) <= 1:
		return myarray
	else:
		pivot = myarray[0]
		smaller = []
		larger = []
		for i in myarray[1:]:
			if i<=pivot:
				smaller.append(i)
			else:
				larger.append(i)
		return QuickSort(smaller) + [pivot] + QuickSort(larger)
			

import random
a =  [random.randint(1,100) for i in range(20)]
print 'Original Data'
print a
print 
results = QuickSort(a)
print 
print 
print results

Merge Sort

#Merge Sort in Python

def merge(array1, array2):
	pointer1 = 0
	pointer2 = 0
	output = []
	while True:
		if array1[pointer1]<array2[pointer2]:
			output.append(array1[pointer1])
			pointer1 +=1
			if pointer1 >=len(array1):
				output += array2[pointer2:]
				break
		else:
			output.append(array2[pointer2])
			pointer2 +=1
			if pointer2 >=len(array2):
				output +=array1[pointer1:]
				break
	return output

def MergeSort(myarray):
	arraylength = len(myarray)
	if arraylength<=1:
		return myarray
	else:
		left = myarray[0:int(round(arraylength/2))]
		right = myarray[int(round(arraylength/2)):]

		return merge(MergeSort(left),MergeSort(right))

import random
a =  [random.randint(1,100) for i in range(20)]
print 'Original Data'
print a
print 
results = MergeSort(a)
print 
print 
print results

Look and say algorithm

def lookandsay(mystring):
	print mystring
	element = mystring[0]
	mystring = mystring[1:]
	counter = 1
	for letter in mystring:
		if letter == element:
			counter +=1
		else:
			
			sys.stdout.write("%d%s" % (counter,element))
			counter = 1
			element = letter
	print "%d%s\n" % (counter,element)


import sys			
if __name__ == '__main__':
		lookandsay('11123422')
		print 
		lookandsay('111234221')

Retrieved from "http://rlang.org/wiki/Basics_of_Python"

Sorting a dictionary

http://www.saltycrane.com/blog/2007/09/how-to-sort-python-dictionary-by-keys/

How to sort a dict by keys (Python 2.4 or greater):

mydict = {'carl':40,
          'alan':2,
          'bob':1,
          'danny':3}

for key in sorted(mydict.iterkeys()):
    print "%s: %s" % (key, mydict[key])

Taken from the Python FAQ: http://www.python.org/doc/faq/general/#why-doesn-t-list-sort-return-the-sorted-list. To sort the keys in reverse, add reverse=True as a keyword argument to the sorted function.

How to sort a dict by keys (Python older than 2.4):

keylist = mydict.keys()
keylist.sort()
for key in keylist:
    print "%s: %s" % (key, mydict[key])

The results are the same as the above.

How to sort a dict by value (Python 2.4 or greater):

for key, value in sorted(mydict.iteritems(), key=lambda (k,v): (v,k)):
    print "%s: %s" % (key, value)