Data Structures and Algorithms
Unit 2 – Searching, Sorting and Hashing
2.1 Introduction to Searching and Sorting
2.1.1 Need for Searching
Definition:
Searching is the process of locating the position of a particular element, known as the key, within
a collection of data items such as an array, list, or database.
Purpose of Searching:
1. To quickly retrieve information from large datasets.
2. To enable efficient update, delete, and retrieval operations in data structures.
3. To improve the performance of applications that depend on fast access to data (e.g.,
databases, search engines).
Examples:
● Searching for a name in a telephone directory.
● Looking up a student’s roll number in a university database.
● Checking if a particular product ID exists in an inventory system.
searching forms the foundation for efficient information retrieval and is a critical operation in
almost every real-world application.
2.1.2 Need for Sorting
Definition:
Sorting is the process of arranging a set of data elements into a particular sequence — usually in
ascending or descending order, based on a key field.
Purpose of Sorting:
1. Enhances Searching Efficiency:
○ Many searching algorithms (e.g., Binary Search) require sorted data to work
correctly and efficiently.
S.Y. B. Tech IT Page No. 1 MMCOE, Pune
Data Structures and Algorithms
2. Improves Readability and Organization:
○ Data arranged in a logical order is easier to understand and analyze.
3. Facilitates Data Processing:
○ Sorting is often a prerequisite step for operations such as merging, duplicate
removal, and reporting.
Examples:
● Arranging exam scores in descending order to generate a merit list.
● Sorting files by date before archiving.
● Alphabetically sorting student names in a class list.
sorting plays a dual role: it improves the usability of data and also serves as a performance
booster for several algorithms that rely on ordered inputs.
2.1.3 Internal vs External Sorting
Sorting techniques are broadly classified into internal and external sorting, depending on
whether the dataset fits entirely in main memory.
Criteria Internal Sorting External Sorting
Definitio Sorting is done entirely Sorting is applied when the data does
n within the main not fit into main memory and must
memory (RAM). be managed using external storage
(e.g., disk).
Example Sorting an array of 500 Sorting a 10GB log file stored on disk.
integers in RAM.
Speed Faster, since only main Slower due to repeated disk I/O
memory operations operations.
are involved.
Techniq Bubble Sort, Selection External Merge Sort, Polyphase Merge
ues Sort, Insertion Sort, Sort, Replacement Selection.
Used Quick Sort, Merge
S.Y. B. Tech IT Page No. 2 MMCOE, Pune
Data Structures and Algorithms
Sort, Heap Sort.
internal sorting is suitable for small to medium datasets, while external sorting is indispensable
for large-scale applications like databases and data warehouses.
2.1.4 Sort Stability
Stable Sort:
● A sorting algorithm is said to be stable if it preserves the relative order of records with
equal keys.
● This is especially important in multi-key sorting, where a secondary key must maintain its
order after sorting on the primary key.
Example:
● Two students have the same marks:
○ Original order: (Rahul, 80), (Sneha, 80)
○ After stable sort: (Rahul, 80), (Sneha, 80)
● Stable Sorting Algorithms: Bubble Sort, Insertion Sort, Merge Sort.
Unstable Sort:
● A sorting algorithm is unstable if it does not necessarily preserve the order of equal
elements.
Example:
● Original order: (Rahul, 80), (Sneha, 80)
● After unstable sort: (Sneha, 80), (Rahul, 80)
● Unstable Sorting Algorithms: Quick Sort (general implementation), Selection Sort, Heap
Sort.
stability is desirable when data records are complex structures with multiple fields, since users
often expect secondary attributes to remain consistently ordered.
2.2 Searching Methods
2.2.1 Linear Search
S.Y. B. Tech IT Page No. 3 MMCOE, Pune
Data Structures and Algorithms
● Concept: Sequentially compares each element with the key until a match is found or the list
ends.
Algorithm:
1. Start from first element (index = 0).
2. Compare current element with key.
3. If match found → return index.
4. Else → move to next element.
5. If end reached → return "Not Found".
Example:
Array: [10, 25, 36, 45]
Key: 36
Comparisons: 10 ≠ 36, 25 ≠ 36, 36 = 36 → Found at index 2
Complexity:
○ Best Case: O(1) (found at first position)
○ Worst Case: O(n) (found at last or not found)
○ Space Complexity: O(1)
2.2.2 Binary Search
● Concept: Works only on sorted data. Repeatedly divides search interval in half.
Algorithm:
1. low = 0, high = n-1
2. while low <= high:
mid = (low + high) / 2
if key == arr[mid] → return mid
else if key < arr[mid] → high = mid - 1
S.Y. B. Tech IT Page No. 4 MMCOE, Pune
Data Structures and Algorithms
else → low = mid + 1
3. return "Not Found"
Example:
Array: [10, 20, 30, 40, 50], Key: 40
Step 1: mid = 2 → arr[2] = 30 → 40 > 30 → low = 3
Step 2: mid = 3 → arr[3] = 40 → Found at index 3
●
● Complexity:
○ Best Case: O(1)
○ Worst Case: O(log n)
○ Space Complexity: O(1) (iterative)
2.3 Sorting Methods
2.3.1 Bubble Sort
● Concept: Compares adjacent elements and swaps them if they are in wrong order.
Continues until no swaps are needed.
Algorithm:
for i = 0 to n-1
for j = 0 to n-i-2
if arr[j] > arr[j+1]
swap(arr[j], arr[j+1])
Example: (Ascending order)
Pass 1: [5, 3, 8] → swap 5 & 3 → [3, 5, 8]
Pass 2: [3, 5, 8] → no swap → sorted
S.Y. B. Tech IT Page No. 5 MMCOE, Pune
Data Structures and Algorithms
● Complexity:
Best: O(n), Worst: O(n²), Space: O(1)
● Stability: Stable
2.3.2 Insertion Sort
Concept: Builds the sorted array one element at a time by inserting each new element into its
correct position.
Algorithm:
for i = 1 to n-1
key = arr[i]
j=i-1
while j >= 0 and arr[j] > key
arr[j+1] = arr[j]
j=j-1
arr[j+1] = key
Example:
Step 1: [7, 4, 5] → insert 4 before 7 → [4, 7, 5]
Step 2: insert 5 before 7 → [4, 5, 7]
Complexity:
Best: O(n), Worst: O(n²), Space: O(1)
Stability: Stable
2.3.3 Quick Sort
● Concept: Uses divide-and-conquer. Selects a pivot, partitions the array into two subarrays
(less than pivot, greater than pivot), and recursively sorts.
S.Y. B. Tech IT Page No. 6 MMCOE, Pune
Data Structures and Algorithms
Algorithm:
quickSort(arr, low, high):
if low < high:
p = partition(arr, low, high)
quickSort(arr, low, p-1)
quickSort(arr, p+1, high)
Complexity:
Best/Average: O(n log n), Worst: O(n²) (if pivot chosen poorly)
Stability: Not stable in general
2.3.4 Merge Sort
● Concept: Recursively divides array into halves, sorts them, and merges the sorted halves.
Algorithm:
mergeSort(arr, l, r):
if l < r:
m = (l+r)/2
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
Complexity: Always O(n log n), Space: O(n)
Stability: Stable
2.4 Hashing
S.Y. B. Tech IT Page No. 7 MMCOE, Pune
Data Structures and Algorithms
2.4.1 Concept of Hash Tables
● Stores data in an array where the position is determined by a hash function.
● Example:
Key = 1234, Table size = 10 → Position = 1234 % 10 = 4.
2.4.2 Characteristics of a Good Hash Function
● Should distribute keys uniformly.
● Should minimize collisions.
● Should be fast to compute.
2.4.3 Key-to-Address Transformation Techniques
Hashing Functions – Methods
Hashing is the process of mapping keys into positions (addresses) in a hash table using a hash
function. A good hash function reduces collisions and distributes keys uniformly.
Common methods:
1. Division Method
Formula:
h(k)=kmod mh(k) = k \mod m
where:
● kk = key
● mm = size of hash table (usually a prime number, not a power of 2)
Explanation:
● The key is divided by the table size mm.
● The remainder gives the index (hash value).
Example:
If k=1234k = 1234, m=10m = 10:
h(1234)=1234mod 10=4h(1234) = 1234 \mod 10 = 4
Advantages:
● Simple and fast.
● Works well if mm is prime.
S.Y. B. Tech IT Page No. 8 MMCOE, Pune
Data Structures and Algorithms
Disadvantages:
● Poor choice of mm (like multiples of 2 or 10) may cause clustering of values.
2. Mid-Square Method
Process
1. Square the key kk.
2. Extract a few middle digits from the result.
3. Use those digits as the hash value.
Explanation:
● Middle digits are chosen because they are influenced by all digits of the key (not just higher
or lower order digits).
● Reduces patterns in distribution.
Example:
Key = 123 → 1232=15129123^2 = 15129
Middle digits = 512
If table size = 1000 → Hash index = 512
Advantages:
● Produces good distribution for keys with similar patterns.
● Simple to compute.
Disadvantages:
● More expensive than division.
● Extracting middle digits must be carefully defined.
3. Folding Method
Process:
1. Split the key into equal parts (usually groups of digits).
2. Add the parts together.
3. If necessary, apply modulo with table size.
Techniques:
● Shift Folding: Divide the number into parts and add them directly.
S.Y. B. Tech IT Page No. 9 MMCOE, Pune
Data Structures and Algorithms
● Boundary Folding: Alternate reversing of parts before adding to mix digits better.
Example (Shift Folding):
Key = 123456, split into (12, 34, 56)
12+34+56=10212 + 34 + 56 = 102
If table size = 100 → Index = 102 mod 100 = 2
Advantages:
● Works well with large keys.
● Ensures all digits contribute to hash value.
Disadvantages:
● May still lead to collisions if key patterns repeat.
4. Multiplication Method
Formula:
h(k)=⌊m×(k×Amod 1)⌋h(k) = \lfloor m \times (k \times A \mod 1) \rfloor
where:
● kk = key
● mm = size of hash table
● AA = constant (0 < A < 1), often irrational (e.g., A=5−12A = \frac{\sqrt{5}-1}{2})
Explanation:
● Multiply key kk by constant AA.
● Take the fractional part (after decimal point).
● Multiply by table size mm.
● Floor the result to get hash value.
Example:
Let k=1234k = 1234, m=1000m = 1000, A=0.618A = 0.618
1234×0.618=762.6121234 \times 0.618 = 762.612
S.Y. B. Tech IT Page No. 10 MMCOE, Pune
Data Structures and Algorithms
Fractional part = 0.612
h(k)=⌊1000×0.612⌋=612h(k) = \lfloor 1000 \times 0.612 \rfloor = 612
Advantages:
● Works well regardless of mm.
● Avoids clustering seen in division method.
Disadvantages:
● Slightly more computational cost (multiplication + fractional extraction).
2.4.4 Synonyms or Collisions
● Synonyms: Different keys producing the same address.
● Collision: When two keys hash to the same location.
2.4.5 Collision Resolution Techniques
1. Linear Probing
● Definition:
In linear probing, if the hash table position computed by the hash function is already
occupied, the next position is checked sequentially (index +1, index +2, and so on) until an
empty slot is found.
● Hash Function:
h(k,i)=(h(k)+i)mod mh(k, i) = (h(k) + i) \mod m
where i=0,1,2,…i = 0, 1, 2, \ldots
● Example:
Suppose table size m=7m = 7 and keys = {37, 47, 57}.
1. 37mod 7=237 mod 7 = 2 → place at index 2.
2. 47mod 7=547 mod 7 = 5 → place at index 5.
3. 57mod 7=157 mod 7 = 1 → place at index 1.
If another key 67mod 7=467 mod 7 = 4, but if index 4 is full, check 5 → 6 → 0 →
until empty slot is found.
● Advantages:
1. Simple to implement.
S.Y. B. Tech IT Page No. 11 MMCOE, Pune
Data Structures and Algorithms
2. Requires no extra memory.
● Disadvantages:
1. Causes primary clustering – consecutive occupied slots form clusters.
2. Performance degrades when table gets nearly full.
2. Quadratic Probing
● Definition:
Quadratic probing resolves collision by using quadratic increments instead of linear
increments.
● Hash Function:
h(k,i)=(h(k)+i2)mod mh(k, i) = (h(k) + i^2) \mod m
● Example:
Suppose m=7m = 7, and a key k=49k = 49.
1. 49mod 7=049 mod 7 = 0, so initial index = 0.
2. If index 0 is occupied: try (0+12)mod 7=1(0 + 1^2)mod 7 = 1.
3. If index 1 is also full: try (0+22)mod 7=4(0 + 2^2) mod 7 = 4.
4. If still full: try (0+32)mod 7=2(0 + 3^2) mod 7 = 2, and so on.
● Advantages:
1. Reduces primary clustering.
2. Distributes keys more uniformly.
● Disadvantages:
1. Suffers from secondary clustering (keys with same initial position follow same
probe sequence).
2. Slightly more computation than linear probing.
3. Rehashing (Double Hashing)
● Check the Load Factor: Periodically or after each insertion operation, the hash table
checks its load factor. If the load factor exceeds a predefined threshold (often around 0.7 or
0.8), it indicates that the table is becoming crowded, and rehashing is needed.
● Create a New Hash Table: A new, larger hash table (usually with double the number of
buckets) is created. The number of buckets is increased to reduce the load factor and make
the table more efficient.
● Rehashing Process: Each element in the old hash table is rehashed, meaning their keys
are mapped to new bucket positions in the larger table using the updated hash function.
This process redistributes the key-value pairs among the new buckets.
S.Y. B. Tech IT Page No. 12 MMCOE, Pune
Data Structures and Algorithms
● Transfer Elements: The key-value pairs are transferred from the old table to the new
table based on their new hash values. This involves copying the data from the old table to
the appropriate locations in the new table.
● Update References: Any references or pointers to the old hash table are updated to point
to the new hash table.
● Dispose of the Old Table: Once all elements have been transferred, the old hash table can
be deallocated or discarded.
● Advantages:
1. Eliminates clustering.
2. Gives better performance than probing.
● Disadvantages:
1. More complex implementation.
2. Requires careful choice of secondary hash function.
4. Chaining
● Definition:
In chaining, all elements that hash to the same address are stored in a linked list at that
index.
● Process:
1. Each hash table entry contains a pointer to a linked list.
2. If multiple keys hash to the same index, they are appended to the linked list.
● Example:
Table size m=7m = 7, Keys = {50, 700, 76}.
1. 50mod 7=150 mod 7 = 1 → index 1 → store 50.
2. 700mod 7=700 mod 7 = 0 → index 0 → store 700.
3. 76mod 7=676 mod 7 = 6 → index 6 → store 76.
4. If another key 83 hashes to 6 → append it in the linked list at index 6.
● Advantages:
1. No clustering problem.
2. Hash table never becomes “full.”
S.Y. B. Tech IT Page No. 13 MMCOE, Pune
Data Structures and Algorithms
● Disadvantages:
1. Requires extra memory for pointers.
2. Search time increases with longer chains.
5. With Replacement
Definition:
If a collision occurs and the existing element at that slot does not belong to its “home”
position, it is replaced by the new key, and the displaced key is reinserted elsewhere.
Steps:
1. Compute hash index for new key.
2. If slot is occupied by a displaced element → replace it.
3. Reinsert the displaced key.
Advantage: Keeps keys closer to their original hash index → faster searches.
Disadvantage: Reinsertion requires extra computation.
6. Without Replacement
● Definition:
If a collision occurs, the existing element remains in its place, and the new element is
inserted in another location using probing/chaining.
● Steps:
1. Compute hash index for new key.
2. If slot occupied → leave it as is.
3. Find another slot for the new key.
Advantage: Simple to implement.
Disadvantage: May increase displacement and search time.
S.Y. B. Tech IT Page No. 14 MMCOE, Pune
Data Structures and Algorithms
References:
1. Reema Thareja, "Data Structures using C ", Second Edition, Oxford Higher
Publication
2. Fundamentals of Computer Algorithms by Horowitz , Sahani, Galgotia Pub 2001 ed.
Sr. Question BL Marks
No.
1 Why do we need searching in a database or array? BL- 2
1
2 Explain the need for sorting of data with one example. BL- 2
2
3 Differentiate between internal and external sorting. BL- 2
2
4 What is meant by a stable sort? Give one example. BL- 2
1
5 Explain the difference between linear search and binary search. BL- 2
2
6 Differentiate bubble sort and insertion sort in terms of data movement. BL- 2
2
7 Give any two characteristics of a good hash function. BL- 2
1
8 What is a collision in hashing and why does it occur? BL- 2
2
9 Explain any two collision resolution techniques in hashing. BL- 2
2
10 Define a hash table and mention one advantage. BL- 2
1
11 Explain the difference between internal and external sorting with BL- 4
examples. 2
12 Describe the concept of stable and unstable sorting with examples. BL- 4
2
13 Write the pseudocode for linear search and explain its best and worst BL- 4
case time complexity. 3
14 Write the pseudocode for binary search and explain the condition for BL- 4
applying it. 3
S.Y. B. Tech IT Page No. 15 MMCOE, Pune
Data Structures and Algorithms
15 Compare bubble sort and insertion sort in terms of efficiency, number of BL- 4
comparisons, and swaps. 3
16 Explain the working of quick sort with a suitable example. BL- 4
2
17 Explain the working of merge sort with a suitable example. BL- 4
2
18 Explain collision in hashing with an example and describe linear BL- 4
probing to resolve it. 3
19 Explain chaining in hash tables with and without replacement with a BL- 4
small example. 3
20 Discuss the characteristics of a good hash function and give two BL- 4
examples of key-to-address transformation techniques. 2
21 Explain the steps of linear search with pseudocode. Perform a frequency BL- 6
count for best and worst case. 3
22 Write pseudocode for binary search and calculate its time complexity for BL- 6
an array of size n. 3
23 Explain bubble sort and insertion sort with an example of 5 numbers. BL- 6
Compare the number of comparisons and swaps. 3
24 Solve the following quick sort problem: Sort the array [34, 7, 23, BL- 6
32, 5, 62] using quick sort. Show each partition step. 3
25 Solve the following merge sort problem: Sort the array [12, 11, 13, BL- 6
5, 6, 7] using merge sort and show all merging steps. 3
26 Consider a hash table of size 10 and the keys [23, 43, 13, 27]. Use BL- 6
linear probing to insert keys and show the final hash table. 3
27 Consider a hash table of size 10 and the keys [32, 42, 52, 12, 22]. BL- 6
Use chaining with replacement to insert keys and show the final table. 3
28 Explain collision in hashing. Solve a problem: Insert keys [15, 25, BL- 6
35, 45] in a hash table of size 10 using quadratic probing. Show the 3
final table.
29 A hash table of size 10 uses linear probing. After inserting several keys, BL- 6
collisions occur frequently. Suggest two strategies to reduce collisions 4
and justify your choices.
30 BL- 6
4
Consider a hash table of size 7 and keys [10, 20, 5, 15, 25].
Insert keys using linear probing.
When the table gets full, apply rehashing with table size 14.
Show the final table after rehashing.
Sr. Question BL Marks
S.Y. B. Tech IT Page No. 16 MMCOE, Pune
Data Structures and Algorithms
No.
1 Why do we need searching in a database or array? BL- 2
1
2 Explain the need for sorting of data with one example. BL- 2
2
3 Differentiate between internal and external sorting. BL- 2
2
4 What is meant by a stable sort? Give one example. BL- 2
1
5 Explain the difference between linear search and binary search. BL- 2
2
6 Differentiate bubble sort and insertion sort in terms of data movement. BL- 2
2
7 Give any two characteristics of a good hash function. BL- 2
1
8 What is a collision in hashing and why does it occur? BL- 2
2
9 Explain any two collision resolution techniques in hashing. BL- 2
2
10 Define a hash table and mention one advantage. BL- 2
1
11 Explain the difference between internal and external sorting with BL- 4
examples. 2
12 Describe the concept of stable and unstable sorting with examples. BL- 4
2
13 Write the pseudocode for linear search and explain its best and worst BL- 4
case time complexity. 3
14 Write the pseudocode for binary search and explain the condition for BL- 4
applying it. 3
15 Compare bubble sort and insertion sort in terms of efficiency, number of BL- 4
comparisons, and swaps. 3
16 Explain the working of quick sort with a suitable example. BL- 4
2
17 Explain the working of merge sort with a suitable example. BL- 4
2
18 Explain collision in hashing with an example and describe linear BL- 4
probing to resolve it. 3
19 Explain chaining in hash tables with and without replacement with a BL- 4
small example. 3
S.Y. B. Tech IT Page No. 17 MMCOE, Pune
Data Structures and Algorithms
20 Discuss the characteristics of a good hash function and give two BL- 4
examples of key-to-address transformation techniques. 2
21 Explain the steps of linear search with pseudocode. Perform a frequency BL- 6
count for best and worst case. 3
22 Write pseudocode for binary search and calculate its time complexity for BL- 6
an array of size n. 3
23 Explain bubble sort and insertion sort with an example of 5 numbers. BL- 6
Compare the number of comparisons and swaps. 3
24 Solve the following quick sort problem: Sort the array [34, 7, 23, BL- 6
32, 5, 62] using quick sort. Show each partition step. 3
25 Solve the following merge sort problem: Sort the array [12, 11, 13, BL- 6
5, 6, 7] using merge sort and show all merging steps. 3
26 Consider a hash table of size 10 and the keys [23, 43, 13, 27]. Use BL- 6
linear probing to insert keys and show the final hash table. 3
27 Consider a hash table of size 10 and the keys [32, 42, 52, 12, 22]. BL- 6
Use chaining with replacement to insert keys and show the final table. 3
28 Explain collision in hashing. Solve a problem: Insert keys [15, 25, BL- 6
35, 45] in a hash table of size 10 using quadratic probing. Show the 3
final table.
29 A hash table of size 10 uses linear probing. After inserting several keys, BL- 6
collisions occur frequently. Suggest two strategies to reduce collisions 4
and justify your choices.
30 BL- 6
Consider a hash table of size 7 and keys [10, 20, 5, 15, 25]. 4
Insert keys using linear probing.
When the table gets full, apply rehashing with table size 14.
Show the final table after rehashing.
S.Y. B. Tech IT Page No. 18 MMCOE, Pune