Reverse Doubly Linked List

Source Code

class Node:
   def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

class Dll:
    def __init__(self):
        self.start = None

    def createlist(self):
         n=int(input("enter no of nodes"))
         for i in range(n):
            data = int(input("enter value"))
            newnode = Node(data)
            if self.start == None:
               self.start = newnode
            else:
               temp=self.start
               while temp.right != None:
                 temp=temp.right
               temp.right=newnode
               newnode.left=temp     

    def count(self):
        nc=0
        temp=self.start
        while temp!=None:
           nc=nc+1
           temp=temp.right
        print("number of nodes till now:%d" %nc)
        return nc               

    def display(self):
      print("elements in double linked list are:")
      if self.start == None:
            print("empty")
      else:
         temp=self.start
         while temp!= None:
            print("%d" %(temp.data))
            temp=temp.right
    def rev(self):     
        current = self.start       
        while current!=None:
            temp = current.left 
            current.left = current.right
            current.right = temp
            current = current.left       
        if temp!=None:
            self.start = temp.left
        print("Reverse done")

def menu():
    print("1.createlist\n2.count\n3.display\n4.reverse\n5.exit\n")   
def stop():
    print("you are about to terminate the program")
    exit(0)   
s=Dll()
def default():
    print("check your input")
menu()
while True:
    menu= {
    1: s.createlist,   
    2: s.count,
    3: s.display,
    4: s.rev,
    5:stop}
    option = int(input("Please enter your choice"))
    menu.get(option,default)()

output:

1.createlist

2.count

3.display

4.reverse

5.exit

Please enter your choice1

enter no of nodes3

enter value1

enter value2

enter value3

Please enter your choice2

number of nodes till now:3

Please enter your choice3

elements in double linked list are:

1

2

3

Please enter your choice4

Reverse done

Please enter your choice3

elements in double linked list are:

3

2

1

Please enter your choice5

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]
>>>