Notes on Searching and Sorting Algorithms

Searching Algorithms

Searching algorithms are procedures used to find a specific item within a collection of data. Common types include:

  1. Linear Search
  2. Binary Search
  3. Hashing
  4. Interpolation Search
  5. Tree-based Searching
  6. Ternary Search
  7. Jump Search
  8. Exponential Search
  9. Fibonacci Search
  10. Interpolation Search for Trees
  11. Hash-based Searching (e.g., Bloom Filter)
  12. String Searching Algorithms

Linear Search

  • A sequential search algorithm that examines each element until it finds the target or reaches the end of the collection.
  • If found, it returns the index; if not found, it returns -1.
  • Example: In the array {10, 50, 30, 70}, searching for 30 results in the index 2.
  • Algorithm Steps:
  1. Start at the first element and compare with the target.
  2. If equal, return the index. If not, proceed to the next element.
  3. If no match is found by the end, return -1.
  • Time Complexity:
  • Best Case: O(1)
  • Worst/Average Case: O(N)
  • Advantages: Works on any data type, no extra memory required, simple implementation.
  • Disadvantages: Slow for large datasets.
  • Use Cases: Effective for small datasets or unordered data.

Binary Search

  • A more efficient algorithm than linear search, applicable only on sorted arrays.
  • Implements a divide and conquer strategy by comparing the target to the middle element, recursively searching the appropriate half.
  • Key Steps:
  1. Calculate the middle index.
  2. If the mid element is equal to the target, return the index.
  3. If it's greater, repeat for the left half; if less, repeat for the right half.
  • Time Complexity:
  • Best Case: O(1)
  • Average/Worst Case: O(log N)
  • Advantages: Significantly faster than linear search for large datasets.
  • Disadvantages: Requires sorted data.

Sorting Algorithms

Sorting algorithms arrange elements in a specified order. Common types include:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort

Bubble Sort

  • Repeatedly swaps adjacent elements if they are in the wrong order.
  • Average time complexity is high, making it unsuitable for larger datasets.
  • Can detect if the input is already sorted.

Selection Sort

  • Selects the smallest element from the unsorted portion and places it at the beginning.
  • Advantages: Simple implementation, works well on small datasets.
  • Disadvantages: Inefficient for larger lists.

Insertion Sort

  • Builds a sorted array one element at a time by repeatedly placing the next element in its correct position.
  • Time Complexity: Perform well on small data sets but not efficient on large lists.

Merge Sort

  • A divide and conquer algorithm that divides the array into halves, sorts them, and merges the sorted halves back together.
  • Efficient for large datasets.

Quick Sort

  • Selects a pivot and partitions the array around it; recursively sorts the partitions.
  • Generally faster than other algorithms but unstable and sensitive to the choice of pivot.