This section focuses on the fundamentals of sorting and searching techniques with explanations and links to practice problems.

Sorting Algorithms:

  1. Bubble Sort
    • Description: Repeatedly swaps adjacent elements if they are in the wrong order.
    • Time Complexity: O(n²)
    • Practice Problems:
      • Sort an array of 0s, 1s, and 2s.
  2. Merge Sort
    • Description: Divides the array into halves, sorts each half, and merges them.
    • Time Complexity: O(n log n)
    • Practice Problems:
      • Count inversions in an array.
  3. Quick Sort
    • Description: Select a pivot and partition the array around it.
    • Time Complexity: O(n log n) (average case)
    • Practice Problems:
      • Find the kth smallest/largest element in an array.
  4. Heap Sort
    • Description: Uses a binary heap to sort elements.
    • Time Complexity: O(n log n)
    • Practice Problems:
      • Sort an array using heap operations.

Searching Algorithms:

  1. Linear Search
    • Description: Traverses each element sequentially.
    • Time Complexity: O(n)
    • Practice Problems:
      • Find the first occurrence of an element in an array.
  2. Binary Search
    • Description: Repeatedly divides the search interval in half.
    • Time Complexity: O(log n)
    • Practice Problems:
      • Search an element in a rotated sorted array.
  3. Depth First Search (DFS) and Breadth First Search (BFS)
    • Description: DFS explores as deep as possible; BFS explores level by level.
    • Time Complexity: O(V + E) (for graphs)
    • Practice Problems:
      • Find connected components in a graph.
      • Detect cycles in a directed graph.

Advanced Searching Techniques:

  1. Ternary Search
    • Description: Divides the array into three parts for optimization problems.
    • Practice Problems:
      • Find the maximum/minimum of a unimodal function.
  2. Jump Search
    • Description: Jumps ahead by fixed steps and performs a linear search within a block.
    • Time Complexity: O(√n)
    • Practice Problems:
      • Find a specific element in a large sorted array.
  3. Exponential Search
    • Description: Useful for unbounded or infinite arrays.
    • Practice Problems:
      • Search an element in an infinite sorted array.