Binary Search

This searching technique is applied on sorted list. First calculate mid point then follow the following procedure

1. Check whether a[mid] and key are equal , if condition is true print the position, if this is false

2.Compare whether key is greater than a[mid] ,if this is true update l to mid+1 and repeat the above procedure, if this is false

3. Update h to mid -1 and repeat the above procedure.

4. If all the above conditions are false print 'key not found'

Source Code: 

a=[]

flag=0

n=int(input("enter how many number of elements"))

for i in range(n):

    a.append(int(input()))

print("List is:\n")

print(a)

key=int(input("enter key"))

l=0

h=n-1

while l<=h:

    mid=(l+h)//2

    if key==a[mid]:

        flag=1

        break

    elif key>a[mid]:

        l=mid+1

    else:

        h=mid-1

if flag==1:

    print("%d found at %d position" %(key,mid))

else:

    print("%d not found" %key)

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 how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key10

10 not found

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

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key1

1 found at 0 position

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

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key2

2 found at 1 position

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

>>> 

enter how many number of elements5

1

2

3

4

5

List is:

[1, 2, 3, 4, 5]

enter key5

5 found at 4 position

>>> 

Quick Sort using Python

Quick sort is a divide and conquer algorithm. In this sort pivot element is chosen for sorting. Usually first element of the list is chosen as pivot element. In this sorting comparison is done to move in forward direction and also in backward direction.

To move in forward direction (from left to right) element values should be less than or equal to pivot element value.

When this condition fails now start moving in backward direction(from right to left), to move so elements values should  be greater than pivot element.

When the above two conditions fail compare value of i and j, if i is less than j, swap a[i] and a[j].

When the above three conditions fails swap a[j] and a[p]. At this point list is broken in to two parts. The left part of pivot  contain elements less than pivot value and the right part contain elements greater than pivot value. Repeat the above process until sorted list is obtained.

Source Code:

def qsort(a,left,right):
    if left<right:
        i=left
        j=right
        p=left
        while i<j:
            while a[i]<=a[p] and i<right:
                i=i+1
            while a[j]>a[p] and j>left:
                j=j-1
            if i<j:
                a[i],a[j]=a[j],a[i]
        a[p],a[j]=a[j],a[p]
        qsort(a,left,j-1)
        qsort(a,j+1,right)
a=[]
n=int(input("enter number of elements"))
for i in range(n):
    a.append(int(input()))
print("List before sorting")
print(a)
left=0
right=n-1
qsort(a,left,right)
print("List after sorting")

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 number of elements5

3

4

2

5

1

List before sorting

[3, 4, 2, 5, 1]

List after sorting

[1, 2, 3, 4, 5]

>>>

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

Selection sort

As per my logic selection sort find minimum element from the list and put it in the starting of the list at the end of first iteration. In the second iteration second minimum element is placed in the second position and so on.

Source Code:

a=[]

n=int(input("Enter number of elements"))

for i in range(n):

    a.append(int(input()))

print("List before sorting")

print(a)

for i in range(n):

    for j in range(i+1,n):

        if a[i]>a[j]:

            a[i],a[j]=a[j],a[i]

print("List after sorting")

print(a)

Output:

Enter number of elements5

5

4

3

2

1

List before sorting

[5, 4, 3, 2, 1]

List after sorting

[1, 2, 3, 4, 5]

Insertion Sort using python

This is comparison based sorting. Playing cards is an example of insertion sort.

Source Code:

def insertion(a,n):
    for i in range(n):
        temp=a[i]
        j=i
        while j>0 and a[j-1]>temp:
            a[j]=a[j-1]
            j=j-1
            a[j]=temp
a=[]
n=int(input("Enter number of elements"))
for i in range(n):
    a.append(int(input()))
print("list before sorting")
print(a)
insertion(a,n)
print("list after sorting")

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 number of elements5

10

30

20

11

5

list before sorting

[10, 30, 20, 11, 5]

list after sorting

[5, 10, 11, 20, 30]

>>> 

Fibonacci Search

Fibonacci Search is a searching technique, where key position is found by using fibonacci list. In this technique two lists are used  one is input list and one is fibonacci list. For this search input list should contain numbers in ascending order.

Source Code:

def fibonacii(a,key):
    fib=[0,1,1,2,3,5,8,13]
    k=len(a)
    begin=0
    while k>0:
        k=k-1
        pos = begin+fib[k]
        if key == a[pos]:
            return pos
        elif key<a[pos]:
            continue
        else:
            begin=pos+1
            k=k-3
    return -1
a=[]
n=int(input("how many elements u want to enter"))
for i in range(n):
    a.append(int(input()))
key=int(input("enter the key"))
p=fibonacii(a,key)
if p==-1:
    print("%d not found" %key)
else:

    print("%d is found" %key)

Output:

how many elements u want to enter5

1

2

3

4

5

enter the key1

1 is found

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

how many elements u want to enter5

1

2

3

4

5

enter the key3

3 is found

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

how many elements u want to enter5

1

2

3

4

5

enter the key5

5 is found

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

how many elements u want to enter5

1

2

3

4

5

enter the key100

100 not found

>>> 

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