Tag Archive | python

Quick-sort “median-of-three” – Python implementation

def swap(array,a,b):
    array[a],array[b] = array[b],array[a]
def partition(array,start,end):
    median = (end – 1 – start) / 2
    median = median + start
    left = start + 1
    if (array[median] – array[end-1])*(array[start]-array[median]) >= 0:
        swap(array,start,median)
    elif (array[end – 1] – array[median]) * (array[start] – array[end – 1]) >=0:
         swap(array,start,end – 1)
    pivot = array[start]
    for right in range(start,end):
        if pivot > array[right]:
            swap(array,left,right)
            left = left + 1
    swap(array,start,left-1)
    return left-1
def quickSortHelper(array,start,end):
    if start < end:
        splitPoint = partition(array,start,end)
        quickSortHelper(array,start,splitPoint)
        quickSortHelper(array,splitPoint+1,end)
def quickSort(array):
    quickSortHelper(array,0,len(array))
if __name__ == “__main__”:
    array = list(xrange(10))
    array.reverse()
    quickSort(array)
    print array

 

For finding “median-of-three” visit the following link:
Advertisements

Stack v2.0 – Python implementation

Since the version in the previous post sucks i have posted a new version of stack implementation. Note: Use built in version for max performances.
 

class Stack:
    def __init__(self):
        self.items = []
    def pop(self):
        return self.items.pop()
    def push(self,element):
        self.items.append(element)
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    def top(self):
        return self.items[len(self.items) – 1]
    def show(self):
        print self.items
s = Stack()
s.push(1)
s.push(55)
print s.top()
s.show()
s.pop()
s.show()
print s.top()

Finding “median-of-three” with two comparisons – Python implementation

def find_median(a,b,c):
    # (A-B)*(C-A) >= 0
    if (a – b)*(c-a) >= 0:
        return a
        #A
    # (B – A)*(C-B) >=0
    elif (b – a) * (c – b) >=0:
        return b
        #B
    else:
        #C
        return c
a = 1
b = 3
c = 7
print find(a,b,c)
a = 1
b = 6
c = 2
print find(a,b,c)

Depth-first search (DFS) recursive – Python implementation

def dfs_rec(graph,start,path = []):
    path = path + [start]
    for edge in graph[start]:
        if edge not in path:
            path = dfs_rec(graph, edge,path)
    return path
graph = {1: [2, 3],
         2: [1, 4, 5, 6],
         3: [1, 4],
         4: [2, 3, 5],
         5: [2, 4, 6],
         6: [2, 5]}
print dfs_rec(graph,1)

Heap – Python implementation

class Heap:
    #init
    def __init__(self):
        self.buffer = [0]
        self.size = 0
    #insert – key
    def insert(self, key):
        self.buffer.append(key)
        self.size = self.size + 1
        self.bublUp(self.size)
    #bublUp
    def bublUp(self, i):
        if i // 2 > 0:
            if self.buffer[i] < self.buffer[i // 2]:
                 swap(i,i // 2)
            self.bublUp(i // 2)
    #delMin
    def delMin(self):
        minVal = self.buffer[1]
        self.buffer[1] = self.buffer[self.size]
        self.buffer.pop()
        self.bublDown(1)
        return minVal
    #bublDown
    def bublDown(self, i):
        if i * 2 <= self.size:
            mc = self.minChild(i)
            if self.buffer[mc] < self.buffer[i]:
                self.swap(mc,i)
            self.bublDown(mc)
    #minChild
    def minChild(self,i):
        if 2*i + 1 > self.size:
            return 2 * i
        else:
            if self.buffer[2 * i] > self.buffer[2 * i + 1]:
                return 2 * i + 1
            else:
                return 2 * i
    #helper functions
    def swap(self, a, b):
        self.buffer[a],self.buffer[b] = self.buffer[b],self.buffer[a]
    def show(self):
        print self.buffer
h = Heap()
h.insert(4)
h.insert(4)
h.insert(8)
h.insert(9)
h.insert(4)
h.insert(12)
h.insert(9)
h.insert(11)
h.insert(13)
h.show()
print h.delMin()
h.show()

Merge sort – Python implementation

def Sort(left,right):
    i = j = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    result = result + left[i:]
    result = result + right[j:]
    return result
def mergeSort(array):
    if len(array) < 2: return array
    else:
        mid = len(array) / 2
        left = mergeSort(array[:mid])
        right = mergeSort(array[mid:])
        return Sort(left,right)
a = list(xrange(10000))
a.reverse()
mergeSort(a)

Required knowledge for n00b computer scientist – Field algorithms

  1. What is Big-O?
  2. Implement Stack
  3. Implement Queue
  4. Implement Merge-Sort
  5. Implement Quick-Sort
  6. Implement Sequential  Search
  7. Implement Sequential Sorted Search
  8. Implement Brackets Pair Checker (“([{“)
  9. Implement Infix To Postfix conversion
  10. Implement Postfix calculator
  11. Implement base convertor (recursive and regular)
  12. Implement binary search.
  13. Implement palindrome  checker
  14. Implement a function that will enable reversing the input string.
  15. Implement a function that will enable deleting the white space and special characters.
  16. Implement Quick-Sort with random pivot.
  17. Implement Quick-Sort with “Median-of-Three”.
  18. Implement algorithm which finds median of three numbers with two comparisons.
  19. Implement graph
  20. Implement random contraction algorithm – Karger’s algorithm minimum cut
  21. Implement DFS (Depth-first Search)
  22. Implement non-recursive DFS (Depth-first Search)
  23. Implement BFS (Breadth-First Search)
  24. Implement BFS (Breadth-First Search) path finding
  25. Implement topological sort using non-recursive DFS (Depth-first Search)
  26. Implement computing Strong Connecting Components (SCC) – Kosaraju’s or Tarjan’s algorithm (improved Kosaraju’s version).
  27. Implement Dijkstra’s shortest path algorithm

Dijkstra’s shortest path algorithm – Python Implementation

from pprint import pprint
def dijkstra(graph,start,target):
    inf = 0
    for u in graph:
        for v ,w in graph[u]:
           inf = inf + w
    dist = dict([(u,inf) for u in graph])
    prev = dict([(u,None) for u in graph])
    q = graph.keys()
    dist[start] = 0
    #helper function
    def x(v):
        return dist[v]
    #
    while q != []:
        u = min(q, key=x)
        q.remove(u)
        for v,w in graph[u]:
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    #”way”
    trav = []
    temp = target
    while temp != start:
        trav.append(prev[temp])
        temp = prev[temp]
    trav.reverse()
    trav.append(target)
    return ” -> “.join(trav),dist[target]
graph = {
    ‘A’ : [(‘B’,20), (‘D’, 80), (‘G’, 90)],
    ‘B’ : [(‘F’, 10)],
    ‘C’ : [(‘F’, 50), (‘H’, 20)],
    ‘D’ : [(‘G’, 20), (‘C’, 10)],
    ‘E’ : [(‘B’, 50),(‘G’, 30)],
    ‘F’ : [(‘D’, 40),(‘C’, 10)],
    ‘G’ : [(‘A’, 20)],
    ‘H’ : []
    }
pprint(graph)
print
traverse, dist = dijkstra(graph,’A’,’C’)
print traverse
print “Distance:”,dist

Quicksort – Python implementation (pivot = the first element of the list)

import random
import time
def swap(array,a,b):
    array[a],array[b] = array[b],array[a]
def partition(array,start,end):
    left = start + 1
    pivot = array[start]
    for right in range(start+1,end):
        if pivot > array[right]:
            swap(array,left,right)
            left = left + 1
    swap(array,start,left-1)
    return left-1
def quickSortHelper(array,start,end):
    if start < end:
        splitPoint = partition(array,start,end)
        quickSortHelper(array,start,splitPoint)
        quickSortHelper(array,splitPoint+1,end)
def quickSort(array):
    quickSortHelper(array,0,len(array))
if __name__ == “__main__”:
    array = [random.randint(0,1000) for r in xrange(10000)]
    start = time.time()
    quickSort(array)
    end = time.time()
    print end – start

Topological sort using non-recursive DFS – Python implementation

def dfs(graph,start):
    path = []
    stack = [start]
    label = len(graph)
    result = {}
    while stack != []:
        #this for loop could be done in other ways also
        for element in stack:
            if element not in result:
                result[element] = label
                label = label – 1
        v = stack.pop()
        if v not in path: path.append(v)
        for w in reversed(graph[v]):
            if w not in path and not w in stack:
                stack.append(w)
    result = {v:k for k, v in result.items()}
    return path,result
#
#
#
#Input:
graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
print dfs(graph,1)
#
#
#
Output:
([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})
#
Check the result with the sample.
        1
       /
      3
     /\
    5  6
   /
  4
 /
7
If you think that the solution is not good, pls write me a comment.