Ask a question from expert

Ask now

Python code for Merge Sort, Doubly Linked List and Binary Tree

9 Pages1107 Words290 Views
   

Added on  2019-10-18

About This Document

The code includes implementation of Merge Sort, Doubly Linked List and Binary Tree in Python. Merge Sort is used to sort the given array. Doubly Linked List is used to insert and remove elements from the list. Binary Tree is used to find the minimum value in the tree.

Python code for Merge Sort, Doubly Linked List and Binary Tree

   Added on 2019-10-18

BookmarkShareRelated Documents
arr= [1, 12,100, 9, 5,7,6,8]crr= [3, 7, 15, 19, 20]brr= [2, 12, 15, 20, 45]drr= [2,5,8,10,16,77]err= [1, 3,14, 19, 45, 66]# making merge functiondef merge(a, b, m, n):c=[]i=0j=0#print("Sorting:")#print(a)#print(b)#print(m)#print(n)#print("while loop")while(i<m and j<n):#print(i)#print(a)#print(j)#print(b)if(a[i]<b[j]):c.append(a[i])i+=1else :c.append(b[j])
Python code for Merge Sort, Doubly Linked List and Binary Tree_1
j+=1if (i>(m-1)):for x in range(j, len(b)):c.append(b[x])if (j>(n-1)):for x in range(i, len(a)):c.append(a[x])#print("Return sorted: " ,c)return c#print (merge(brr, crr, len(brr), len(crr)) )#print (merge(drr, err, len(drr), len(err)) )def mergeSort(a, st, lt):mid = int((st+lt)/2)#print(st,lt,mid)if (st ==mid):return aelse :left= a[st:mid]right= a[mid:lt]return merge(mergeSort(left, 0, len(left)), mergeSort(right, 0, len(right)), len(left), len(right))print(mergeSort(arr, 0, len(arr)))
Python code for Merge Sort, Doubly Linked List and Binary Tree_2
class Node(object): def __init__(self, value): self.value=value self.next=None self.prev=Noneclass List(object): def __init__(self): self.head=None self.tail=None def insert(self,n,x): #Not actually perfect: how do we prepend to an existing list? if n!=None: x.next=n.next n.next=x x.prev=n if x.next!=None: x.next.prev=x if self.head==None: self.head=self.tail=x x.prev=x.next=None elif self.tail==n: self.tail=x def remove(self, val): """Remove a node from the list.""" current = self.head
Python code for Merge Sort, Doubly Linked List and Binary Tree_3

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
SEO Suggestions for Desklib
|7
|1158
|304