User:Faridani/python
Basics of Python
edit1 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
edit#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
edithttp://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):
editmydict = {'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):
editkeylist = 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):
editfor key, value in sorted(mydict.iteritems(), key=lambda (k,v): (v,k)): print "%s: %s" % (key, value)