🔍

Search and Sort Algorithms

Subject DSA

Modules Module 5

Class
@November 12, 2025
Date

5.1: Searching techniques: Linear search, binary search, Fibonacci search

5.2: Hashing: Hash functions, overflow handling, collision and collision
Description resolution techniques
5.3: Sorting techniques: Merge sort, quick sort, radix sort, selection sort,
insertion sort, heap sort algorithms, and their performance analysis

5.1: Searching Techniques: Linear Search,

Binary Search, Fibonacci Search
Searching algorithms efficiently locate specific information within a dataset. They form the
foundation for advanced concepts such as database querying and help illustrate time-
complexity principles.

Linear Search (Sequential Search)

Linear search scans through elements one by one until it finds the target value or reaches the
end of the list.

Real-World Examples:

Searching for a contact in an unorganized notebook.

Checking attendance by scanning roll numbers sequentially.

Algorithm: LINEAR_SEARCH(A, N, VAL)

1. Initialize position variable: SET POS = -1 .

2. Initialize counter: SET I = 1 .

Search and Sort Algorithms 1

 3. Loop while I<= N (where N is the number of elements).

4. Inside the loop, check if A[I] == VAL (the value you're searching for).

5. If TRUE: Set POS = I , print the position, and exit.

6. If FALSE: Increment the counter: SET I = I + 1 .

7. If the loop finishes and POS is still -1 , print "VALUE IS NOT PRESENT".

Analysis:

Time Complexity: O(n), where nis the number of elements in the array.

Best Case: O(1)—the element is found at the first position, requiring only one
comparison.

Worst Case: O(n)—the element is at the last position or not in the array, requiring
ncomparisons.
Examples:
Here is a step-by-step example of a Linear Search, based on the provided presentation.
Goal: Find the value V AL = 7in the following array:
A = {10, 8, 2, 7, 3, 4, 9, 1, 6, 5}
Linear search works by checking each element one by one, starting from the beginning.

1. Step 1: Look at the first element, A[0].Is10 == 7? No.

2. Step 2: Look at the second element, A[1].Is8 == 7? No.
3. Step 3: Look at the third element, A[2].Is2 == 7? No.
4. Step 4: Look at the fourth element, A[3].Is7 == 7? Yes.
5. Result: The value 7 is found at position 4 (or index 3, assuming a 0-based index).
The search stops.

Another example from the presentation searches for the value 33 (V AL = 33) in the
array A = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44}.

The search would proceed as follows:

1. Is 10 == 33? No.
2. Is 14 == 33? No.
3. Is 19 == 33? No.

Search and Sort Algorithms 2

 4. Is 26 == 33? No.
5. Is 27 == 33? No.
6. Is 31 == 33? No.
7. Is 33 == 33? Yes.
8. Result: The value 33 is found.

Binary Search
Binary search is a highly efficient algorithm that requires sorted data. It works by repeatedly
dividing the search interval in half.

Real-World Examples:

Searching for a word in a dictionary.

Looking up a name in a sorted telephone directory.

Algorithm: BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

1. Initialize boundaries: SET BEG = lower_bound , SET END = upper_bound , SET POS = -1 .

2. Loop while BEG <= END .

3. Calculate the middle index: SET MID = (BEG + END) / 2 .

4. Compare the middle value with the target:

If A[MID] == VAL : Value found. Set POS = MID , print POS , and exit.

If A[MID] > VAL : Target is in the lower half. Set END = MID - 1 .

If A[MID] < VAL : Target is in the upper half. Set BEG = MID + 1 .

5. If the loop finishes and POS is still -1 , print "VALUE IS NOT PRESENT".

Example: Search for V AL = 9in the sorted array A =

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
1. BEG=0, END=10, MID=5. A[5] is 5. Since 5 < 9, set BEG = MID + 1 = 6.
2. BEG=6, END=10, MID=8. A[8] is 8. Since 8 < 9, set BEG = MID + 1 = 9.
3. BEG=9, END=10, MID=9. A[9] is 9. Value found at position 9.

Analysis:

Time Complexity: Each comparison halves the search space, resulting in

logarithmic time complexity.

Search and Sort Algorithms 3

 Best Case: O(1)—the element is found in the middle on the first try.

Average/Worst Case: O(log n).

5.2: Hashing: Hash functions, overflow

handling, collision and collision resolution
techniques
Hashing is a technique for indexing and retrieving elements from a data structure. It provides
fast data access using a "hash key."

Hash Function: A mathematical formula that takes a key and produces an integer used
as an index (or "hash value") in the hash table.

Hash Table: An array that maps keys to data using a hash function, allowing insertion,
deletion, and search operations in (ideally) constant time.

Hash Function Methods

Several methods exist for calculating hash values:

Division Method: The hash value is the remainder when the key is divided by the table
size (m).

Formula: h(x) = x mod m.

Example: If key = 102and table_size = 10, the index is 102
mod 10 = 2.
Mid-Square Method: The key is squared, and the middle r digits are extracted as the
index.

Example: If key = 1234and the table has 100 locations (so r = 2), then
key 2 = 1522756. The middle two digits (3rd and 4th from the right) are 27,
giving a hash value of 27.

Folding Method: The key is divided into parts, which are then combined (e.g., added) to
create the hash value.

Example: If key = 5678, split it into 56and 78. The sum is 56 + 78 = 134.
If a two-digit index is needed, ignore the carry, resulting in a hash value of 34.

Collision Resolution Techniques

Search and Sort Algorithms 4

 Closed Addressing (Separate Chaining / Open Hashing)
This is the most straightforward method. Instead of storing the value directly in the array,
each hash table location holds a pointer to a data structure (like a linked list) that stores all the
keys that hash to that same location.

How it works:

1. When a key is hashed, the algorithm goes to the corresponding index in the hash
table.

2. If this is the first key for that index, a new linked list is created, and the key is added
as the first node.

3. If a linked list already exists (meaning a collision or "overflow" has already occurred
for this index), the new key is simply added to the end of that list.

Example from your notes:

Keys: 7, 24, 18, 52, 36, 54...

Hash function: h(k) = k mod 9

Step 3: Key 18is inserted. 18 mod 9 = 0. It's stored at index 07.
Step 5: Key 36is inserted. 36 mod 9 = 0. This is an overflow. The algorithm
appends 36to the linked list at index 0, so it becomes 18− > 36.

Step 6: Key 54is inserted. 54 mod 9 = 0. Another overflow. The key is
appended to the same list, which is now 18− > 36− > 54.

Open Addressing (Closed Hashing)

In this method, all keys are stored within the hash table array itself. When an overflow
(collision) occurs, the algorithm "probes" or searches for the next available (open) slot in the
table to store the value.
Your notes detail a specific type of open addressing:

Linear Probing

This is the simplest probing technique. If the calculated index his full, the algorithm
sequentially checks the next slots: h + 1, h + 2, h + 3, and so on, until a vacant slot is
found.

How it works:

The formula used is h(k, i) = [h’(k) + i] mod m.

mis the table size.

Search and Sort Algorithms 5

 h’(k)is the original hash function (e.g., k mod m).
iis the probe number, which starts at and increases by 1 for each failed attempt.
Example from your notes:

Hash table of size 10 (m = 10), h’(k) = k mod 10.

Key = 72: h(72, 0) = (72 mod 10 + 0) mod 10 = 2. Slot 2 is empty.
Insert 72 at T [2].

Key = 92:

1. Probe i = 0: h(92, 0) = (92 mod 10 + 0) mod 10 = 2. But T [2]

is already occupied by 72. This is an overflow.

2. Probe i = 1 : h(92, 1) = (92 mod 10 + 1) mod 10 = 3. But T [3]

is also occupied (by key 63 in the example).

3. Probe i = 2 : h(92, 2) = (92 mod 10 + 2) mod 10 = 4. T [4]is

also occupied (by key 24).

4. Probe i = 3 : h(92, 3) = (92 mod 10 + 3) mod 10 = 5. T [5]is

vacant. Insert 92 at T [5].

The main problem with linear probing is that it can lead to clustering, where occupied slots
form long, consecutive clusters, which increases the number of probes needed to find a free
location.

5.3: Sorting techniques: Merge sort, quick sort,

radix sort, selection sort, insertion sort, heap
sort algorithms, and their performance analysis
Sorting arranges items in a systematic order.

Insertion Sort
Insertion sort builds the final sorted array one element at a time. It takes an element from the
unsorted portion and inserts it into its correct position in the sorted portion.

Algorithm: INSERTION-SORT(ARR, N)

1. Loop from K=1 to N-1 (starting with the second element).

2. Store the current element: SET TEMP = ARR[K] .

Search and Sort Algorithms 6

 3. Initialize a second index: SET J = K - 1 (the last element of the sorted portion).

4. Loop while TEMP <= ARR[J] (and J ≥ 0).

5. Inside the inner loop, shift the sorted element right: SET ARR[J + 1] = ARR[J] .

6. Decrement J : SET J = J - 1 .

7. After the inner loop, insert the stored element: SET ARR[J + 1] = TEMP .

8. Repeat for all elements.

Analysis:

Best Case: O(n)—occurs when the array is already sorted.

Worst Case: O(n2 )—occurs when the array is sorted in reverse order.

Space Complexity: O(1)(in-place sort).

Note: Efficient for small datasets and nearly sorted lists.

Example:
Initial Array: {12, 31, 25, 8, 32, 17}

Pass 1: (Compare 31 and 12)

{12, 31, 25, 8, 32, 17}(31 is in the correct place)

Pass 2: (Pick 25, compare with 31, insert before 31)

{12, 25, 31, 8, 32, 17}

Pass 3: (Pick 8, compare with 31, 25, and 12, insert at start)

{8, 12, 25, 31, 32, 17}

Pass 4: (Pick 32, compare with 31)

{8, 12, 25, 31, 32, 17}(32 is in the correct place)

Pass 5: (Pick 17, compare with 32, 31, 25, 12, insert before 25)

{8, 12, 17, 25, 31, 32}

Final Sorted Array: {8, 12, 17, 25, 31, 32}

Selection Sort
In each pass, selection sort finds the smallest element from the unsorted portion and swaps it
into its correct position at the beginning of the unsorted section. It maintains two sub-arrays: a
sorted portion on the left and an unsorted portion on the right.

Search and Sort Algorithms 7

 Algorithm: SELECTION_SORT(ARR, N)

1. Loop from K=1 to N-1 (tracking the boundary of the sorted portion).

2. In each pass, find the index ( POS ) of the smallest element in the unsorted range
ARR[K] to ARR[N-1] (e.g., using a SMALLEST function).

3. Swap the element at the current boundary ( A[K] ) with the smallest element found
( ARR[POS] ).

4. Repeat until K reaches N − 1.

Analysis:

Time Complexity: O(n2 )for all cases (Best, Average, and Worst). Even when the
array is sorted, the algorithm must scan the entire unsorted portion in every pass to
find the next smallest element.

Space Complexity: O(1)(in-place sort).

Example:

Initial Array: {12, 29, 25, 8, 32, 17, 40}

Pass 1: (Find smallest element: 8. Swap with 12)

{8, 29, 25, 12, 32, 17, 40}

Pass 2: (Find smallest in unsorted part: 12. Swap with 29)

{8, 12, 25, 29, 32, 17, 40}

Pass 3: (Find smallest in unsorted part: 17. Swap with 25)

{8, 12, 17, 29, 32, 25, 40}

Pass 4: (Find smallest in unsorted part: 25. Swap with 29)

{8, 12, 17, 25, 32, 29, 40}

Pass 5: (Find smallest in unsorted part: 29. Swap with 32)

{8, 12, 17, 25, 29, 32, 40}

Pass 6: (Find smallest in unsorted part: 32. Swap with 32)

{8, 12, 17, 25, 29, 32, 40}

Final Sorted Array: {8, 12, 17, 25, 29, 32, 40}

Quick Sort

Search and Sort Algorithms 8

 Quick sort is a highly efficient sorting algorithm that uses the divide-and-conquer approach.

Algorithm (Divide and Conquer):

1. Divide: Choose an element as the pivot. Partition the array into two sub-arrays:
elements less than or equal to the pivot move to its left, and elements greater than the
pivot move to its right.

2. Conquer: Recursively sort the two sub-arrays (left and right of the pivot) by calling
quicksort on them.

3. Combine: No combination step is needed—partitioning and recursive calls sort the

array in place.

Analysis:

Best Case: O(n log n)—occurs when the pivot is near the middle, splitting the
array into two roughly equal halves.

Average Case: O(n log n).

Worst Case: O(n2 )—occurs when the pivot is the smallest or largest element (e.g.,
in an already sorted array when picking the first element as pivot).

Space Complexity: O(n log n)(due to recursion call stack).

Example:
Initial Array: {4, 1, 7, 3, 2, 5, 8, 6}

Partition 1: (P ivot = 4)

The algorithm scans from both ends, swapping elements that are on the wrong
side.

i(left scan) stops at 7(larger than 4).

j (right scan) stops at 2(smaller than 4).
Swap 7and 2: {4, 1, 2, 3, 7, 5, 8, 6}

icontinue, stops at 7.

j continues, stops at 3.
ihave crossed j . Swap the pivot(4)with j (3).
Array after 1st partition: {3, 1, 2, 4, 7, 5, 8, 6}

Sub-arrays to sort: (3, 1, 2)and (7, 5, 8, 6)

Search and Sort Algorithms 9

 Partition 2: (Sort {3, 1, 2}with P ivot = 3)
Partitioning results in: (2, 1)and (3)(pivot in place)
Recursive sort on {2, 1}results in {1, 2}

Left side sorted: {1, 2, 3}

Partition 3: (Sort {7, 5, 8, 6}with P ivot = 7)

Partitioning results in: (6, 5)and (8)(pivot in place)
Recursive sort on {6, 5}results in {5, 6}

Right side sorted: {5, 6, 7, 8}

Combine:

Final Sorted Array: {1, 2, 3, 4, 5, 6, 7, 8}

Merge Sort
Merge sort is a popular, efficient sorting algorithm that uses the divide-and-conquer approach.

Algorithm (Divide and Conquer): MERGE_SORT(arr, beg, end)

1. Divide: Recursively divide the list into two halves. If beg<end , find the midpoint
and call MERGE_SORT for the left half ( beg to mid ) and the right half ( mid + 1 to
end ). Continue until sub-lists contain only one element.

2. Conquer & Combine: Call MERGE(arr, beg, mid, end) . This function takes two sorted
sub-arrays (left and right halves) and merges them into a single sorted array. This
merging process repeats up the recursion chain until the entire list is sorted.

Analysis:

Time Complexity: O(n log n)for all cases (Best, Average, and Worst).
Performance is highly consistent.

Space Complexity: O(n)—requires temporary arrays to merge sub-lists.

Example:

Initial Array: {12, 31, 25, 8, 32, 17, 40, 42}

Divide Phase (Splitting):

{12, 31, 25, 8}and {32, 17, 40, 42}

{12, 31}, {25, 8}and {32, 17}, {40, 42}

Search and Sort Algorithms 10

 {12}, {31}, {25}, {8}and {32}, {17}, {40}, {42}
Conquer Phase (Merging):

Merge {12}and {31}-> {12, 31}

Merge {25}and {8}-> {8, 25}

Merge {32}and {17}-> {17, 32}

Merge {40}and {42}-> {40, 42}

Merge {12, 31}and {8, 25}-> {8, 12, 25, 31}

Merge {17, 32}and {40, 42}-> {17, 32, 40, 42}

Merge {8, 12, 25, 31}and {17, 32, 40, 42}->

{8, 12, 17, 25, 31, 32, 40, 42}
Final Sorted Array: {8, 12, 17, 25, 31, 32, 40, 42}

Radix Sort
Radix sort is a non-comparative sorting algorithm for integers, also known as bucket sort. It
sorts data by grouping elements by individual digits, starting from the least significant digit
(ones place) and moving to the most significant digit.

Algorithm:

1. Find the largest element ( max ) in the array to determine the number of digits (k ),
which determines the number of passes required.

2. For each digit place (from i = 1to k ):

3. Use a stable sorting algorithm (like Counting Sort) to sort the array based only on
the digit at the current place.

Stable Sort: Critical—if two numbers have the same digit at the current place (e.g.,
181 and 289), their relative order from the previous pass must be maintained.

Analysis:

Time Complexity: O(nk), where nis the number of elements and k is the number
of digits in the largest number.

Space Complexity: O(n + k).

Example:

Initial Array: {345, 654, 924, 123, 567, 472, 555, 808, 911}

Search and Sort Algorithms 11

 Pass 1 (Sort by Ones Place):

911(ends in 1)
472(ends in 2)
123(ends in 3)
654, 924(end in 4)
345, 555(end in 5)
567(ends in 7)
808(ends in 8)
Array after Pass 1: {911, 472, 123, 654, 924, 345, 555, 567, 808}

Pass 2 (Sort by Tens Place):

808(tens place is 0)
911(tens place is 1)
123, 924(tens place is 2)
345(tens place is 4)
654, 555(tens place is 5)
567(tens place is 6)
472(tens place is 7)
Array after Pass 2: {808, 911, 123, 924, 345, 654, 555, 567, 472}

Pass 3 (Sort by Hundreds Place):

123(hundreds place is 1)
345(hundreds place is 3)
472(hundreds place is 4)
555, 567(hundreds place is 5)
654(hundreds place is 6)
808(hundreds place is 8)
911, 924(hundreds place is 9)
Array after Pass 3: {123, 345, 472, 555, 567, 654, 808, 911, 924}

Search and Sort Algorithms 12

 Final Sorted Array: {123, 345, 472, 555, 567, 654, 808, 911, 924}

Heap Sort
Heap sort is an in-place comparison-based sorting algorithm.

Algorithm:

1. Build Heap: Create a complete binary tree from the array elements, then rearrange it
into a Max Heap (where every parent node is larger than its children) using a
heapify process.

2. Sort:

The largest element is now at the root ( arr[0] ).

Swap the root with the last element of the heap.

Reduce the heap size by one and call heapify on the new root to restore the Max
Heap property.

Repeat until the heap is empty—the array will be sorted.

Analysis:

Time Complexity: O(n log n)for all cases (Best, Average, and Worst).

Space Complexity: O(1)(in-place sort).

Example:
Initial Array: {9, 4, 3, 8, 10, 2, 5}

Step 1 & 2: Build a Max Heap (Heapify)

The array is rearranged to satisfy the Max Heap property.

After building the heap, the array will look like:

{10, 9, 5, 8, 4, 2, 3}(with 10 at the root)

Step 3: Sort the Array (Extract Max)

Pass 1: Swap root (10) with last element (3). Heap is {3, 9, 5, 8, 4, 2}, Array
is {..., 10}.

Heapify {3, 9, 5, 8, 4, 2}-> {9, 8, 5, 3, 4, 2}

Pass 2: Swap root (9) with last element (2). Heap is {2, 8, 5, 3, 4}, Array is
{..., 9, 10}.

Search and Sort Algorithms 13

 Heapify {2, 8, 5, 3, 4}-> {8, 4, 5, 3, 2}

Pass 3: Swap root (8) with last element (2). Heap is {2, 4, 5, 3}, Array is
{..., 8, 9, 10}.
Heapify {2, 4, 5, 3}-> {5, 4, 2, 3}

Pass 4: Swap root (5) with last element (3). Heap is {3, 4, 2}, Array is
{..., 5, 8, 9, 10}.
Heapify {3, 4, 2}-> {4, 3, 2}

Pass 5: Swap root (4) with last element (2). Heap is {2, 3}, Array is
{..., 4, 5, 8, 9, 10}.
Heapify {2, 3}-> {3, 2}

Pass 6: Swap root (3) with last element (2). Heap is {2}, Array is
{..., 3, 4, 5, 8, 9, 10}.
Final Sorted Array: {2, 3, 4, 5, 8, 9, 10}

Summary of Sorting Algorithm Complexities

Sorting Space
Best Case Average Case Worst Case
Algorithm Complexity

Selection Sort O(n2 ) O(n2 ) O(n2 ) O(1)

Insertion Sort O(n) O(n2 ) O(n2 ) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n2 ) O(n)∗
Heap Sort O(n log n) O(n log n) O(n log n) O(1)
Radix Sort Ω(nk) θ(nk) O(nk) O(n + k)

Search and Sort Algorithms 14