MODULE 2

Searching: Linear Search and Binary search.

Sorting: Bubble Sort, Selection Sort, Insertion Sort. Quicksort and Merge Sort (Recursive
Algorithms only) Complexity analysis of sorting algorithms (Detailed analysis is not
required) and Heap sort.
Hash Tables: Different Hash Functions: Division method, Multiplication Method, Mid Square
Method, Folding Method, Collision Resolution Techniques: Closed Hashing (Linear Probing)
-Drawbacks, Open Hashing (Separate Chaining). Remedies-Random Probing, Quadratic
Probing, Double Hashing. Load Factor and Re-hashing

SEARCHING

LINEAR SEARCH AND BINARY SEARCH

1.​ Linear search: Small & unsorted arrays

2.​ Binary search : Large arrays & sorted arrays
1.​ Linear Search
●​ It means looking at each element of the array, in turn, until you find the target
value.
Algorithm
 ●​ In the best case, the target value is in the first element of the array. So the search
takes some tiny, and constant, amount of time. Computer scientists denote this
O(1) In real life, we don’t care about the best case, because it so rarely actually
happens.
●​ In the worst case, the target value is in the last element of the array. So the search
takes an amount of time proportional to the length of the array. Computer
scientists denote this O(n)
●​ In the average case, the target value is somewhere in the array. So on average, the
target value will be in the middle of the array. So the search takes an amount of
time proportional to half the length of the array – also proportional to the length of
the array – O(n) again

2. Binary Search

The operation is performed on small list , and the list must be a sorted one.

• First we find the mid value of sorted list

mid value = (L+U)/2

• Let x is the searching element. If x < mid value, we consider only the left portion of the
list and we next consider that list. Then find the mid value of that list.

• Here , each time complexity can be reduced and list is contracted.

• If the searching element is less than the mid value, we consider lower bound only,
otherwise upper bound.

• The best case is O(1), because the searching element may be the mid value.

• The total list is reduced when divide each time. That is search space is reduced.

1st bisect = n/2

2nd bisect n/2² ……

𝑖 bisection, search space = n/2^i

Finally the search space become 1

• If n/2^i =1, then I = O(𝐥𝐨𝐠𝟐 𝒏)

• This is the worst and average time complexity .

• Binary searching is efficient than linear searching

●​ The general term for a smart search through sorted data is a binary search.

1.​ The initial search region is the whole array.

2.​ Look at the data value in the middle of the search region.
3.​ If you’ve found your target, stop.
4.​ If your target is less than the middle data value, the new search region is the
lower half of the data.
5.​ If your target is greater than the middle data value, the new search region is
the higher half of the data.
6.​ Continue from Step 2.
Algorithm
●​ Binary search reduces the work by half at each comparison
 SORTING

Sorting is a technique to rearrange the elements of a list in ascending or descending

order. Sorting can be classified in two types;

Internal Sorts:-
 This method uses only the primary memory during sorting process. All data items are
held in main memory and no secondary memory is required this sorting process. If all
the data that is to be sorted can be accommodated at a time in memory is called
internal sorting. There is a limitation for internal sorts; they can only process
relatively small lists due to memory constraints.

External Sorting

External Sorting is when all the data that needs to be sorted need not to be placed in
memory at a time, the sorting is called external sorting. External Sorting is used for
the massive amount of data. For example Merge sort can be used in external sorting as
the whole array does not have to be present all the time in memory,

BUBBLE SORT

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.
 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.

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 swap it with the second element.

3.​ We keep doing this until we get all elements moved to correct

position.
Time Complexity: O(n2) ,as there are two nested loops:(Same for best,

worst and average)

 ●​ 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)

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. 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.

Complexity Analysis of Insertion Sort

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

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.

It works on the principle of divide and conquer, breaking down the

problem into smaller sub-problems.

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.

Complexity Analysis of Quick Sort
Time Complexity:
 ●​ Best Case: (Ω(n log n)), Occurs when the pivot element divides

the array into two equal halves.

●​ Average Case (θ(n log n)), On average, the pivot divides the array

into two parts, but not necessarily equal.

●​ Worst Case: (O(n²)), Occurs when the smallest or largest

element is always chosen as the pivot (e.g., sorted arrays).

MERGE SORT

Merge sort is a popular sorting algorithm known for its efficiency and

stability. It follows the divide-and-conquer approach. It works by

recursively dividing the input array into two halves, recursively sorting the

two halves and finally merging them back together to obtain the sorted

array.

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.

Complexity Analysis of Merge Sort

●​ Time Complexity:
 ○​ Best Case: O(n log n), When the array is already sorted or

nearly sorted.

○​ Average Case: O(n log n), When the array is randomly

ordered.

○​ Worst Case: O(n log n), When the array is sorted in reverse

order.

HEAP SORT

Heap sort is a comparison-based sorting technique based on Binary Heap

Data Structure. It can be seen as an optimization over selection sort where

we first find the max (or min) element and swap it with the last (or first).

We repeat the same process for the remaining elements.

Heap Sort Algorithm

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:
 ○​ Swap the root element of the heap (which is the

largest element in current heap) with the last

element of the heap.

○​ 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.

○​ Heapify the remaining elements of the heap.

●​ Finally we get sorted array.

Detailed Working of Heap Sort

Step 1: Treat the Array as a Complete Binary Tree

We first need to visualize the array as a complete binary tree. For an array

of size n, the root is at index 0, the left child of an element at index i is at 2i

+ 1, and the right child is at 2i + 2.

Step 2: Build a Max Heap
Step 3: Sort the array by placing largest element at end of
unsorted array.
Complexity Analysis of Heap Sort
Time Complexity: O(n log n) (Same for best, worst and average)

What is Hash Table?

A Hash table is defined as a data structure used to insert, look up, and
remove key-value pairs quickly. It operates on the hashing concept, where
each key is translated by a hash function into a distinct index in an array.
The index functions as a storage location for the matching value. In simple
words, it maps the keys with the value.

What is Load factor?

A hash table's load factor is determined by how many elements are kept
there in relation to how big the table is. The table may be cluttered and
have longer search times and collisions if the load factor is high. An ideal
load factor can be maintained with the use of a good hash function and
proper table resizing.

What is a Hash function?

A Function that translates keys to array indices is known as a hash
function. The keys should be evenly distributed across the array via a
decent hash function to reduce collisions and ensure quick lookup speeds.

Choosing a hash function:

Selecting a decent hash function is based on the properties of the keys

and the intended functionality of the hash table. Using a function that
evenly distributes the keys and reduces collisions is crucial.

Criteria based on which a hash function is chosen:

●​ To ensure that the number of collisions is kept to a minimum, a

good hash function should distribute the keys throughout the

hash table in a uniform manner. This implies that for all pairings

of keys, the likelihood of two keys hashing to the same position in

the table should be rather constant.

●​ To enable speedy hashing and key retrieval, the hash function

should be computationally efficient.

●​ It ought to be challenging to deduce the key from its hash value.

As a result, attempts to guess the key using the hash value are

less likely to succeed.

●​ A hash function should be flexible enough to adjust as the data

being hashed changes. For instance, the hash function needs to

continue to perform properly if the keys being hashed change in

size or format.

Types of Hash Functions

There are many hash functions that use numeric or alphanumeric keys.

1.​ Division Method.

2.​ Multiplication Method

3.​ Mid-Square Method

4.​ Folding Method

1. Division Method
The division method involves dividing the key by a prime number and

using the remainder as the hash value.

h(k)=k mod m

k is the key value, and m is the size of the hash table.

It is best suited that M is a prime number as that can make sure the keys

are more uniformly distributed. The hash function is dependent upon the

remainder of a division.
Example:

k = 12345​
M = 95​
h(12345) = 12345 mod 95 ​
= 90

k = 1276​
M = 11​
h(1276) = 1276 mod 11 ​
=0
2. Mid Square Method:

The mid-square method is a very good hashing method. It involves two

steps to compute the hash value-

1.​ Square the value of the key k i.e. k2

2.​ Extract the middle r digits as the hash value.

Formula:

h(K) = h(k x k)

Here,​
k is the key value.

The value of r can be decided based on the size of the table.

Example:
Suppose the hash table has 100 memory locations. So r = 2 because two

digits are required to map the key to the memory location.

k = 60​
k x k = 60 x 60​
= 3600​
h(60) = 60

The hash value obtained is 60

Example:

3. Folding Method:

This method involves two steps:

 1.​ Divide the key-value k into a number of parts i.e. k1, k2,

k3,….,kn, where each part has the same number of digits

except for the last part that can have lesser digits than the

other parts.

2.​ Add the individual parts. The hash value is obtained by

ignoring the last carry if any.

Formula:

k = k1, k2, k3, k4, ….., kn​

s = k1+ k2 + k3 + k4 +….+ kn​
h(K)= s

Here,​
s is obtained by adding the parts of the key k

Example:

k = 12345​
k1 = 12, k2 = 34, k3 = 5​
s = k1 + k2 + k3​
= 12 + 34 + 5​
= 51 ​
h(K) = 51

Example:
4. Multiplication Method

This method involves the following steps:

1.​ Choose a constant value A such that 0 < A < 1.

2.​ Multiply the key value with A.
3.​ Extract the fractional part of kA.
4.​ Multiply the result of the above step by the size of the hash
table i.e. M.
5.​ The resulting hash value is obtained by taking the floor of the
result obtained in step 4.

Formula:

h(K) = floor (M (kA mod 1))

Here,​
M is the size of the hash table.​
k is the key value.​
A is a constant value.

Example:
k = 12345​
A = 0.357840​
M = 100

h(12345) = floor[ 100 (12345*0.357840 mod 1)]​

= floor[ 100 (4417.5348 mod 1) ]​
= floor[ 100 (0.5348) ]​
= floor[ 53.48 ]​
= 53

Collision resolution techniques:

Collisions happen when two or more keys point to the same array index.

Chaining, open addressing, and double hashing are a few techniques for

resolving collisions.
OPEN HASHING

Open hashing, also known as separate chaining, is a collision resolution

technique used in hash tables within data structures. In this method, when
multiple keys hash to the same index (a collision occurs), instead of trying to
find another empty slot within the main hash table array, these colliding keys
are stored in a linked list (or another suitable data structure like a binary
search tree) at that specific index.

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.
CLOSED HASHING/ OPEN ADDRESSING

Open Addressing is a method for handling collisions. In Open Addressing,

all elements are stored in the hash table itself. So at any point, the size of

the table must be greater than or equal to the total number of keys (Note

that we can increase table size by copying old data if needed). This

approach is also known as closed hashing. This entire procedure is based

upon probing.

Type of closed hashing:

1. 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.

The function used for rehashing is as follows: rehash(key) =

(n+1)%table-size.

For example, The typical gap between two probes is 1 as seen in the

example below:

Let hash(x) be the slot index computed using a hash function and S be the
table size
If slot hash(x) % S is full, then we try (hash(x) + 1) % S​
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S​
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S

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.
Remedies for Clustering in Closed Hashing

To overcome the limitations of linear probing, especially clustering, other

probing strategies are used:

1)​ Quadratic Probing

Quadratic probing is an open addressing scheme in hashing 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 i2-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
 2)​ 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.

 3)​ Random Probing

In Random Probing, when a collision occurs, instead of checking the next

slot or following a fixed pattern (like in linear or quadratic probing), we use
a random sequence to choose the next slot.

●​ Formula:​
h'(key, i) = (h(key) + R(i)) % table_size​
where R(i) is a pseudo-random function (same sequence for the
same key).​

●​ This helps reduce clustering because it spreads keys more evenly

across the table.​

Example

●​ Hash table size: 10​

●​ Hash function: h(key) = key % 10​

 ●​ Keys to insert: 25, 35, 15, 95​

●​ Random sequence (fixed for this example): R(i) = [3, 7, 2, 5,

6]​
→ This means on the 1st probe we add 3, then 7, and so on.​

Step-by-Step Insertion:

1.​ Insert 25​

h(25) = 25 % 10 = 5​
Slot 5 is empty → insert at index 5​

2.​ Insert 35​

h(35) = 35 % 10 = 5​
Slot 5 is occupied → use random probing:​

○​ 1st probe: (5 + 3) % 10 = 8 → slot 8 is empty → insert at

8​

3.​ Insert 15​

h(15) = 15 % 10 = 5​
Slot 5 is taken → use random probing:​

○​ 2nd probe: (5 + 7) % 10 = 2 → slot 2 is empty → insert at

2​

4.​ Insert 95​

h(95) = 95 % 10 = 5​
 Slot 5 is taken → use random probing:​

○​ 3rd probe: (5 + 2) % 10 = 7 → empty → insert at 7

What is Load Factor?

Load factor is a measure that helps to decide when to increase the HashTable or
HashMap capacity to maintain the operations(search and insert) complexity of O(1).
The default value of the load factor is 0.75, i.e. 75% of the HashMap size. Load
factor can be decided using the formula as follows:

The initial capacity of the HashMap * Load factor of the HashMap

Let's understand Load Factor with the help of an example. For example if the initial
capacity of Hashtable is 20 and the load factor of hastable is 0.75(default value),
then according to the formula 20*0.75 = 15. It means the 15th key-value pair of the
hashtable will keep its size as 20. Now when we insert the 16th key-value pair into
the hashtable, it will increases its size from 20 to 20*2 = 40 buckets.

Rehashing:​
Rehashing is the process of increasing the size of a hashmap and
redistributing the elements to new buckets based on their new hash
values. It is done to improve the performance of the hashmap and to
prevent collisions caused by a high load factor.

When a hashmap becomes full, the load factor (i.e., the ratio of the
number of elements to the number of buckets) increases. As the load
factor increases, the number of collisions also increases, which can lead to
poor performance. To avoid this, the hashmap can be resized and the
elements can be rehashed to new buckets, which decreases the load
factor and reduces the number of collisions.

During rehashing, all elements of the hashmap are iterated and their new
bucket positions are calculated using the new hash function that
corresponds to the new size of the hashmap. This process can be
time-consuming but it is necessary to maintain the efficiency of the
hashmap.

Why rehashing?

Rehashing is needed in a hashmap to prevent collision and to maintain the

efficiency of the data structure.

As elements are inserted into a hashmap, the load factor (i.e., the ratio of
the number of elements to the number of buckets) increases. If the load
factor exceeds a certain threshold (often set to 0.75), the hashmap
becomes inefficient as the number of collisions increases. To avoid this, the
hashmap can be resized and the elements can be rehashed to new
buckets, which decreases the load factor and reduces the number of
collisions. This process is known as rehashing.

Rehashing can be costly in terms of time and space, but it is necessary to

maintain the efficiency of the hashmap.

How Rehashing is done?​

Rehashing can be done as follows:

●​ For each addition of a new entry to the map, check the load

factor.

●​ If it's greater than its pre-defined value (or default value of 0.75 if

not given), then Rehash.

●​ For Rehash, make a new array of double the previous size and

make it the new bucketarray.

●​ Then traverse to each element in the old bucketArray and call the

insert() for each so as to insert it into the new larger bucket array.