MODULE 5
Bubble Sort Algorithm
• Bubble Sort is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in
the wrong order.
• This algorithm is not suitable for large data sets as its
average and worst-case time complexity are quite high.
• We sort the array using multiple passes. After the first pass, the
maximum element goes to end (its correct position). Same way,
after second pass, the second largest element goes to second
last position and so on.
• In every pass, we process only those elements that have already
not moved to correct position. After k passes, the largest k
elements must have been moved to the last k positions.
• In a pass, we consider remaining elements and compare all
adjacent and swap if larger element is before a smaller element.
If we keep doing this, we get the largest (among the remaining
elements) at its correct position.
• Complexity Analysis of Bubble Sort:
• Time Complexity: O(n2)
• Auxiliary Space: O(1)
• Advantages of Bubble Sort:
• Bubble sort is easy to understand and implement.
• It does not require any additional memory space.
• It is a stable sorting algorithm, meaning that elements with the same key value maintain
their relative order in the sorted output.
• Disadvantages of Bubble Sort:
• Bubble sort has a time complexity of O(n2) which makes it very slow for large data sets.
• Bubble sort has almost no or limited real world applications. It is mostly used in
academics to teach different ways of sorting.
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.
• First we find the smallest element and swap it with the first element. This
way we get the smallest element at its correct position.
• Then we find the smallest among remaining elements (or second
smallest) and swap it with the second element.
• We keep doing this until we get all elements moved to correct position.
• Complexity Analysis of Selection Sort
• Time Complexity: O(n2) ,as there are two nested loops:
• One loop to select an element of Array one by one = O(n)
• Another loop to compare that element with every other
Array element = O(n)
• Therefore overall complexity = O(n) * O(n) = O(n*n) =
O(n2)
• Advantages of Selection Sort
• Easy to understand and implement, making it ideal for teaching basic sorting
concepts.
• Requires only a constant O(1) extra memory space.
• It requires less number of swaps (or memory writes) compared to many other
standard algorithms. Only cycle sort beats it in terms of memory writes.
Therefore it can be simple algorithm choice when memory writes are costly.
• Disadvantages of the Selection Sort
• Selection sort has a time complexity of O(n^2) makes it slower compared to
algorithms like Quick Sort or Merge Sort.
• Does not maintain the relative order of equal elements which means it is not
stable.
Applications of Selection Sort
• Perfect for teaching fundamental sorting mechanisms and
algorithm design.
• Suitable for small lists where the overhead of more
complex algorithms isn't justified and memory writing is
costly as it requires less memory writes compared to
other standard sorting algorithms.
• Heap Sort algorithm is based on Selection Sort.
Insertion Sort Algorithm
• 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. It is like sorting playing cards in your hands. You split the cards into
two groups: the sorted cards and the unsorted cards. Then, you pick a card
from the unsorted group and put it in the right place in the sorted group.
• We start with the second element of the array as the first element is assumed
to be sorted.
• Compare the second element with the first element if the second element is
smaller then swap them.
• Move to the third element, compare it with the first two elements, and put it in
its correct position
• Repeat until the entire array is sorted.
• Time Complexity
• Best case: O(n), If the list is already sorted, where n is the number of
elements in the list.
• Average case: O(n2), If the list is randomly ordered
• Worst case: O(n2), If the list is in reverse order
• Space Complexity
• Auxiliary Space: O(1), Insertion sort requires O(1) additional space, making it
a space-efficient sorting algorithm.
• Advantages
• Simple and easy to implement.
• Stable sorting algorithm.
• Efficient for small lists and nearly sorted lists.
• Space-efficient as it is an in-place algorithm.
• Adoptive. the number of inversions is directly proportional to number of
swaps. For example, no swapping happens for a sorted array and it takes
O(n) time only.
• Disadvantages
• Inefficient for large lists.
• Not as efficient as other sorting algorithms (e.g., merge sort, quick sort) for
most cases.
Applications of Insertion Sort
• The list is small or nearly sorted.
• Simplicity and stability are important.
• Used as a subroutine in Bucket Sort
• Can be useful when array is already almost sorted (very few inversions)
• Since Insertion sort is suitable for small sized arrays, it is used in Hybrid
Sorting algorithms along with other efficient algorithms like Quick Sort and
Merge Sort. When the subarray size becomes small, we switch to insertion
sort in these recursive algorithms. For example IntroSort and TimSort use
insertions sort.
Linear Search
• In Linear Search, we iterate over all the elements of the array and check if it
the current element is equal to the target element.
• If we find any element to be equal to the target element, then return the index
of the current element.
• Otherwise, if no element is equal to the target element, then return -1 as the
element is not found.
• Linear search is also known as sequential search.
Applications of Linear Search Algorithm:
• Unsorted Lists: When we have an unsorted array or list, linear search is most
commonly used to find any element in the collection.
• Small Data Sets: Linear Search is preferred over binary search when we
have small data sets with
• Searching Linked Lists: In linked list implementations, linear search is
commonly used to find elements within the list. Each node is checked
sequentially until the desired element is found.
• Simple Implementation: Linear Search is much easier to understand and
implement as compared to Binary Search or Ternary Search.
Advantages of Linear Search Algorithm:
• Linear search can be used irrespective of whether the array is sorted or not.
It can be used on arrays of any data type.
• Does not require any additional memory.
• It is a well-suited algorithm for small datasets.
Disadvantages of Linear Search Algorithm:
• Linear search has a time complexity of O(N), which in turn makes it slow for
large datasets.
• Not suitable for large arrays.
Time and Space Complexity of Linear Search Algorithm:
• Time Complexity:
• Best Case: In the best case, the key might be present at the first index. So
the best case complexity is O(1)
• Worst Case: In the worst case, the key might be present at the last index i.e.,
opposite to the end from which the search has started in the list. So the
worst-case complexity is O(N) where N is the size of the list.
• Average Case: O(N)
Binary Search (Recursive and Iterative)
• Binary Search Algorithm is a searching algorithm used in a sorted array by
repeatedly dividing the search interval in half.
• The idea of binary search is to use the information that the array is sorted
and reduce the time complexity to O(log N).
• Step-by-step algorithm for Binary Search:
• Divide the search space into two halves by finding the middle index “mid”.
• Compare the middle element of the search space with the key.
• If the key is found at middle element, the process is terminated.
• If the key is not found at middle element, choose which half will be used as
the next search space.
• If the key is smaller than the middle element, then the left side is used for
next search.
• If the key is larger than the middle element, then the right side is used for
next search.
• This process is continued until the key is found or the total search space is
exhausted.
• Complexity Analysis of Binary Search Algorithm
• Time Complexity:
• -> Best Case: O(1)
• -> Average Case: O(log N)
• -> Worst Case: O(log N)
• Auxiliary Space: O(1), If the recursive call stack is
considered then the auxiliary space will be O(log N).
Applications of Binary Search Algorithm
• Searching in sorted arrays
• Finding first/last occurrence or closest match in a sorted array
• Database indexing — Used in B-trees and similar structures for fast data lookup.
• Debugging in version control — Tools like git bisect use binary search to isolate faulty
commits.
• Network routing & IP lookup — Efficiently find routing entries in tables sorted by address
ranges.
• File systems & libraries — Fast search through sorted directories or symbol tables.
• Gaming/graphics — Collision detection or ray tracing using sorted spatial data.
• Machine learning tuning — Efficient hyperparameter search (e.g., learning rate, thresholds).
• Optimization problems & competitive programming — Solve boundary-value challenges by
narrowing search space.
• Advanced data structures — Binary search trees, self-balancing BSTs, and fractional
cascading rely on search logic.
What is Hashing?
• Hashing refers to the process of generating a fixed-size output from an input
of variable size using the mathematical formulas known as hash functions.
• This technique determines an index or location for the storage of an item
in a data structure.
• It might not be strictly related to key-value pairs only if you are manipulating
the data say for some encryption or changing it to a form that will be less
complex to handle with, then its also hashing
What is Hash Table?
• The implementation of a Hash table is the most popular use for hashing.
• This is a container that store the key-value pairs.
• Hash Tables use Hashing to generate a short Integer value out of the key
and maps it with a value.
Some Important concepts regarding Hash Table:
• Initial Capacity: In a Hash Table, it constructs a new empty hashtable with a
default initial capacity of 11.
• Load Factor: Load factor is defined as the ratio of the preferred number of
entries that can be inserted in the Hash table before a size increment is
required (a) to the total size of the hash table (b) i.e., load factor is (a/b).
• Collision: A collision occurs when two keys are hashed to the same index in a
hash table. Collisions are a problem because every slot in a hash table is
supposed to store a single element. When Collision occurs it creates a
chaining like a linked list and stores the keys.
Difference between Hash Table and Hashing:
Hashing Hash Table
Hashing is the process of transforming any given key or a
1 Hash Table is a container to store the key-value pairs.
string of characters into another value.
Hash table, HashMap, multimap, unordered_map, set etc uses
2 Hashing is a built-in method. It can be defined by users also.
hashing to store data.
Hashing is used to generate a hashcode which is of type
3 Based on our needs we can use any type of hash table.
Integer.
Hash Table generally works as a lookup table to check the
Hashing uses the same process for every key to generate
4 keys we already came across and update or change the values
hashcodes.
being mapped with them or insert a new key in the table.
Collision Resolution Techniques
• In Hashing, hash functions were used to generate hash values.
• The hash value is used to create an index for the keys in the hash table.
• The hash function may return the same hash value for two or more keys.
• When two or more keys have the same hash value, a collision happens.
• To handle this collision, we use Collision Resolution Techniques.
Collision Resolution Techniques
• There are mainly two methods to handle collision:
• Separate Chaining
• Open Addressing
1) Separate Chaining
• The idea behind Separate Chaining is to make each cell of the hash table
point to a linked list of records that have the same hash function value.
• Chaining is simple but requires additional memory outside the table.
• Example: We have given a hash function and we have to insert some
elements in the hash table using a separate chaining method for collision
resolution technique.
• Hash function = key % 5,
• Elements = 12, 15, 22, 25 and 37.
2) Open Addressing
• In open addressing, all elements are stored in the hash table itself. Each
table entry contains either a record or NIL.
• When searching for an element, we examine the table slots one by one until
the desired element is found or it is clear that the element is not in the table.
• 2.a) Linear Probing
• In linear probing, the hash table is searched sequentially that starts from the
original location of the hash.
• If in case the location that we get is already occupied, then we check for the
next location.
• Algorithm:
• Calculate the hash key. i.e. key = data % size
• Check, if hashTable[key] is empty
• store the value directly by hashTable[key] = data
• If the hash index already has some value then
• check for next index using key = (key+1) % size
• Check, if the next index is available hashTable[key] then store the value.
Otherwise try for next index.
• Do the above process till we find the space.
• Example: Let us consider a simple hash function as “key mod 5” and a
sequence of keys that are to be inserted are 50, 70, 76, 85, 93.
• 2.b) Quadratic Probing
• 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 slot is found.
• An example sequence using quadratic probing is:
• H + 1 ^2 , H + 2^ 2 , H + 3^ 2 , H + 4 ^2 ...................... H + k^ 2
• This method is also known as the mid-square method because in this method we look for
i^2-th probe (slot) in i-th iteration and the value of i = 0, 1, . . . n – 1.
• We always start from the original hash location.
• If only the location is occupied then we check the other slots.
• Let hash(x) be the slot index computed using the hash function and n be the size of the hash
table.
• If the slot hash(x) % n is full, then we try (hash(x) + 1 ^2 ) % n.
• If (hash(x) + 1 ^2 ) % n is also full, then we try (hash(x) + 2^ 2 ) % n.
• If (hash(x) + 2 ^2 ) % n is also full, then we try (hash(x) + 3^ 2 ) % n.
• This process will be repeated for all the values of i until an empty slot is found
• Example: Let us consider table Size = 7, hash function as Hash(x) = x % 7 and collision
resolution strategy to be f(i) = i ^2 . Insert = 22, 30, and 50
• 2.c) Double Hashing
• Double hashing is a collision resolving technique in Open Addressed Hash
tables.
• Double hashing make use of two hash function,
• The first hash function is h1(k) which takes the key and gives out a location
on the hash table. But if the new location is not occupied or empty then we
can easily place our key.
• But in case the location is occupied (collision) we will use secondary hash-
function h2(k) in combination with the first hash-function h1(k) to find the new
location on the hash table.
• This combination of hash functions is of the form
• h(k, i) = (h1(k) + i * h2(k)) % n
• where
• i is a non-negative integer that indicates a collision number,
• k = element/key which is being hashed
• n = hash table size.
• Complexity of the Double hashing algorithm:
• Time complexity: O(n)
• Example: Insert the keys 27, 43, 692, 72 into the Hash Table of size 7.
• where first hash-function is h1(k) = k mod 7 and second hash-function is
h2(k) = 1 + (k mod 5)
27%7
• Note:
• Linear Probing: If there is a collision at i then we use the hash function - H(k, i ) = [H'(k) + i ] % m
• where, i is the index, m is the size of hash table H( k, i ) and H'( k ) are hash functions.
• Quadratic Probing: If there is a collision at i then we use the hash function - H(k, i ) = [H'(k) + c1 * i +
c2 * i2 ] % m
• where, i is the index, m is the size of hash table H(k, i ) and H'( k ) are hash functions, c1 and c2 are
constants.
• Double Hashing: If there is a collision at i then we use the hash function - H(k, i ) = [H1(k, i) + i * H2(k) ]
%m
• where, i is the index, m is the size of hash table H(k, i ), H1( k) = k % m and H2(k) = k % m' are hash
functions.
Applications of Hash:
• Hash is used in databases for indexing.
• Hash is used in disk based data structures.
• In some programming languages like Python, JavaScript hash is used to
implement objects.
• Hash tables are commonly used to implement caching systems
• Used in various cryptographic algorithms.
• Hash tables are used in load balancing algorithms
• Hash provides better synchronization than other data structures.
• Hash tables are more efficient than search trees or other data structures.
• Hash provides constant time for searching, insertion and deletion
operations on average.
• Hash tables are space-efficient.
• Most Hash table implementation can automatically resize itself.
• Hash tables are easy to use.
• Hash tables offer a high-speed data retrieval and manipulation.
• Databases: Hashes are commonly used in databases to store and retrieve records quickly.
• Caches: Hashes are used in caches to quickly look up frequently accessed data. A cache might use a hash to store
recently accessed data, with the keys being the data itself and the values being the time it was accessed or other
metadata.
• Symbol tables: Hashes are used in symbol tables to store key-value pairs representing identifiers and their
corresponding attributes.
• Cryptography: Hashes are used in cryptography to create digital signatures, verify the integrity of data, and store
passwords securely. Hash functions are designed such that it is difficult to reconstruct the original data from the
hash, making them useful for verifying the authenticity of data.
• Distributed systems: Hashes are used in distributed systems to assign work to different nodes or servers. For
example, a load balancer might use a hash to distribute incoming requests to different servers based on the request
URL or other criteria.
• File systems: Hashes are used in file systems to quickly locate files or data blocks. For example, a file system might
use a hash to store the locations of files on a disk, with the keys being the file names and the values being the disk
locations.
Disadvantages of Hash:
•Hash is inefficient when there are many collisions.
•Hash collisions are practically not be avoided for large set of possible keys.
•Hash does not allow null values.
•Hash tables have a limited capacity and will eventually fill up.
•Hash tables can be complex to implement.
•Hash tables do not maintain the order of elements, which makes it difficult
to retrieve elements in a specific order.