DATA STRUCTURES

UNIT – 3

SORTING AND SEARCHING

BUBBLE SORT – SELECTION SORT – INSERTION SORT – MERGE SORT – QUICK SORT
– LINEAR SEARCH – BINARY SEARCH – HASHING – HASH FUNCTIONS – COLLISION
HANDLING – LOAD FACTORS, REHASHING, AND EFFICIENCY- HASH TABLE
IMPLEMENTATION IN PYTHON.

[Link] SORT:

Bubble sort is a simple sorting algorithm that repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order. The
algorithm continues iterating through the list until no swaps are needed, indicating
that the list is sorted. The larger elements gradually "bubble" to the top or end of the
list, hence the name.
Here's a more detailed explanation:

How it works:
1. 1. Comparison:
Bubble sort compares each pair of adjacent elements in the list.
2. 2. Swapping:
If the elements are in the wrong order (e.g., in ascending order, the left element is
greater than the right element), they are swapped.
3. 3. Iteration:
This comparison and swapping process is repeated for the entire list, from the
beginning to the end.
4. 4. Pass:
Each complete pass through the list ensures that the largest unsorted element
"bubbles" up to its correct position at the end of the list.
5. 5. Repetition:
The algorithm continues with these passes until no more swaps are needed,
indicating that the list is fully sorted.
Example:
Let's say you have the list: ``
1. 1. Pass 1:
 Compare 5 and 1. Swap. List becomes: ``
 Compare 5 and 4. Swap. List becomes: ``
 Compare 5 and 2. Swap. List becomes: ``
 Compare 5 and 8. No swap. List remains: ``
 After pass 1, the largest element, 8, is in its correct position.
2. 2. Pass 2:
 Compare 1 and 4. No swap.
 Compare 4 and 2. Swap. List becomes: ``
 Compare 4 and 5. No swap.
 After pass 2, 5 is also in its correct position.
3. 3. Pass 3:
 Compare 1 and 2. No swap.
 Compare 2 and 4. No swap.
 After pass 3, 4 is also in its correct position.
4. 4. Pass 4:
 Compare 1 and 2. No swap.

 After pass 4, 2 is also in its correct position.

The list is now sorted: ``

Advantages:
Simple to understand and implement and Easy to code.

Disadvantages:
 Inefficient for large datasets. The time complexity in the average and worst cases is
O(n^2), making it slow for large lists.
 Not suitable for real-time applications where performance is critical.

2. SELECTION SORT:

Selection sort is a simple comparison-based sorting algorithm that divides the input
list into a sorted and an unsorted portion. It repeatedly selects the smallest (or largest,
depending on the order) element from the unsorted sublist and swaps it with the first
element of the unsorted sublist. This process is repeated until the entire list is sorted.

Here's a breakdown:
 How it works:
 The algorithm iterates through the list, finding the minimum element in the
unsorted portion and placing it at the beginning of the sorted portion.
 Time Complexity:
Selection sort has a time complexity of O(n^2) in all cases (best, average, and
worst), making it less efficient for large datasets.
 Space Complexity:
It has a space complexity of O(1) because it sorts the array in place without
requiring additional memory proportional to the input size.
 Advantages:
It's simple to understand and implement, making it suitable for educational
purposes and small datasets. It also requires a minimal number of swaps compared
to some other algorithms.
 Disadvantages:
Its quadratic time complexity makes it slow for large datasets.
 Use Cases:
Selection sort is often used for teaching basic sorting concepts, for small datasets,
or in scenarios where memory usage is a major constraint.

3. INSERTION SORT:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list)
one item at a time. It works by taking each element from the unsorted portion of the
input and inserting it into its correct position within the already sorted portion. This
process is repeated until all elements are sorted.

How it works:
1. 1. Divide:
The input is conceptually divided into a sorted and an unsorted portion. Initially,
the first element is considered sorted, and the rest are unsorted.
2. 2. Iterate:
The algorithm iterates through the unsorted portion, taking one element at a time.
3. 3. Compare and Insert:
 Each element is compared with the elements in the sorted portion, moving larger
elements to the right to create space for the current element's correct insertion.
4. 4. Repeat:
This process of comparison and insertion is repeated until all elements are moved
from the unsorted portion to the sorted portion.
Example:
Let's say you have the unsorted array: ``.
1. `` is considered sorted.
2. 1 is compared with 5. Since 1 is smaller, it's placed before 5: ``.
3. 4 is compared with 5, then with 1. It's placed between them: ``.
4. 2 is compared with 5, 4, and 1. It's placed before 4: ``.
5. 8 is compared with 5, 4, 2, and 1. It's placed after 5: ``.
Key Characteristics:
 Simple to understand and implement: Insertion sort is one of the easiest sorting
algorithms to grasp and code.
 Efficient for small datasets: It performs well on small input sizes or nearly sorted
data.
 In-place sorting: Insertion sort sorts the array in place, meaning it doesn't require
extra memory for sorting.
 Adaptive: If the input is already partially sorted, insertion sort can be quite efficient.
 Time Complexity:
o Best case: O(n) when the input is already sorted.
o Average and Worst case: O(n^2) where 'n' is the number of elements.
 Space Complexity: O(1).
 4. MERGE SORT:

Merge sort is a highly efficient sorting algorithm that follows the "divide and
conquer" paradigm. It recursively breaks down an array into smaller subarrays until
each subarray contains only one element (which is inherently sorted). Then, it
repeatedly merges these subarrays to produce new sorted subarrays until the entire
input array is sorted.
Here's a breakdown of the process:
1. Divide: The input array is divided into two halves (approximately equal in size)
recursively until you have subarrays of size 1.
2. Conquer: Each subarray of size 1 is considered sorted by definition.
3. Merge: The sorted subarrays are merged in a sorted manner to create larger sorted
subarrays. This merging step is crucial and involves comparing elements from the
subarrays and placing them in the correct order into a new, larger sorted array.

Example:
Let's say you have the array ``.
1. Divide: The array is split into `` and ``. These are further split until you have ``, ``, ``,
``, ``, ``, and ``.
2. Conquer: All single-element arrays are considered sorted.
3. Merge:
o `` and `` are merged to get ``.

o `` and `` are merged to get ``.

o `` and `` are merged to get ``.
o `` is merged with nothing.
o `` and `` are merged to get ``.
o `` and `` are merged to get ``.
o Finally, `` and `` are merged to get the fully sorted array ``.
Key Characteristics:
 Time Complexity:
Merge sort has a time complexity of O(n log n) in all cases (best, average, and
worst), making it a very efficient sorting algorithm for large datasets.
 Space Complexity:
Merge sort has a space complexity of O(n) because it requires extra space to store
the temporary merged subarrays.
 Stability:
Merge sort is a stable sorting algorithm, meaning that it preserves the relative order
of equal elements.
 5. QUICK SORT:

Quick sort is a highly efficient, comparison-based sorting algorithm that uses a

divide-and-conquer approach. It works by selecting a "pivot" element from the array
and partitioning the other elements into two sub-arrays based on whether they are
less than or greater than the pivot. These sub-arrays are then recursively sorted, and
the process continues until the entire array is sorted.
Here's a breakdown of how Quick Sort works:

1. Choose a Pivot:
 An element from the array is selected as the pivot. The choice of pivot can affect
performance, with common strategies including the first element, last element, a
random element, or the median.
2. Partition the Array:
 The array is rearranged such that all elements less than the pivot are placed before it,
and all elements greater than the pivot are placed after it. The pivot is now in its
correct sorted position.
3. Recursively Sort Sub-arrays:
 The same process (choosing a pivot and partitioning) is applied to the sub-arrays on
either side of the pivot. This continues recursively until each sub-array contains only
one element (which is inherently sorted).
Key Concepts:
 Divide and Conquer:
Quick sort breaks down the sorting problem into smaller, more manageable sub-
problems (the sub-arrays).
 In-place Sorting:
Quick sort can be implemented to sort the array in-place, meaning it requires
minimal extra memory (beyond what's needed for the recursion stack).
 Comparison-based:
Quick sort compares elements to determine their relative order, making it suitable
for sorting various data types.
 Not Stable:
Quick sort doesn't guarantee the preservation of the original order of equal
elements.
 Best and Average Case Complexity:
 Best and Average Case:
O(n log n) - This makes quicksort a very efficient algorithm, especially for large
datasets.
 Worst Case:
O(n^2) - This occurs when the pivot selection consistently results in unbalanced
partitions (e.g., always choosing the smallest or largest element as the pivot).
Example:
Let's say you have the array: ``.
1. Pivot: Choose 7 as the pivot.
2. Partition: The array becomes ``.
3. Recursively sort: Now, quicksort is applied to `` and ``. This process continues until
the entire array is sorted.

6. LINEAR SEARCH:

Linear search, also known as sequential search, is a simple algorithm used to find a
specific value within a list or array. It works by examining each element of the list
one by one, starting from the beginning, until the desired value is found or the end of
the list is reached.

How it works:
1. Start: Begin at the first element of the list.
2. Compare: Compare the current element with the target value.
3. Match: If the current element matches the target value, the search is successful, and
the index of the element is returned.
4. Advance: If the current element does not match, move to the next element in the
list.
5. Repeat: Repeat steps 2-4 until either a match is found or the end of the list is
reached.
6. Not Found: If the end of the list is reached without finding a match, the search is
unsuccessful, and a special value (e.g., -1) is often returned to indicate that the
element was not found.
Key Characteristics:
 Simplicity: Linear search is easy to understand and implement.
 No need for sorting: It can be used on both sorted and unsorted lists.
 Inefficiency for large datasets: It can be slow for large lists, as it may need to
examine every element.
 Time complexity: The time complexity of linear search is O(n), where n is the
number of elements in the list, meaning the number of steps it takes to find an
element grows linearly with the size of the list.

Practical Applications:
 Small datasets:
Linear search is suitable for smaller lists or when the data is not sorted and
efficiency is not a major concern.
 Real-world examples:
Finding a specific book in a small, unsorted collection, or searching for a specific
item in a small inventory.

7. BINARY SEARCH:

Binary search is an efficient algorithm for finding the position of a target value
within a sorted array. It works by repeatedly dividing the search interval in half. This
makes it significantly faster than a linear search, especially for large datasets.

How Binary Search Works:

1. 1. Sorted Array Requirement:
Binary search can only be applied to sorted arrays (either ascending or descending
order).
2. 2. Divide and Conquer:
The algorithm starts by examining the middle element of the array.
3. 3. Comparison:
 If the middle element matches the target value, the search is successful, and the
index of the middle element is returned.
 If the target value is less than the middle element, the search continues in the left
half of the array.
 If the target value is greater than the middle element, the search continues in the
right half of the array.
4. 4. Repeat:
Steps 2 and 3 are repeated on the reduced search interval until the target is found or
the interval becomes empty.
Example:
Let's say you're searching for the number 15 in the sorted array ``.
1. The middle element is 11 (at index 4). Since 15 > 11, the search continues in the
right half: ``.
2. The new middle element is 15 (at index 6). The target is found, and the index 6 is
returned.
Time Complexity:
Binary search has a time complexity of O(log n), where n is the number of elements
in the array. This logarithmic complexity makes it very efficient for large datasets.

Key Benefits:
 Efficiency:
Binary search is significantly faster than linear search for large sorted arrays.
 Widely Applicable:
It's a fundamental algorithm used in various applications, including databases,
search engines, and more.
 8. HASHING:

Hashing in data structures is a technique used to map keys to specific indices in a

hash table (an array) for efficient data storage and retrieval. It involves using a hash
function to convert keys into hash codes (indices), enabling fast access to the
corresponding data.
Here's a breakdown of key concepts:

1. Hash Function:
 A hash function takes a key (which can be of any size) and transforms it into a fixed-
size integer (hash code).
 The goal is to distribute keys evenly across the hash table to minimize collisions.
 A good hash function should be easy to compute and minimize collisions.
2. Hash Table:
 A hash table is an array that stores data items, with each item associated with a
unique index (hash code) calculated by the hash function.
 It provides fast average-case performance for insertion, deletion, and search
operations (often O(1) complexity).
3. Collisions:
 Collisions occur when two different keys generate the same hash code, resulting in
them potentially wanting to occupy the same index in the hash table.
 Various techniques are used to resolve collisions, including:
o Chaining: Storing multiple items that hash to the same index in a linked list or other
data structure at that index.
o Open Addressing: Finding an alternative empty slot in the hash table when a
collision occurs, using methods like linear probing, quadratic probing, or double
hashing.
4. Applications:
 Databases:
Hashing is fundamental for indexing and fast data retrieval in databases.
 Symbol Tables:
Used in compilers and interpreters for storing variables and their associated
information.
 Caching:
Hashing is used to store frequently accessed data in cache memory for faster
access.
 Password Storage:
While not directly storing passwords in plain text, hashing is used to generate a
unique hash of the password which is stored instead.
 Digital Signatures:
 Hashing is used to create a message digest (a fixed-size representation of the
original data) which is used in combination with digital signatures for
authentication and verification.

5. Types of Hash Functions:

 Division Method:
The most common method, where the key is divided by the table size and the
remainder is used as the index (k mod m).
 Multiplication Method:
Involves multiplying the key by a constant, extracting the fractional part, and then
multiplying that fractional part by the table size.
 Universal Hashing:
A randomized approach where the hash function is chosen randomly from a family
of hash functions, ensuring good performance on average.
6. Important Considerations:
 Choosing a good hash function is crucial for performance. A poorly designed
hash function can lead to frequent collisions and degrade performance.
 Hashing provides excellent average-case performance but can have poor worst-
case performance if collisions are not handled well.

9. HASH FUNCTIONS:

Hash functions are essential components of hash tables in data structures. They map
data of arbitrary size to a fixed-size value, called a hash, which is then used to index
a data structure like an array. This process, known as hashing, allows for efficient
insertion, deletion, and retrieval of data.

Here's a breakdown of how hash functions work in data structures:

1. Hashing:
A hash function takes an input (key) and applies a mathematical formula to it,
producing a hash value (or hash code). This hash value acts as an index for storing
or retrieving data in a hash table.
2. Hash Table:
 The hash table is a data structure that uses the hash values generated by the hash
function to store and access data items. It's typically implemented as an array,
where each index corresponds to a hash value.

3. Collision Handling:
A collision occurs when two different keys produce the same hash value. Various
techniques, like separate chaining or open addressing, are used to handle these
collisions and ensure data integrity.
4. Efficiency:
Hashing, facilitated by hash functions, can achieve an average time complexity of
O(1) for basic operations like insertion, deletion, and search, making it highly
efficient for large datasets.
5. Example:
If you have a set of key-value pairs (e.g., employee ID and name), the hash
function would map each employee ID to a specific index in the hash table, where
the corresponding employee's name would be stored.
Types of Hash Functions:
 Modular Hashing: Uses the modulus operator (%) to calculate the hash value.
 Multiplicative Hashing: Involves multiplication and bitwise operations.
 Universal Hashing: Uses a family of hash functions to reduce the likelihood of
collisions.
Key aspects of a good hash function:
 Uniform Distribution: It should distribute hash values evenly across the hash table
to minimize collisions.
 Efficiency: It should be computationally inexpensive to calculate.
 Deterministic: For the same input, it should always produce the same hash value.
In essence, hash functions are the engine that drives the efficiency of hash
tables, enabling rapid access to data in various applications, from databases to
caching systems.

10. COLLISION HANDLING:

Collision handling in data structures, particularly in hash tables, is the process of
resolving situations where two or more different keys map to the same index within
the table. Since hash functions cannot always guarantee unique outputs for all
 possible inputs, collisions are a common occurrence, and efficient handling is crucial
for maintaining data integrity and performance.
Here's a breakdown of collision handling:

Collision:
 A collision happens when a hash function produces the same index for two or more
distinct keys.
 This means multiple data items want to occupy the same slot in the hash table.

Collision Handling Important:

 Performance:
If collisions are not handled properly, searching, insertion, and deletion operations
can degrade to linear time complexity (O(n)), negating the benefits of hashing
(ideally O(1)).
 Data Integrity:
Incorrect collision handling can lead to data loss or incorrect results when accessing
or modifying data.
3. Common Collision Handling Techniques:
 Separate Chaining:
 Each slot in the hash table points to a linked list (or other data structure) that holds
all the elements that hash to that particular index.
 When a collision occurs, the new element is added to the linked list at that index.
 Pros: Relatively simple to implement, handles a large number of collisions
efficiently.
 Cons: Requires extra memory for the linked lists, can lead to longer search times if
many collisions occur at the same index.
 Open Addressing:
 All elements are stored directly within the hash table itself.
 When a collision occurs, alternative slots are probed (searched) until an empty slot
is found.
 Types of Open Addressing:
 Linear Probing: Examines consecutive slots (e.g., (hash + 1), (hash + 2), etc.).
 Pros: Simple to implement, good cache performance.
 Cons: Prone to "clustering," where collisions lead to long sequences of occupied
slots, slowing down searches.
 Quadratic Probing: Probes slots at increasing quadratic intervals (e.g., (hash + 1),
(hash + 4), (hash + 9), etc.).
 Pros: Reduces primary clustering compared to linear probing.
 Cons: Still can suffer from clustering and may not explore all slots.
 Double Hashing: Uses a second hash function to determine the probe sequence.
 Pros: Reduces clustering and distributes elements more evenly.
 Cons: Slightly more complex to implement.
 Deleted Slots: In open addressing, deleting an element requires special
handling. Simply removing the element can cause search failures. Deleted slots are
often marked as "deleted" and can be reused for insertions.

4. Choosing a Collision Handling Technique:

 The choice depends on factors like the expected frequency of collisions, the size of
the hash table, and the importance of search performance.
 Separate chaining is often preferred when dealing with a large number of potential
collisions or when dynamic resizing is needed.
 Open addressing, particularly double hashing, can be suitable when memory is
limited and collisions are relatively infrequent.

11. LOAD FACTORS:

In data structures, especially hash tables, load factor is a metric that indicates how
full the structure is. It's the ratio of the number of elements stored to the total
capacity of the structure (usually the number of buckets in a hash table). A higher
load factor means the structure is more full, potentially leading to more collisions
and slower operations.
Here's a more detailed breakdown:

Definition:
 Load factor = (Number of elements) / (Total capacity) or (Number of elements) /
(Number of buckets)
 For example, if a hash table has 10 elements and 20 buckets, the load factor is 0.5 (or
50%).
Why it's important:
 Performance:
Load factor directly impacts the performance of hash table operations (like
insertion, deletion, and search). A high load factor (close to 1) means more
elements are likely to be stored in the same bucket (collision), increasing the time
complexity of these operations.
 Efficiency:
 A low load factor means wasted space, while a high load factor means more
collisions. Finding the right balance is key for efficient use of space and time.

 Rehashing:
When the load factor exceeds a certain threshold, rehashing (resizing the hash table
and redistributing the elements) is often triggered to maintain optimal
performance, according to [Link] and Scaler Blog.
Typical Load Factor:
 A common default load factor for hash tables is 0.75 (or 75%), according to
[Link] and Scaler Blog.
 This means that when the hash table is about 75% full, it will be resized and
rehashed.
Example:
 If a hash table has an initial capacity of 16, and you insert 12 elements, the load
factor is 12/16 = 0.75. If you insert the 13th element, the load factor becomes 13/16
= 0.8125, which might trigger a resize, according to Scaler Blog.

12. REHASHING:

Rehashing in data structures, specifically hash tables, is the process of resizing the
table and redistributing its elements when the load factor (ratio of elements to table
size) becomes too high, impacting performance. It's triggered when the table is
nearing its capacity, causing slower insertion, deletion, and search operations.

How Rehashing Works:

1. 1. Load Factor Check:
The hash table monitors its load factor. This is the number of stored elements
divided by the total number of buckets (slots) in the table.
2. 2. Threshold Trigger:
When the load factor exceeds a predefined threshold (often around 0.7 or 0.8),
rehashing is initiated.
3. 3. New Table Creation:
A new hash table is created, usually with double the number of buckets as the
original.
4. 4. Re-Hashing:
 Each element from the old table is re-hashed using the new table's size (calculated
using the hash function) and re-inserted into the new table.

5. 5. Old Table Replacement:

The old hash table is discarded, and the new, larger table becomes the active one.
Purpose of Rehashing:
 Maintain Efficiency:
By resizing the table, rehashing ensures a low load factor, which helps maintain the
average time complexity of hash table operations (insertion, deletion, search) close
to O(1) (constant time).
 Avoid Performance Degradation:
Without rehashing, as the hash table fills up, collisions (multiple elements mapping
to the same bucket) increase, leading to slower operations and potentially O(n)
(linear time) performance in worst-case scenarios.

13. EFFICIENCY:

Data structure efficiency refers to how well a data structure performs operations like
searching, insertion, and deletion, impacting the overall performance of algorithms
and software. It's evaluated based on time complexity (how fast operations are) and
space complexity (how much memory is used). Efficient data structures minimize
resource usage and maximize speed, leading to better algorithm performance and a
more responsive user experience, according to a Lenovo article.
Key aspects of data structure efficiency:
 Time Complexity:
Measures how execution time grows with input size. For example, searching in a
sorted array using binary search has logarithmic time complexity, while searching
in an unsorted array sequentially has linear complexity.
 Space Complexity:
Measures how much memory a data structure uses. Efficient data structures
minimize memory consumption, especially when dealing with large datasets.
 Scalability:
A scalable data structure can handle growing datasets without significant
performance degradation. This is crucial for applications that need to adapt to
increasing data volume, says a LinkedIn article .
 Choice of Data Structure:
Different data structures excel at different operations. For instance, hash tables
offer fast lookups, while trees provide efficient sorting and searching capabilities.
 Algorithmic Optimization:
Choosing the right data structure is crucial for optimizing algorithms. By
leveraging the strengths of each data structure, developers can create faster and
more efficient programs.
 Implementation Details:
 Factors like programming language, compiler choice, and specific implementation
can also influence efficiency.

14. HASH TABLE IMPLEMENTATION IN PYTHON:

A hash table, also known as a hash map, is a data structure that stores key-value
pairs. It uses a hash function to compute an index into an array of buckets or slots,
from which the desired value can be found. Python's built-in dictionaries are
implemented as hash tables.

Core Components and Implementation Principles:

 Buckets (Array):
The underlying storage for a hash table is typically an array of a fixed size. Each
element in this array is a "bucket" where key-value pairs are stored.
 Hash Function:
A hash function takes a key as input and produces an integer, called a hash code or
hash value. This hash code is then used to determine the index within the array
where the key-value pair should be stored. The goal of a good hash function is to
distribute keys evenly across the buckets to minimize collisions.
 Collision Resolution:
A collision occurs when two different keys hash to the same index. Hash tables
employ strategies to handle these collisions:
 Separate Chaining: Each bucket stores a linked list (or another data structure like
another hash table) of key-value pairs that hash to that index. When a collision
occurs, the new key-value pair is added to the linked list at that bucket.
 Open Addressing: Instead of using separate lists, all elements are stored directly
within the array. When a collision occurs, the algorithm probes for the next
available slot according to a predefined sequence (e.g., linear probing, quadratic
probing, double hashing).
Basic Operations:
 Insertion (put):
 Compute the hash of the key.
 Use the hash to determine the bucket index.
 If a collision resolution strategy is needed, apply it (e.g., add to linked list in
chaining, find next available slot in open addressing).
 Store the key-value pair in the designated bucket.
 Retrieval (get):
 Compute the hash of the key.
 Use the hash to determine the bucket index.
 Search within the bucket (e.g., traverse the linked list in chaining, probe for the key
in open addressing) to find the corresponding value.
 Deletion (remove):
 Compute the hash of the key.
 Use the hash to determine the bucket index.
 Locate and remove the key-value pair from the bucket.
Python's Dictionaries and Sets:
Python's built-in dict and set types are highly optimized implementations of hash
tables. They handle hashing, collision resolution, and resizing automatically, making
them the preferred choice for most scenarios where hash table functionality is
required. Implementing a custom hash table in Python is primarily for educational
purposes or for very specific performance requirements that deviate from the
general-purpose optimizations provided by built-in types.