Which of the following algorithms follows the divide and conquer paradigm?

The correct answer is Option 2) Quick sort.

Key Points

• Quick Sort is a classic example of the Divide and Conquer paradigm.
• It works by:
  1. Selecting a pivot element from the array.
  2. Dividing the array into two sub-arrays:
     • Elements less than the pivot
     • Elements greater than the pivot
  3. Recursively applying the same process to the sub-arrays.
• This recursive division into smaller problems and combining results characterizes the divide and conquer strategy.

Additional Information

• Option 1 – Bubble Sort: Simple comparison-based algorithm; does not follow divide and conquer.
• Option 3 – Depth-first Search: A graph traversal algorithm; not based on divide and conquer.
• Option 4 – Selection Sort: Picks the smallest/largest element each time; not recursive or divided.
• Other Divide and Conquer algorithms:
  • Merge Sort
  • Binary Search
  • Strassen’s Matrix Multiplication