Quick Sort

Quick sort is a sorting algorithm that uses the divide-and-conquer strategy to sort the list of elements. The basic idea of quick sort is to partition the input list into two sub-list, one containing elements that are smaller than a chosen pivot element, and the other containing elements that are greater than or equal to the pivot. This process is repeated recursively on each sub-list until the entire list is sorted.

Algorithm:

1. Choose a pivot element from the list. This can be any element, but typically the first or last element is chosen.

2. Partition the list into two sub-list, one containing elements smaller than the pivot, and the other containing elements greater than or equal to the pivot. Steps for Partition:-

   1. Set pivot to the value of the element at the lower index of the list L.
   2. Initialize two indices i and j to lower and lower+1 respectively.
   3. Loop over the range from lower+1 to upper (inclusive) using the variable j.
   4. If the value at index j is less than or equal to the pivot value, increment i and swap the values at indices i and j in the list L.
   5. After the loop, swap the pivot value at index lower with the value at index i in the list L.
   6. Return the index i as the position of the pivot value.

3. Recursively apply steps 1 and 2 to each sub-list until the entire list is sorted.

 

Visualization

Open Visualization

Select the Quick Sort(QUI) option on top bar then run the visualization.

Source - https://visualgo.net/en/sorting

 

Implementation

def partition(L,lower,upper):
  # Select first element as a pivot 
  pivot = L[lower]
  i = lower
  for j in range(lower+1,upper+1):
    if L[j] <= pivot:
      i += 1
      L[i],L[j] = L[j],L[i]
  L[lower],L[i]= L[i],L[lower]
  # Return the position of pivot
  return i

def quicksort(L,lower,upper):
  if(lower < upper):
    pivot_pos = partition(L,lower,upper);
    # Call the quick sort on leftside part of pivot
    quicksort(L,lower,pivot_pos-1)
    # Call the quick sort on rightside part of pivot
    quicksort(L,pivot_pos+1,upper)
  return L

 

 

Code Execution Flow

 

 

Lecture Implementation

def quicksort(L,l,r): # Sort L[l:r]
    if (r - l <= 1):
        return L
    (pivot,lower,upper) = (L[l],l+1,l+1)
    for i in range(l+1,r):
        if L[i] > pivot:
            # Extend upper segment
            upper = upper+1
        else:
            # Exchange L[i] with start of upper segment
            (L[i], L[lower]) = (L[lower], L[i])
            # Shift both segments
            (lower,upper) = (lower+1,upper+1)
    # Move pivot between lower and upper
    (L[l],L[lower-1]) = (L[lower-1],L[l])
    lower = lower-1
    
    # Recursive calls
    quicksort(L,l,lower)
    quicksort(L,lower+1,upper)
    return(L)

 

 

 

 

 

 

Code Execution Flow

 

Analysis

Best Case - In each recursive call, If the selected pivot element comes at the middle position and divide the list into two equal halves.

Recurrence relation:- $T(n) = 2T(n/2)+ O(n)$

Complexity:- $n + n + n...logn~times = nlogn = O(nlogn)$

 

Worst Case - If the list is already sorted in ascending or descending order (if the selected pivot element comes at the first or last position of the list in each recursive call).

Recurrence relation:- $T(n) = T(n-1)+ O(n)$

Complexity:- $n + (n-1) + (n-2)...1 = n(n+1)/2 = O(n^2)$

 

Average Case

Complexity:- $n + n + n...logn~times = nlogn = O(nlogn)$

 

Stable - No

Sort in Place - Yes

 

Comparison of sorting algorithm

 

 

Linked List

A linked list is a data structure consisting of a sequence of nodes, where each node contains a piece of data and a reference (or pointer) to the next node in the sequence. The first node is called the head, and the last node is called the tail, and the tail node points to null. Linked lists are useful for storing and manipulating collections of data, especially when the size of the collection is not known in advance, as they can dynamically adjust in size.

There are two types of linked lists:

• Singly linked list
• Doubly linked list

Singly linked list

• head:- Store the reference of the first node. If the list is empty, then it stores None

• Each node have two fields:

  • data :- Store actual value
  • next:- Store reference of the next node

 

Representation

Doubly linked list

• head:- Store the reference of the first node. If the list is empty, then it stores None

• tail:- Store the reference of the last node. If the list is empty, then it stores None

• Each node have three fields:

  • prev:- store reference of the previous node
  • data :- Store actual value
  • next:- Store reference of the next node

 

Representation

 

Visualization of Linked List

Open Visualization

Select the Linked List(LL) or Doubly Lined List(DLL) option on top bar then run the visualization.

Source - https://visualgo.net/en/list

 

 

Implementation of singly linked list in Python

Using one class- Recursively

class Node:
    def __init__(self, v = None):
        self.value = v
        self.next = None
        return
    def isempty(self):
        if self.value == None:
            return(True)
        else:
            return(False)
    # recursive
    def append(self,v):
        # If current node is empty
        if self.isempty(): 
            self.value = v
        # If current node is last node of the list 
        elif self.next == None:
            self.next = Node(v)
        # Else raverse to next node
        else:
            self.next.append(v) 
        return
    # append, iterative
    def appendi(self,v):
        # if current node is empty 
        if self.isempty():
            self.value = v
            return
        temp = self
        # Traverse the list to find the last node
        while temp.next != None:
            temp = temp.next
        temp.next = Node(v) 
        return
    def insert(self,v):
        if self.isempty():
            self.value = v
            return
        newnode = Node(v)
        # Exchange values in self and newnode
        (self.value, newnode.value) = (newnode.value, self.value)
        # Switch links
        (self.next, newnode.next) =(newnode, self.next)
        return
    # delete, recursive
    def delete(self,v):
        # If list is empty
        if self.isempty():
            return
        # If v is the current node of the list
        if self.value == v:
            self.value = None
            if self.next != None:
                self.value = self.next.value
                self.next = self.next.next
            return
        else:
            if self.next != None:
                self.next.delete(v)
                if self.next.value == None:
                    self.next = None
        return
    def display(self):
        if self.isempty()==True:
            print('None')
        else:
            temp = self
            while temp!=None:
                print(temp.value,end="  ")
                temp = temp.next
head = Node(10)
head.append(20)
head.append(30)
head.appendi(40)
head.appendi(50)
head.delete(30)
head.display()

 

Code Execution Flow

 

 

Using two classes

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

class LinkedList:
    def __init__(self):
        self.head = None
    def isempty(self):
        if self.head == None: 
            return True
        else:
            return False
    def append(self,data):
        # If list is empty
        if self.isempty():
            self.head=Node(data)
        else:
            temp = self.head
            # Traverse the list to find the last node
            while temp.next != None:
                temp = temp.next
            temp.next = Node(data)
    def delete(self,v):
        # If list is empty
        if self.isempty() == True:
            return 'List is empty'
        # If list have only one element and equal to v
        elif self.head.next == None:
            # If v is the first node of the list
            if self.head.data == v: 
                self.head = None
            else:
                return 'Not exist'
        else:
            temp = self.head
            temp1 = self.head
            # Traverse the list to find node with v value
            while temp.next!= None and temp.data != v: 
                temp1 = temp
                temp = temp.next
            # If v is the first node of the list
            if temp.data == v and temp == self.head: 
                self.head = temp.next
            # If v is the any node of the list except the first node
            elif temp.data == v: 
                temp1.next= temp.next
            else:
                return 'Not exist'
    def display(self):
        if self.isempty()==True:
            print('None')
        else:
            temp = self.head
            while temp!=None:
                print(temp.data,end="  ")
                temp = temp.next
L = LinkedList()
L.append(30)
L.append(40)
L.append(50)
L.delete(30)
L.display()

 

Code Execution Flow

 

Advantage

• Insertion and deletion operations are easy
• Many complex applications can be easily carried out with linked list concepts like tree, graph, etc.

Disadvantage

• More memory required to store data
• Random access is not possible

Application

• Implementation stack, queue, deque
• Representation of graph.
• Representation of sparse matrix
• Manipulation of the polynomial expression

 

Stack

A Stack is a non-primitive linear data structure. It is an ordered list in which the addition of a new data item and deletion of an already existing data item can be done from only one end, known as top of the stack.

The last added element will be the first to be removed from the Stack. That is the reason why stack is also called Last In First Out (LIFO) type of data structure.

 

Basic operations on Stack

Push

The process of adding a new element to the top of the Stack is called the Push operation.

Pop

The process of deleting an existing element from the top of the Stack is called the Pop operation. It returns the deleted value.

Traverse/Display

The process of accessing or reading each element from top to bottom in Stack is called the Traverse operation.

Applications of Stack

• Reverse the string
• Evaluate Expression
• Undo/Redo Operation
• Backtracking
• Depth First Search(DFS) in Graph(Will be discussed in Week-4)

Implementation of the Stack in Python

Stack implementation using a python list

class Stack:
    def __init__(self):
        self.stack = []
    def isempty(self):
        return(self.stack == [])
    def Push(self,v):
        self.stack.append(v)
    def Pop(self):
        v = None
        if not self.isempty():
            v = self.stack.pop()
        return v    
    def __str__(self):
        return(str(self.stack))
S = Stack()
S.Push(10)
S.Push(20)
S.Push(30)
S.Push(40)
print(S.Pop())
print(S.Pop())
print(S)

 

Code Execution Flow

 

Stack implementation using a Linked list

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

class Stack:
    def __init__(self):
        self.top = None
        
    def isempty(self):
        if self.top == None: 
            return True
        else:
            return False

    def Push(self,data):
        if self.isempty():
            self.top = Node(data)
        else:
            temp = Node(data)
            temp.next = self.top
            self.top = temp

    def Pop(self):
        if self.isempty() == True:
            return None
        else:
            temp = self.top.data
            self.top = self.top.next
            return temp

    def display(self):
        if self.isempty()==True:
            return None
        else:
            temp = self.top
            while temp != None:
                print(temp.data)
                temp = temp.next		


S = Stack()
S.Push(30)
S.Push(40)
S.Push(50)
S.Push(60)
S.Push(70)
print(S.Pop())
print(S.Pop())
S.display()

 

Code Execution Flow

 

 

Queue

The Queue is a non-primitive linear data structure. It is an ordered collection of elements in which new elements are added at one end called the Back end, and the existing element is deleted from the other end called the Front end.

A Queue is logically called a First In First Out (FIFO) type of data structure.

 

Basic operations on Queue

Enqueue

The process of adding a new element at the Back end of Queue is called the Enqueue operation.

Dequeue

The process of deleting an existing element from the Front of the Queue is called the Dequeue operation. It returns the deleted value.

Traverse/Display

The process of accessing or reading each element from Front to Back of the Queue is called the Traverse operation.

Applications of Queue

• Spooling in printers
• Job Scheduling in OS
• Waiting list application
• Breadth First Search(BFS) in Graph(Will be discussed in Week-4)

Implementation of the Queue in python

Queue implementation using a python list

class Queue:
    def __init__(self):
        self.queue = []
    def isempty(self):
        return(self.queue == []) 
    def enqueue(self,v):
        self.queue.append(v)   
    def dequeue(self):
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return v    
    def __str__(self):
        return(str(self.queue))

Q = Queue()
Q.enqueue(10)
Q.enqueue(20)
Q.enqueue(30)
Q.enqueue(40)
print(Q.dequeue())
print(Q.dequeue())
print(Q)

 

Code Execution Flow

 

 

Queue implementation using a Linked list

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        
    def isempty(self):
        if self.front == None: 
            return True
        else:
            return False

    def Enqueue(self,data):
        if self.isempty():
            self.front = Node(data)
            self.rear = self.front
        else:
            temp = Node(data)
            self.rear.next = temp
            self.rear = temp

    def Dequeue(self):
        if self.isempty() == True:
            return None
        elif self.front.next == None:
            temp = self.front.data
            self.front = None
            self.rear = None            
        else:
            temp = self.front.data
            self.front = self.front.next
        return temp

    def display(self):
        if self.isempty()==True:
            print(None)
        else:
            temp = self.front
            while temp != None:
                print(temp.data)
                temp = temp.next		


Q = Queue()
Q.Enqueue(30)
Q.Enqueue(40)
Q.Enqueue(50)
Q.Enqueue(60)
Q.Enqueue(70)
print(Q.Dequeue())
print(Q.Dequeue())
print(Q.Dequeue())
print(Q.Dequeue())
print(Q.Dequeue())
print(Q.Dequeue())
Q.display()

 

Code Execution Flow

 

 

Hash mapping

Hash mapping, also known as hash table or dictionary, is a data structure that allows for efficient insertion, deletion, and retrieval of key-value pairs.

The basic idea behind hash mapping is to use a hash function to map the key to a bucket in an array. The hash function takes the key as input and returns an index of the array where the value corresponding to the key can be stored. When we want to retrieve a value, we simply use the hash function to calculate the index and then access the value stored at that index.

One of the advantages of hash mapping is its constant-time complexity for basic operations such as insertion, deletion, and retrieval, on average, making it efficient for large datasets. However, the performance can be affected by factors such as the quality of the hash function, the number of collisions (i.e., when multiple keys map to the same index), and the size of the array.

 

For storing element

For searching element

Collision

The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision.

Collision resolving technique

Open addressing(Close hashing)

• Linear probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Linear probing operates by taking the original hash index and adding successive values linearly until a free slot is found.

  An example sequence of linear probing is:

  h(k)+0, h(k)+1, h(k)+2, h(k)+3 .... h(k)+m-1

  where m is a size of hash table, and h(k) is the hash function.

  Hash function

  Let h(k) = k mod m be a hash function that maps an element k to an integer in [0, m−1], where m is the size of the table. Let the i^th probe position for a value k be given by the function

  h'(k,i) = (h(k) + i) mod m

  The value of i = 0, 1, . . ., m – 1. So we start from i = 0, and increase this until we get a free block in hash table.

   

• Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open or empty slot is found.

  An example of a sequence using quadratic probing is:

  $h, h+1, h+4, h+9...h+i^2$

  Quadratic function

  Let h(k) = k mod m be a hash function that maps an element k to an integer in [0, m−1], where m is the size of the table. Let the $i^{th}$ probe position for a value k be given by the function

  $h(k,i)= (h(k)+c_1i+c_2i^2)~mod~m$

  where c1 and c2 are positive integers. The value of i = 0, 1, . . ., m – 1. So we start from i = 0, and increase this until we get one free slot in hash table.

   

Closed addressing ( Open hashing)

• Separate chaining using linked list: Maintain the separate linked list for each possible generated index by the hash function.

  For example, if the hash function is k mod 10 where k is the key and 10 is the size of the hash table.

 

 

Visualization of Hashing

Open Visualization

Source - https://visualgo.net/en/hashtable