Selection Sort:
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly
selecting the smallest (or largest) element from the unsorted portion and swapping it
with the first unsorted element. This process continues until the entire array is sorted.
Steps:
1. First we find the smallest element and swap it with the first element. This way
we get the smallest element at its correct position.
2. Then we find the smallest among remaining elements (or second smallest) and
move it to its correct position by swapping.
3. We keep doing this until we get all elements moved to correct position.
How does Selection Sort work?
Time Complexity and Space Complexity:
Selection Sort is an in-place sorting algorithm, meaning it does not require extra space for
another data structure.
Space Complexity: O(1)
Algorithm:
Insertion Sort:
Insertion sort is a simple sorting algorithm that works by iteratively inserting each
element of an unsorted list into its correct position in a sorted portion of the list.
Steps:
We start with second element of the array as first element in the array is
assumed to be sorted.
Compare second element with the first element and check if the second
element is smaller then swap them.
Move to the third element and compare it with the first two elements and put at
its correct position
Repeat until the entire array is sorted.
How does Selection Sort work?
Time Complexity:
1. Best Case (Array is already sorted):
• Agar array already sorted hai, to har element apni sahi jagah par hoga.
• Algorithm har iteration mein sirf ek comparison karega aur koi swapping nahi
hogi.
Time Complexity: O(n)
2. Worst Case (Array is reverse sorted):
• Agar array reverse sorted hai, to har naya element sorted part ke sabhi
elements ke saath compare hoga aur end mein insert hoga.
Time Complexity: O(n²)
3. Average Case (Random order):
Time Complexity: O(n²)
Space Complexity: O(1)
Algorithm:
Merge Sort:
Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It
works by recursively dividing the input array into smaller subarrays and sorting those
subarrays then merging them back together to obtain the sorted array.
Steps:
Here’s a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively into two halves until it can no more be
divided.
2. Conquer: Each subarray is sorted individually using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted order. The
process continues until all elements from both subarrays have been merged.
How does Merge Sort work?
Time Complexity:
Merge sort does not check if the array is already sorted, the algorithm will still divide
and merge the array
➢ Best Case: O(n log n)
➢ Worst Case: O(n log n)
➢ Average Case: O(n log n)
Space Complexity: O( n ) (kyunki additional arrays use hote hain)
Algorithm:
---------------------------------------------------------------------------------
Quick Sort:
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an
element as a pivot and partitions the given array around the picked pivot by placing the
pivot in its correct position in the sorted array.
Steps:
There are mainly three steps in the algorithm:
1. Choose a Pivot: Select an element from the array as the pivot. The choice of
pivot can vary (e.g., first element, last element, random element, or median).
2. Partition the Array: Rearrange the array around the pivot. After partitioning, all
elements smaller than the pivot will be on its left, and all elements greater than
the pivot will be on its right. The pivot is then in its correct position, and we
obtain the index of the pivot.
3. Recursively Call: Recursively apply the same process to the two partitioned
sub-arrays (left and right of the pivot).
4. Base Case: The recursion stops when there is only one element left in the sub-
array, as a single element is already sorted.
How does QuickSort Algorithm work?
Time Complexity:
1. Best Case: O(n log n)
When the array is divided into two roughly equal parts at each step (ideal partitioning).
2. Average Case: O(n log n)
• In most cases, where the partitions are balanced or somewhat imbalanced, the
time complexity remains O(n log n).
3. Worst Case: O(n^2)
• Happens when the array is already sorted (either ascending or descending) and
the pivot chosen is always the smallest or largest element.
Algorithm:
Heap Sort:
Heap sort is a comparison-based sorting technique based on Binary Heap Data
Structure. We use Binary Heap so that we can quickly find and move the max element
in O(Log n) instead of O(n) and hence achieve the O(n Log n) time complexity.
Steps:
First convert the array into a max heap using heapify, Please note that this happens in-
place. The array elements are re-arranged to follow heap properties. Then one by one
delete the root node of the Max-heap and replace it with the last node and heapify.
Repeat this process while size of heap is greater than 1.
• Rearrange array elements so that they form a Max Heap.
• Repeat the following steps until the heap contains only one element:
o Swap the root element of the heap (which is the largest element in
current heap) with the last element of the heap.
o Remove the last element of the heap (which is now in the correct
position). We mainly reduce heap size and do not remove element from
the actual array.
o Heapify the remaining elements of the heap.
• Finally we get sorted array.
Detailed Working of Heap Sort
Time Complexity:
Building the Max-Heap: O( n )
Heap Sort Process: O( log n )
Overall Time Complexity:
• Best Case: O(n log n )
• Average Case: O(n log n )
• Worst Case: O(n log n )
Space Complexity:
Heap Sort does not use additional data structures for sorting.
Space Complexity: O( 1 )
Algorithm:
-------------------------------------------------------------
Binary Search Tree:
A Binary Search Tree (or BST) is a data structure used in computer science for
organizing and storing data in a sorted manner. Each node in a Binary Search Tree has
at most two children, a left child and a right child, with the left child containing values
less than the parent node and the right child containing values greater than the parent
node. This hierarchical structure allows for efficient searching, insertion,
and deletion operations on the data stored in the tree.
Insertion in Binary Search Tree (BST):
A new key is always inserted at the leaf by maintaining the property of the binary
search tree. We start searching for a key from the root until we hit a leaf node. Once a
leaf node is found, the new node is added as a child of the leaf node. The below steps
are followed while we try to insert a node into a binary search tree:
• Initilize the current node (say, currNode or node) with root node
• Compare the key with the current node.
• Move left if the key is less than or equal to the current node value.
• Move right if the key is greater than current node value.
• Repeat steps 2 and 3 until you reach a leaf node.
• Attach the new key as a left or right child based on the comparison with the leaf
node’s value.
Time Complexity:
Best Case (Balanced BST): If the tree is balanced, we only need to traverse the height
of the tree to find the correct insertion point.
Time complexity is O( log n ).
Worst Case (Unbalanced BST): If the tree is unbalanced, we may have to traverse all
nodes to find the correct position.
Time complexity is O( n ).
Space Complexity:
Algorithm:
Deletion in Binary Search Tree (BST)
Time Complexity:
Algorithm:
AVL Tree:
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference
between heights of left and right subtrees for any node cannot be more than one.
Rotating the subtrees in an AVL Tree:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree gets out of
balance, we do a single left rotation.
Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get out of
balance, we do a single right rotation.
Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place after that
right rotation executes.
Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place after that
left rotation executes.
Steps to follow for insertion:
Let the newly inserted node be w
• Perform standard BST insert for w.
• Starting from w, travel up and find the first unbalanced node. Let z be the first
unbalanced node, y be the child of z that comes on the path from w to z and x be
the grandchild of z that comes on the path from w to z.
• Re-balance the tree by performing appropriate rotations on the subtree rooted
with z. There can be 4 possible cases that need to be handled as x, y and z can
be arranged in 4 ways.
• Following are the possible 4 arrangements:
o y is the left child of z and x is the left child of y (Left Left Case)
o y is the left child of z and x is the right child of y (Left Right Case)
o y is the right child of z and x is the right child of y (Right Right Case)
o y is the right child of z and x is the left child of y (Right Left Case)
Time Complexity: O(log(n)), For Insertion
Auxiliary Space: O(Log n) for recursion call stack as we have written a recursive
method to insert.
Deletion in an AVL Tree
Steps to follow for deletion.
To make sure that the given tree remains AVL after every deletion, we must augment
the standard BST delete operation to perform some re-balancing. Following are two
basic operations that can be performed to re-balance a BST without violating the BST
property (keys(left) < key(root) < keys(right)).
1. Left Rotation
2. Right Rotation
Time complexity of AVL delete is O(log n).
Auxiliary Space: O(log n) for recursion call stack as we have written a recursive
method to delete
Methods Of Selection Sort:
Methods Of Insertion Sort:
Methods of Merge Sort:
Methods of Quick Sort:
Methods of Heap Sort: