Python_DSA_Day2.txt

##1 HeapSOrt using heapq

from heapq import heapify, heappush, heappop

def heapSort(arr):
    heap = []
    for element in arr:
        heappush(heap, element)

    output = []
    while heap:
        output.append(heappop(heap))
    
    return output    
    
arr = [1,6,2,8,3,9,4]
print(heapSort(arr))


##2 Sort a nearly sorted (or K sorted) array
#Input : arr[] = {6, 5, 3, 2, 8, 10, 9}, k = 3 
#Output : arr[] = {2, 3, 5, 6, 8, 9, 10}

#Input : arr[] = {10, 9, 8, 7, 4, 70, 60, 50}, k = 4
#Output : arr[] = {4, 7, 8, 9, 10, 50, 60, 70}

from heapq import heapify, heappop, heappush

def sort_k(arr, n, k):
    heap = arr[:k+1]
    heapify(heap)
    
    target_index = 0
    for rem_index in range(k+1, n):    
        arr[target_index] = heappop(heap)
        heappush(heap, arr[rem_index])
        target_index += 1    
    
    while heap: 
        arr[target_index] = heappop(heap) 
        target_index += 1


# Driver Code 
k = 3
arr = [2, 6, 3, 12, 56, 8] 
n = len(arr) 
sort_k(arr, n, k) 
print(arr)


##3 Merge Sort

def merge(arr, left, mid, right):
    
    b1 = arr[left:mid+1]
    b2 = arr[mid+1:]
    
    n1 = len(b1)
    n2 = len(b2)
    
    k=left
    i = 0
    j = 0
    while i < n1 and j < n2:
        if b1[i] > b2[j]:
            arr[k] = b2[j]
            j+=1
        else:
            arr[k] = b1[i]
            i+=1
        k+=1
    
    while i<n1:
        arr[k] = b1[i]
        i+=1
        k+=1
    
    while k<n2:
        arr[k] = b2[j]
        j+=1
        k+=1
        
    return arr  
    
def mergeSort(arr, left, right):
    
    if left<right:
        mid = left+(right-left)//2
        
        mergeSort(arr, left, mid)
        mergeSort(arr, mid+1, right)
        
        merge(arr, left, mid, right)
    
    return arr    
    
#Driver COde    
arr = [1,5,2,9,6,10,7,78,6,0]
n = len(arr)-1
print(mergeSort(arr, 0, n))




##4 Sort Linked List (LEETCODE) - MergeSort

# Definition for singly-linked list.
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        
class LinkedList: 
    def __init__(self): 
        self.head = None
      
    # push new value to linked list 
    # using append method 
    def append(self, new_value): 
          
        # Allocate new node 
        new_node = Node(new_value) 
          
        # if head is None, initialize it to new node 
        if self.head is None: 
            self.head = new_node 
            return
        curr_node = self.head 
        while curr_node.next is not None: 
            curr_node = curr_node.next
              
        # Append the new node at the end 
        # of the linked list 
        curr_node.next = new_node 

    # Merge Sort Starts here
    '''
    4->2->1->3
    
    1->2->3->4
    
    merge sort - recursive
    
    1. find the middle linkedlist 
    2. divide it into 2 linkedlist and sort each 
    3. merge the linkedlist in the right order 
    
    base case:
        if not head or not head.next -> head
        
    reducing the input size 
       reducing by half (dividing the linkedlist into 2)
       using a slow and a fast pointers
       
              4     ->    2     ->    1       ->      3    -> 8
                                     ^
                                   slow 
                                                              ^
                                                           fast    
                        ^
                       pre
                          
                    prev.next = None 
                    
                    first half: head to prev
                    second half: slow to fast 
            
       1 -> 4 -> 3
                   ^
       
       3 -> 5 -> 8 
            ^
       
       --
    0 ->  1 -> 3 -> 4 -> 3 -> 5 -> 8 
                                   ^
     Time complexity: O(n log n)
     Space complexity: O(log n)
    '''
    def sortList(self, head):
        def merge(left, right):
            dummy = Node(0)
            curr = dummy 
            while left and right:
                if left.val < right.val:
                    curr.next = left
                    left = left.next
                else:
                    curr.next = right
                    right = right.next
                curr = curr.next
                    
            curr.next = left or right 
            
            return dummy.next
        
        if not head or not head.next:
            return head
        
        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre, slow, fast = slow, slow.next, fast.next.next
            
        pre.next = None 
        left = self.sortList(head)
        right = self.sortList(slow)
        
        return merge(left, right)

# Function to print
def printList(head): 
    if head is None: 
        print(' ') 
        return
    curr_node = head 
    while curr_node: 
        print(curr_node.val, end = " ") 
        curr_node = curr_node.next
    print(' ') 

# Driver Code    
li = LinkedList()
li.append(15)
li.append(25)
li.append(30)
li.append(10)
li.append(5)
li.append(20)
li.append(3)
li.append(2)
li.head = li.sortList(li.head)
print ("Sorted Linked List is:") 
printList(li.head)