Merge Sort using Python

Merge sort contains two phases.
1. Partition phase
2. Merge phase

In partition phase the list is broken in to parts by calculating mid point.
In merging phase the list is merged by sorting. Finally a sorted list is obtained.

 Merge sort is a divide and conqure algorithm. Divide and Conqure means divide the problem in to small parts, solve these sub parts and finally combine the solutions to get the final answer.

Source Code:

def part(a,l,r):
    if l<r:
        m=(l+r)//2
        part(a,l,m)
        part(a,m+1,r)
        merge(a,l,m,r)
    #print(b)
def merge(a,l,m,r):
    b=[]
    k=0
    i=l
    j=m+1
    while i<=m and j<=r:
        if a[i]<a[j]:
            b.append(a[i])
            k=k+1
            i=i+1
        else:
            b.append(a[j])
            k=k+1
            j=j+1
    while i<=m:
        b.append(a[i])
        k=k+1
        i=i+1
    while j<=r:
        b.append(a[j])
        k=k+1
        j=j+1
    for i in range(k):
        a[l]=b[i]
        l=l+1
a=[ ]
n=int(input("enter n"))
for i in range(n):
    a.insert(i,int(input()))
l=0
r=n-1
part(a,l,r)
print(a)
   
Output:   

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
enter n5
10
5
3
7
2
[2, 3, 5, 7, 10]
>>>


       

Queue Using List

Queue is a linear data structure. Queue has  First In First Out (FIFO) policy. In Queue elements are inserted at one end and deleted at other end. Queue does the insertion by using rear variable and deletion by using front variable. Rear value increases by one unit at insertion and Front value increases by one unit at deletion.

Source Code:

def display():
    if not MyQueue:
        print("queue is empty")
    else:
        print(MyQueue)
def insert():
    global rear
    if rear < size:
        value=int(input("enter number"))
        MyQueue.append(value)
        rear=rear+1
    else:
        print("Queue overflow!")
def delete():
    global front
    if not MyQueue:
        print("queue underflow")
    else:
        print("element deleted is %d" %MyQueue[front])
        del MyQueue[front]
def stop():
    print("you are about to terminate the program")
    exit(0)
def menulist():
    print("1.insert\n2.delete")
    print("3.display")
    print("4.exit")
def default():
    print("check your input")
MyQueue = []
rear=0
front=0
size=int(input("enter the size of queue"))
menulist()
while True:
    menu= {
    1: insert,
    2: delete,
    3: display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()


Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
enter the size of queue3
1.insert
2.delete
3.display
4.exit
Please enter your choice1
enter number10
Please enter your choice1
enter number20
Please enter your choice1
enter number30
Please enter your choice3
[10, 20, 30]
Please enter your choice1
Queue overflow!
Please enter your choice2
element deleted is 10
Please enter your choice3
[20, 30]
Please enter your choice2
element deleted is 20
Please enter your choice3
[30]
Please enter your choice2
element deleted is 30
Please enter your choice3
queue is empty
Please enter your choice2
queue underflow
Please enter your choice4
you are about to terminate the program

>>>

Stack using Lists

Queue is a linear data structure. Queue has  First In First Out (FIFO) policy. In Queue elements are inserted at one end and deleted at other end. Queue does the insertion by using rear variable and deletion by using front variable. Rear value increases by one unit at insertion and Front value increases by one unit at deletion.

Source Code:

MyStack = []
size=int(input("enter the size of stack"))
def display():
 print("Stack currently contains:")
 for Item in MyStack:
  print(Item)
def push():
 if len(MyStack) < size:
    value=int(input("enter number"))
    MyStack.append(value)
 else:
  print("Stack is overflow!")
def pop():
 if len(MyStack) > 0:
  MyStack.pop()
 else:
  print("Stack is underflow.")
def stop():
    print("you are about to terminate the program")
    exit(0)
def menulist():
    print("1.push\n2.pop")
    print("3.display")
    print("4.exit")
def default():
    print("check your input")
menulist()
while True:
    menu= {
    1: push,
    2: pop,
    3: display,
    4: stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()



Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
enter the size of stack3
1.push
2.pop
3.display
4.exit
Please enter your choice1
enter number10
Please enter your choice1
enter number20
Please enter your choice1
enter number30
Please enter your choice3
Stack currently contains:
10
20
30
Please enter your choice1
Stack is overflow!
Please enter your choice2
Please enter your choice3
Stack currently contains:
10
20
Please enter your choice2
Please enter your choice3
Stack currently contains:
10
Please enter your choice2
Please enter your choice3
Stack currently contains:
Please enter your choice2
Stack is underflow.

Please enter your choice4

Linear Search Using Python

Linear Search is the simplest way of searching key element from the list of elements. In linear search the order of elements can be in ascending order or can be in descending order. The elements in the list can be redundant. Time complexity of this search is O(n).

Source Code:

a=[]
count=0
n=int(input("how many elements u want to enter"))
for i in range(n):
    num=int(input("enter number"))
    a.append(num)
print(a)
key=int(input("enter the key to be serched"))
for i in range(n):
    if key==a[i]:
        print("%d found in %d" %(key,i))
        count=count+1
if count==0:
    print("%d not found" %key)
else:
    print("%d found %d time(s)" %(key,count))

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

how many elements u want to enter6

enter number1

enter number2

enter number3

enter number4

enter number5

enter number6

[1, 2, 3, 4, 5, 6]

enter the key to be serched3

3 found in 2

3 found 1 time(s)

>>> ================================ RESTART ================================

>>> 

how many elements u want to enter6

enter number1

enter number2

enter number3

enter number3

enter number4

enter number5

[1, 2, 3, 3, 4, 5]

enter the key to be serched3

3 found in 2

3 found in 3

3 found 2 time(s)

>>> 

Binary Search Tree

Binary Search Tree 

Binary search tree is a binary tree where node values greater than root node are placed towards right side of root and node values less than or equal to root node are placed towards left side of root.

Source Code:

class Node:
    def __init__(self,data):
        self.data=data
        self.rchild=None
        self.lchild=None
class Bst:
    def __init__(self):
        self.root=None             
 
    def createtree(self,data):
        if self.root==None:
            self.root = Node(data)
        else:
            temp = self.root
            while temp !=None:
                if data < temp.data:
                    if temp.lchild==None:
                        temp.lchild = Node(data)
                        return
                    else:
                        temp = temp.lchild
                else:
                    if temp.rchild==None:
                        temp.rchild = Node(data)
                        return
                    else:
                        temp = temp.rchild
     
    def inorder(self, root):
        if root!=None:
            self.inorder(root.lchild)
            print(root.data)
            self.inorder(root.rchild)
 
    def preorder(self, root):
        if root!=None:
            print(root.data)
            self.preorder(root.lchild)         
            self.preorder(root.rchild)
         
    def postorder(self,root):
        if root!=None:
            self.postorder(root.lchild)         
            self.postorder(root.rchild)
            print(root.data)

    def display(self,root):
        if root!=None:         
            print(root.data)
            self.inorder(root.rchild)
            self.inorder(root.lchild)
         
    def count(self, root):
        if root == None:
            return 0
        else:
            return 1 + self.count(root.lchild) + self.count(root.rchild)

def menu():
    global ch
    print("\n1.create\n2.preorder\n3.postorder\n4.inorder
                   \n5.display\n6.count\n7.stop")
    ch=int(input("enter u r choice"))

t=Bst()
while True:
    menu()
    if ch==1:
         n=int(input("enter no of node for tree"))
         for i in range(n):
            data=int(input("enter data"))
            t.createtree(data)
    elif ch==2:
       print("preorder")
       t.preorder(t.root)
    elif ch==3:
       print("postorder")
       t.postorder(t.root)
    elif ch==4:
       print("inorder")
       t.inorder(t.root)
    elif ch==5:
       t.display(t.root)
    elif ch==6:
        print("number of nodes in binary search tree")
        print(t.count(t.root))
    else:
        exit(0)
 

 

 


 

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice1
enter no of node for tree3
enter data20
enter data10
enter data30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice2
preorder
20
10
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice3
postorder
10
30
20

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice4
inorder
10
20
30

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice5
20
30
10

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice6
number of nodes in binary search tree
3

1.create
2.preorder
3.postorder
4.inorder
5.display
6.count
7.stop
enter u r choice7
>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using Linked List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

class Node:
  def __init__(self,r,c,v):
    self.r=r
    self.c=c
    self.v=v
    self.next=None
class Sparse:
  def __init__(self):
    self.start=None
  def createlist(self,newnode):
    temp=self.start
    if self.start==None:
      self.start=newnode
    else:
      while temp.next!=None:
        temp=temp.next
      temp.next=newnode
  def display(self):
    temp=self.start
    print("row\tcol\tval")
    while temp!=None:
      print("%d\t%d\t%d" %(temp.r,temp.c,temp.v))
      temp=temp.next

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0
sp=Sparse()
print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
    for i in range(row):
      for j in range(col):
        if X[i][j]!=0:
          newnode=Node(i,j,X[i][j])
          sp.createlist(newnode)       
    sp.display()
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

row col val

0 0 1

0 1 2

0 2 3

2 2 4

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html

Sparse Matrix Using List

This is sparse matrix program. A matrix in which number of zeros are greater than half the size of matrix is known as sparse matrix.

Source Code:

row=int(input("enter number of rows : "))
col=int(input("enter number of coloumns : "))

X = [[0]*col for j in range(row)]
count=0

print ("entry elements")
for i in range (row):
  for j in range (col): 
    X[i][j] = int(input())

print("matrix is:")
for i in range(row):
    for j in range(col):
        print(X[i][j], end=' ')
    print()

for i in range(row):
    for j in range(col):
        if X[i][j]==0:
            count=count+1

print("number of zeros:",count)

if count>(row*col)//2:
    print("sparse matrix")
else:

    print("not sparse matrix")

Output:

Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

4

5

6

matrix is:

1 2 3 

0 0 0 

4 5 6 

number of zeros: 3

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

4

5

matrix is:

1 2 3 

0 0 0 

0 4 5 

number of zeros: 4

not sparse matrix

>>> ================================ RESTART ================================

>>> 

enter number of rows : 3

enter number of coloumns : 3

entry elements

1

2

3

0

0

0

0

0

4

matrix is:

1 2 3 

0 0 0 

0 0 4 

number of zeros: 5

sparse matrix

>>>

Now my new Blog on Fundamentals of Python can be found at https://fundamentalsofpython.blogspot.com/2020/02/list-manipulations.html