Bubble sort in python

Bubble sort python code.

def bubble_sort(A):
    n = len(A)    
    for i in range(0,n):
        for j in range (i+1,n):
            if A[i]>A[j]:
                A[i],A[j]=A[j], A[i]

if __name__=="__main__":
    A = [7,3,5,2]
    print A
    bubble_sort(A)
    print A

Output:

[7, 3, 5, 2]
[2, 3, 5, 7]

Selection sort in python

Selection sort python code.

def get_index_of_smallest(A, i):
    index_of_smallest = i
    for j in range(i+1, len(A)):
        if A[index_of_smallest]>A[j]:
            index_of_smallest = j;
    return index_of_smallest


def selection_sort(A):
    for i in range (0, len(A)):
        index_of_smallest = get_index_of_smallest(A,i)
        A[index_of_smallest], A[i] = A[i], A[index_of_smallest]

if __name__=="__main__":
    A = [7,3,5,2]
    print A
    selection_sort(A)
    print A

Output:

[7, 3, 5, 2]
[2, 3, 5, 7]

Insertion sort in python

Insertion sort python code.

def insert(A,i):
    value = A[i]
    j = i
    while j != 0 and A[j-1]>value:
        A[j] = A[j-1]
        j = j - 1
    A[j] = value


def insertion_sort(A):
     for i in range(len(A)):
         insert(A, i)

if __name__=="__main__":
    A = [7,3,5,2]
    print A
    insertion_sort(A)
    print A

Output:

[7, 3, 5, 2]
[2, 3, 5, 7]

DFS Algorithm in Python

Depth-first search (DFS) is very usefull for traversing or searching a tree, tree structure, or graph. Here python implementation of DFS .
All source code available on github

 # DA_DFS.py
class DFS:
    def __init__(self, node,edges):
        self.node = node
        self.edges = edges
        self.color=['W' for i in range(0,node)] # W for White
        self.graph =color=[[False for i in range(0,node)] for j in range(0,node)]
        self.parent =[-1 for u in range(0,node)]

        # Start DFS
        self.construct_graph()
        self.dfs_traversal()

    def construct_graph(self):
        for u,v in self.edges:
            self.graph[u][v], self.graph[v][u] = True, True

    def dfs_visit(self, u):
        self.color[u]='G' # G for Gray
        for i in range(0, self.node):
            if self.graph[u][i]==True and self.color[i]=='W':
                self.parent[i]=u
                self.dfs_visit(i)
        self.color[u]='B' # B for black

    def dfs_traversal(self):
        for i in range(0,self.node):
            if self.color[i]=='W': # W for white
                self.dfs_visit(i)

    def print_path(self, source, destination):
        if destination==source:
            print destination,
        elif self.parent[destination] == -1:
            print "No Path"
        else:
            self.print_path(source, self.parent[destination])
            print "-> ",destination,

node = 8 # 8 nodes from 0 to 7
edges =[(0,1),(0,3),(1,2),(1,5),(2,7),(3,4),(3,6),(4,5),(5,7)] # bi-directional edge

dfs = DFS(node, edges)
dfs.print_path(0, 7)
print ""
dfs.print_path(2, 5)
print ""
dfs.print_path(0, 4)

Output:

0 ->  1 ->  2 ->  7 
2 ->  7 ->  5 
0 ->  1 ->  2 ->  7 ->  5 ->  4

BFS Algorithm in Python

Breadth-first search(BFS) is one of the most widely used graph algorithm for single source shortest path. Here I shown python implemenation of this beautiful algorithm.
All source code available on github

#DA_BFS.py
from collections import deque

class BFS:
    def __init__(self, node,edges, source):
        self.node = node
        self.edges = edges
        self.source = source
        self.color=['W' for i in range(0,node)] # W for White
        self.graph =color=[[False for i in range(0,node)] for j in range(0,node)]
        self.queue = deque()
        self.parent =[-1 for u in range(0,node)]

        # Start BFS algorithm
        self.construct_graph()
        self.bfs_traversal()

    def construct_graph(self):
        for u,v in self.edges:
            self.graph[u][v], self.graph[v][u] = True, True

    def bfs_traversal(self):

        self.queue.append(self.source)
        self.color[self.source] = 'B' # B for Black

        while len(self.queue):
            u =  self.queue.popleft()
            for v in range(0,self.node):
                if self.graph[u][v] == True and self.color[v]=='W':
                    self.color[v]='B'
                    self.queue.append(v)
                    self.parent[v]=u

    def print_shortest_path(self, destination):
        if destination==self.source:
            print destination,
        elif self.parent[destination] == -1:
            print "No Path"
        else:
            self.print_shortest_path(self.parent[destination])
            print "-> ",destination,



node = 8 # 8 nodes from 0 to 7
edges =[(0,1),(0,3),(1,2),(1,5),(2,7),(3,4),(3,6),(4,5),(5,7)] # bi-directional edge
source = 0 # set fist node (0) as source

bfs = BFS(node,edges,source)
bfs.print_shortest_path(5) # shortest path from 0 to 5
print
bfs.print_shortest_path(7) # shortest path from 0 to 7

Output:

0 ->  1 ->  5
0 ->  1 ->  2 ->  7