Searching, Sorting, and Hashing Techniques Study Guide

Fundamentals of Searching Techniques

Definition of Searching: * Searching is the process of finding the location of a specific element (referenced as the "key") within a given set of data or a collection of elements. The result of a search operation is typically the index or memory address of the item if it is present, or a null/error value indicating the item was not found.
Linear Search: * Linear Search, also known as Sequential Search, is the simplest searching algorithm. * It works by starting from the very first element of a data structure (like an array or list) and comparing it with the target key. * The process continues sequentially, checking each subsequent element one by one until either a match is found or the end of the collection is reached. * It does not require the data to be sorted to function correctly.
Binary Search: * Binary Search is an efficient searching algorithm that operates on the "divide and conquer" principle. * Prerequisite: The input collection must be in sorted order (either ascending or descending). * Mechanism: The algorithm compares the target key with the middle element of the array. If the key matches the middle element, the search is successful. If the key is smaller than the middle element, the search continues in the lower half; if it is larger, the search continues in the upper half. This effectively halves the search space with every iteration.
Advantages of Binary Search over Linear Search: * Efficiency: Binary Search is significantly faster for large datasets. Its time complexity is $O(\log(n))$ , whereas Linear Search is $O(n)$ . * Reduced Comparisons: For a list of $n$ elements, Linear Search might require up to $n$ comparisons, while Binary Search requires at most $\log_2(n)$ comparisons.

Sorting Algorithms and Methodology

Definition of Sorting: * Sorting is the process of arranging elements in a specific logical order, typically numerical or lexicographical (alphabetical). This ordering can be in ascending order (smallest to largest) or descending order (largest to smallest).
Bubble Sort: * Bubble Sort is a simple, comparison-based sorting algorithm where each pair of adjacent elements is compared and swapped if they are in the wrong order. * This process is repeated through multiple passes over the list. In each pass, the largest unsorted element "bubbles up" to its correct position at the end of the list.
Selection Sort: * Working Principle: Selection Sort works by repeatedly finding the minimum element (for ascending order) from the unsorted part of the list and putting it at the beginning. * The algorithm maintains two sub-arrays in a given array: one which is already sorted and the remaining part which is unsorted. In every iteration, the smallest element from the unsorted sub-array is picked and moved to the sorted sub-array.
Insertion Sort: * Working Principle: Insertion Sort builds the final sorted array one item at a time. It functions similarly to the way you might sort playing cards in your hands. * Mechanism: The algorithm takes one element from the unsorted portion and finds its correct position within the already sorted portion, shifting other elements as necessary. * Example: Consider the array $[12, 11, 13, 5, 6]$ . * The algorithm starts at the second element ( $11$ ). Since $11 < 12$ , it shifts $12$ and inserts $11$ at the front: $[11, 12, 13, 5, 6]$ . * Next is $13$ , which is already in the correct place relative to $11$ and $12$ . * Then $5$ is compared, shifting $13, 12, 11$ to place $5$ at the very beginning.
Shell Sort: * Shell Sort is an optimization of Insertion Sort that allows the exchange of items that are far apart. * The Role of the Gap: The "gap" (or increment) is a sequence used to determine which elements are compared. Instead of comparing adjacent elements (gap of $1$ ), Shell Sort starts with a larger gap and gradually reduces it to $1$ . * Purpose of the Gap: Using a gap improves performance by move elements towards their final positions faster than standard insertion sort, reducing the total number of shifts required in the final stages.
Merge Sort: * Merge Sort is a recursive, stable, and comparison-based sorting algorithm based on the Divide and Conquer paradigm. * Mechanism: It divides the unsorted list into $n$ sub-lists, each containing one element (a list of one element is considered sorted). It then repeatedly merges these sub-lists to produce new sorted sub-lists until there is only one remaining. * Time Complexity: The time complexity of Merge Sort is consistently $O(n \log(n))$ for the worst, average, and best cases.

Hashing Techniques and Collision Resolution

Definition of Hashing: * Hashing is a technique used to uniquely identify a specific object from a group of similar objects. It maps data of arbitrary size to fixed-size values (hash codes) using a formula, allowing for very fast data retrieval.
Hash Function: * A Hash Function is a mathematical function that takes an input (or 'key') and returns a fixed-size string or integer, which represents the index in the hash table where the data item should be stored. * A good hash function should distribute keys uniformly across the table to minimize collisions.
Collision in Hashing: * A collision occurs when two different keys, when processed by the same hash function, result in the same hash value (index). * Since a single slot in a hash table can usually only hold one piece of data, a strategy must be employed to resolve these conflicts.
Separate Chaining: * Separate Chaining is a collision resolution technique where the hash table is implemented as an array of linked lists (or other containers). * If multiple keys hash to the same index, those keys are stored together in a linked list attached to that specific index slot.
Open Addressing: * Open Addressing is a collision resolution method in which all elements are stored within the hash table itself (no external lists). When a collision occurs, the algorithm searches for the next available "open" slot in the array based on a specific probe sequence. * Types of Open Addressing: 1. Linear Probing: The algorithm searches for the next slot linearly (index $i+1, i+2, \dots$ ). 2. Quadratic Probing: The interval between probes increases quadratically (index $i+1^2, i+2^2, \dots$ ). 3. Double Hashing: A second hash function is used to determine the step size for the probe sequence.
Rehashing: * Rehashing is the process of increasing the size of the hash table (typically doubling it) and re-mapping all existing elements to new positions in the larger table. This is done when the table becomes too full (the load factor exceeds a certain threshold), which helps maintain efficient search and insertion times.
Extendible Hashing: * Extendible Hashing is a dynamic hashing technique used in databases and file systems where the hash table (directory) grows or shrinks as the number of records changes. It uses a directory and buckets, where the directory entries point to the buckets. It avoids the need to rehash the entire database at once by only splitting individual buckets as they overflow.