Sorting and Searching Algorithms Cheatsheet

# Sorting and Searching Algorithms Cheatsheet This cheatsheet provides a concise summary of the mechanisms and complexity analysis for common sorting and searching algorithms. ### Sorting Algorithms Sorting algorithms arrange elements in a specific order. #### **Bubble Sort** * **Mechanism:** Repeatedly compares and swaps adjacent elements if they are in the wrong order. Largest element "bubbles" up in each pass. * **Complexity:** * Average Time: $O(n^2)$ * Worst Time: $O(n^2)$ * Best Time: $O(n)$ (with optimization for already sorted data) * Space (Worst): $O(1)$ * **Stable:** Yes * **Notes:** Simple but inefficient for large datasets. Primarily educational. #### **Selection Sort** * **Mechanism:** Finds the minimum element from the unsorted portion and swaps it with the first element of the unsorted portion. * **Complexity:** * Average Time: $O(n^2)$ * Worst Time: $O(n^2)$ * Best Time: $O(n^2)$ * Space (Worst): $O(1)$ * **Stable:** No (typically) * **Notes:** Minimizes the number of swaps. Inefficient for large datasets. Not adaptive. #### **Insertion Sort** * **Mechanism:** Builds the final sorted array one item at a time. Takes elements from the input and inserts them into the correct position in the already sorted portion. * **Complexity:** * Average Time: $O(n^2)$ * Worst Time: $O(n^2)$ * Best Time: $O(n)$ (when input is already sorted) * Space (Worst): $O(1)$ * **Stable:** Yes * **Notes:** Simple. Efficient for small datasets or datasets that are mostly sorted (adaptive). Used in hybrid sorting algorithms. #### **Merge Sort** * **Mechanism:** A Divide and Conquer algorithm. Divides the array into two halves, recursively sorts them, and then merges the two sorted halves. * **Complexity:** * Average Time: $O(n \log n)$ * Worst Time: $O(n \log n)$ * Best Time: $O(n \log n)$ * Space (Worst): $O(n)$ (requires temporary array for merging) * **Stable:** Yes * **Notes:** Efficient and predictable performance. Stability is advantageous. Can be parallelized. Requires significant extra space. #### **Quick Sort** * **Mechanism:** A Divide and Conquer algorithm. Picks a pivot element, partitions the array around the pivot (elements smaller than pivot go left, larger go right), and recursively sorts the two partitions. * **Complexity:** * Average Time: $O(n \log n)$ * Worst Time: $O(n^2)$ (with poor pivot choices) * Best Time: $O(n \log n)$ * Space (Worst): $O(\log n)$ on average (recursion stack), $O(n)$ in worst case. * **Stable:** No (generally) * **Notes:** Often the fastest in practice due to low constant factors. Performance highly depends on pivot selection. #### **Heap Sort** * **Mechanism:** Uses a binary heap (typically a Max Heap). Builds a heap from the input array, then repeatedly extracts the maximum element (root) and places it at the end of the sorted portion, restoring the heap property. * **Complexity:** * Average Time: $O(n \log n)$ * Worst Time: $O(n \log n)$ * Best Time: $O(n \log n)$ * Space (Worst): $O(1)$ (in-place) * **Stable:** No * **Notes:** Provides guaranteed $O(n \log n)$ worst-case time with constant extra space. Can be seen as an optimized Selection Sort. #### **Counting Sort** * **Mechanism:** A non-comparison sort. Counts the frequency of elements within a specific range $[0, k]$. Uses these counts to determine the final position of each element in the sorted output array. * **Complexity:** * Average Time: $O(n+k)$ * Worst Time: $O(n+k)$ * Best Time: $O(n+k)$ * Space (Worst): $O(k)$ (for count array) * **Stable:** Yes (can be implemented stably) * **Notes:** Very efficient (linear time) when the range $k$ is not much larger than $n$. Not general purpose (requires integer keys in a limited range). Used as a subroutine in Radix Sort. #### **Radix Sort** * **Mechanism:** A non-comparison sort. Sorts elements by processing individual digits or characters, starting from either the least significant (LSD) or most significant (MSD). Uses a stable sorting algorithm (like Counting Sort) for each pass based on the current digit/character. * **Complexity:** * Average Time: $O(d \cdot (n+k))$ * Worst Time: $O(d \cdot (n+k))$ * Best Time: $O(d \cdot (n+k))$ * Space (Worst): $O(n+k)$ (depends on the stable sort subroutine) * **Stable:** Yes (if the underlying digit sort is stable) * **Notes:** Can be faster than $O(n \log n)$ sorts for certain data (large integers, fixed-length strings). Performance depends on the number of digits $d$ and the radix $k$. #### **Bucket Sort** * **Mechanism:** A non-comparison sort. Divides the input range into a number of "buckets". Distributes elements into buckets. Sorts elements within each bucket (often using Insertion Sort). Concatenates the sorted buckets. * **Complexity:** * Average Time: $O(n+k)$ (with uniform data distribution, $k$ is number of buckets) * Worst Time: $O(n^2)$ (if all elements fall into one bucket and $O(n^2)$ sort is used) * Best Time: $O(n+k)$ * Space (Worst): $O(n+k)$ (for buckets and elements) * **Stable:** Yes (if the internal bucket sort is stable) * **Notes:** Efficient for uniformly distributed data. Performance degrades on clustered data. ### Searching Algorithms Searching algorithms find a target element within a collection. #### **Linear Search (Sequential Search)** * **Data Structure:** Array, List (linear structures) * **Requirement:** None (works on unsorted data) * **Complexity:** * Average Time: $O(n)$ * Worst Time: $O(n)$ * **Notes:** Simplest search. Inefficient for large datasets. #### **Binary Search** * **Data Structure:** Sorted Array, Sorted List * **Requirement:** Data must be sorted. * **Complexity:** * Average Time: $O(\log n)$ * Worst Time: $O(\log n)$ * **Notes:** Highly efficient for large sorted datasets. Divide and Conquer approach. #### **Hashing (Hash Table Lookup)** * **Data Structure:** Hash Table * **Requirement:** A good hash function and collision resolution strategy. * **Complexity:** * Average Time: $O(1)$ * Worst Time: $O(n)$ (due to collisions) * **Notes:** Extremely fast average-case performance for lookups, insertions, and deletions. Widely used for dictionaries and sets. #### **Breadth-First Search (BFS)** * **Data Structure:** Graph, Tree * **Requirement:** Graph/Tree structure. * **Complexity:** * Average Time: $O(V+E)$ (V=vertices, E=edges) * Worst Time: $O(V+E)$ * **Notes:** Traverses layer by layer. Used to find the shortest path in unweighted graphs. #### **Depth-First Search (DFS)** * **Data Structure:** Graph, Tree * **Requirement:** Graph/Tree structure. * **Complexity:** * Average Time: $O(V+E)$ (V=vertices, E=edges) * Worst Time: $O(V+E)$ * **Notes:** Traverses as deep as possible along each branch before backtracking. Used in topological sorting, finding cycles. **Cheatsheet: Odd One Out Complexities (Revised)** This cheatsheet highlights the "odd one out" within common groups of sorting and searching algorithms based on their time and space complexities. **Big O Notation Quick Guide:** * `O(1)`: Constant time (fastest, doesn't grow with input) * `O(log n)`: Logarithmic time (grows slowly, often involves dividing the problem) * `O(n)`: Linear time (grows directly with input) * `O(n log n)`: Linearithmic time (efficient for sorting) * `O(n²)`: Quadratic time (grows quickly, often involves nested loops) **Space Complexity:** * `O(1)`: Constant space (uses a fixed amount of extra memory) * `O(log n)`: Logarithmic space (space grows slowly, often due to recursion depth) * `O(n)`: Linear space (space grows directly with input size, often requires extra arrays or data structures) --- | Category | Algorithms & Complexities (Typical) | Odd One Out | Reason | | :---------------------------- | :-------------------------------------------------------------------------------------------------- | :--------------- | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | **O(n²) Sorting Time Group** | Bubble Sort: Best `O(n)`, Avg/Worst `O(n²)` **Selection Sort: Best `O(n²)`**, Avg/Worst `O(n²)` Insertion Sort: Best `O(n)`, Avg/Worst `O(n²)` | **Selection Sort** | Within the common `O(n²)` group, Bubble Sort and Insertion Sort can achieve a better, linear time complexity (`O(n)`) in the best-case scenario (when the array is already sorted). Selection Sort, however, **always performs `O(n²)` comparisons** regardless of the initial order, making its best case the same as its average and worst case. | | **O(n log n) Sorting Time Group** | Merge Sort: Best/Avg/Worst `O(n log n)` **Quick Sort: Worst `O(n²)`**, Best/Avg `O(n log n)` Heap Sort: Best/Avg/Worst `O(n log n)` | **Quick Sort** | While Merge Sort and Heap Sort consistently have `O(n log n)` time complexity across all cases (best, average, worst), Quick Sort has a **worst-case time complexity of `O(n²)`**. This occurs with poor pivot selection, leading to unbalanced partitions. | | **Sorting Space (Across Groups)**| Bubble Sort: `O(1)` Selection Sort: `O(1)` Insertion Sort: `O(1)` Quick Sort: `O(log n)` avg, `O(n)` worst Heap Sort: `O(1)` **Merge Sort: `O(n)`** | **Merge Sort** | Most common comparison sorts (`O(n²)` and Heap Sort from the `O(n log n)` group) are **in-place** or use `O(1)` extra space. Quick Sort uses space for the recursion stack (`O(log n)` average, `O(n)` worst). Merge Sort, however, consistently requires **`O(n)` auxiliary space** for its merging process. | | **Searching Time (Unsorted Data)** | Linear Search: `O(n)` (Other efficient searches require sorted data) | **Linear Search**| When data is not sorted, you generally have to **check each element one by one** in the worst case (`O(n)`) to find what you're looking for. More efficient search algorithms rely on the data being in order to quickly eliminate possibilities. | | **Searching Time (Sorted Data)** | **Binary Search: `O(log n)`** Linear Search: `O(n)` | **Binary Search**| On sorted data, Linear Search is still `O(n)` in the worst case. Binary Search, by repeatedly **halving the search interval**, can find an element much faster, in `O(log n)` time. | | **Searching Space** | Linear Search: `O(1)` Binary Search: `O(1)` | **None** | Both fundamental searching algorithms (Linear and Binary Search) are **in-place** and only require a constant amount of extra space (`O(1)`) to store variables like indices or pointers. There isn't a common searching algorithm that stands out with significantly higher space complexity in typical scenarios. | --- This revised version aligns with finding the "odd one out" specifically within the commonly grouped sorting algorithms based on their typical performance classes and space requirements. Hopefully, this makes the distinctions clearer and easier to remember!