What is the Quick Sort in DSA ?? with Free Explanation

Overview

Quick Sort is a highly efficient and widely used sorting algorithm that employs the divide-and-conquer strategy. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Key Characteristics

1. Time Complexity: O(n log n) on average, O(n²) in the worst case (when the smallest or largest element is always chosen as the pivot).
2. Space Complexity: O(log n) due to the recursion stack (in-place sorting).
3. Stability: Not stable (the relative order of equal elements might change).
4. Algorithm Type: Comparison-based, divide-and-conquer sorting.

How Quick Sort Works

Choose a Pivot:

• Select a pivot element from the array.

Partition the Array:

• Rearrange the elements such that all elements less than the pivot are on its left, and all elements greater than the pivot are on its right.

Recursively Apply:

• Apply the same process to the left and right sub-arrays created by the partition.

Steps and Example

Consider the following unsorted array:

[10, 7, 8, 9, 1, 5]

Step 1: Choose a Pivot

• Choose 5 as the pivot.

Step 2: Partition the Array

• Rearrange elements to [1, 5, 10, 7, 8, 9].

Step 3: Recursively Apply

• Recursively sort the left sub-array [1] and the right sub-array [10, 7, 8, 9].

Detailed Steps

1. Initial array: [10, 7, 8, 9, 1, 5]
2. Pivot: 5
3. Partition: [1, 5, 10, 7, 8, 9]
4. Recursively sort [1] (already sorted)
5. Recursively sort [10, 7, 8, 9]:
   • Pivot: 9
   • Partition: [7, 8, 9, 10]
   • Recursively sort [7, 8]:
     • Pivot: 8
     • Partition: [7, 8]
   • 10 is already sorted
6. Final sorted array: [1, 5, 7, 8, 9, 10]

Visualization

Let’s generate a step-by-step visualization of Quick Sort using diagrams.

Initial Array

[10, 7, 8, 9, 1, 5]

After Choosing Pivot and Partition

Step 1: Choose 5 as pivot
[1, 5, 10, 7, 8, 9]

Recursively Sort Left and Right Sub-arrays

Step 2: Sort left sub-array [1] -> Already sorted

Step 3: Sort right sub-array [10, 7, 8, 9]

Sorting the Right Sub-array

Choose 9 as pivot
[7, 8, 9, 10]
Sort [7, 8] -> Choose 8 as pivot -> [7, 8]
Final right sub-array: [7, 8, 9, 10]

Final Sorted Array

[1, 5, 7, 8, 9, 10]