LogoKode$word
Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity
Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Learn Quick Sort with detailed intuition, partition logic, Java code, dry run, and complexity analysis. Perfect for coding interviews and DSA.

8 views
0
0
Github icon
Github icon
Listen to articleAudio version

Introduction

Quick Sort is one of the most powerful and widely used sorting algorithms in computer science. It follows the Divide and Conquer approach and is known for its excellent average-case performance.

What makes Quick Sort special is:

  1. It sorts in-place (no extra array required)
  2. It is faster in practice than many O(n log n) algorithms like Merge Sort
  3. It is heavily used in real-world systems and libraries

In this article, we’ll go deep into:

  1. Intuition behind Quick Sort
  2. Partition logic (most important part)
  3. Step-by-step dry run
  4. Java implementation with comments
  5. Time complexity analysis
  6. Common mistakes and optimizations

🔗 Problem Link

GeeksforGeeks: Quick Sort

Problem Statement

Given an array arr[], sort it in ascending order using Quick Sort.

Requirements:

  1. Use Divide and Conquer
  2. Choose pivot element
  3. Place pivot in correct position
  4. Elements smaller → left side
  5. Elements greater → right side

Examples

Example 1

Input:

arr = [4, 1, 3, 9, 7]

Output:

[1, 3, 4, 7, 9]

Example 2

Input:

arr = [2, 1, 6, 10, 4, 1, 3, 9, 7]

Output:

[1, 1, 2, 3, 4, 6, 7, 9, 10]

Core Idea of Quick Sort

Pick a pivot → Place it correctly → Recursively sort left & right

🔥 Key Insight (Partition is Everything)

Quick Sort depends entirely on partitioning:

👉 After partition:

  1. Pivot is at its correct sorted position
  2. Left side → smaller elements
  3. Right side → larger elements

Intuition (Visual Understanding)

Consider:

[4, 1, 3, 9, 7]

Step 1: Choose Pivot

Let’s say pivot = 4

Step 2: Rearrange Elements

[1, 3] 4 [9, 7]

Now:

  1. Left → smaller
  2. Right → larger

Step 3: Apply Recursively

Left: [1, 3]
Right: [9, 7]

Final result:

[1, 3, 4, 7, 9]

Partition Logic (Most Important)

Your implementation uses:

  1. Pivot = first element
  2. Two pointers:
  3. i → moves forward
  4. j → moves backward

Java Code

class Solution {

public void quickSort(int[] arr, int low, int high) {

// Base case: if array has 1 or 0 elements
if (low < high) {

// Partition array and get pivot index
int pivotInd = partition(arr, low, high);

// Sort left part
quickSort(arr, low, pivotInd - 1);

// Sort right part
quickSort(arr, pivotInd + 1, high);
}
}

// Function to swap two elements
void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

private int partition(int[] arr, int low, int high) {

int pivot = arr[low]; // choosing first element as pivot

int i = low + 1; // start from next element
int j = high; // start from end

while (i <= j) {

// Move i forward until element > pivot
while (i <= high && arr[i] <= pivot) {
i++;
}

// Move j backward until element <= pivot
while (j >= low && arr[j] > pivot) {
j--;
}

// Swap if pointers haven't crossed
if (i < j) {
swap(arr, i, j);
}
}

// Place pivot at correct position
swap(arr, low, j);

return j; // return pivot index
}
}

Step-by-Step Dry Run

Input:

[4, 1, 3, 9, 7]

Execution:

  1. Pivot = 4
  2. i → moves until element > 4
  3. j → moves until element ≤ 4

Swaps happen → pivot placed correctly

Final partition:

[1, 3, 4, 9, 7]

Complexity Analysis

Time Complexity

CaseComplexity
Best CaseO(n log n)
Average CaseO(n log n)
Worst CaseO(n²)

Why Worst Case Happens?

When array is:

  1. Already sorted
  2. Reverse sorted

Pivot always becomes smallest/largest.

Space Complexity

  1. O(log n) (recursion stack)

❌ Common Mistakes

  1. Wrong partition logic
  2. Infinite loops in while conditions
  3. Incorrect pivot placement
  4. Not handling duplicates properly

⚡ Optimizations

1. Random Pivot

Avoid worst-case:

int pivotIndex = low + new Random().nextInt(high - low + 1);
swap(arr, low, pivotIndex);

2. Median of Three

Choose better pivot:

median(arr[low], arr[mid], arr[high])

Quick Sort vs Merge Sort

FeatureQuick SortMerge Sort link to get more
SpaceO(log n)O(n)
SpeedFaster (practical)Stable
Worst CaseO(n²)O(n log n)

Why Quick Sort is Preferred

  1. Cache-friendly
  2. In-place sorting
  3. Faster in real-world scenarios

Key Takeaways

  1. Partition is the heart of Quick Sort
  2. Pivot must be placed correctly
  3. Recursion splits problem efficiently
  4. Avoid worst case using random pivot

When to Use Quick Sort

  1. Large arrays
  2. Memory constraints (in-place)
  3. Performance-critical applications

Conclusion

Quick Sort is one of the most efficient and practical sorting algorithms. Mastering its partition logic is crucial for solving advanced problems and performing well in coding interviews.

Understanding how pointers move and how pivot is placed will make this algorithm intuitive and powerful.

Frequently Asked Questions (FAQs)

1. Is Quick Sort stable?

No, it is not stable.

2. Why is Quick Sort faster than Merge Sort?

Because it avoids extra space and is cache-efficient.

3. What is the most important part?

👉 Partition logic

Related Articles

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Learn How to Rearrange a Linked List by Odd and Even Positions Using Optimal O(1) Space Approach

Read Article
Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

Learn Merge Sort with step-by-step explanation, recursion, iterative approach, Java code, and complexity analysis. Perfect for coding interviews.

Read Article
Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Learn how to efficiently search for an element in a rotated sorted array using binary search. This guide explains the intuition, multiple strategies, and a clean Java implementation that achieves O(log n) time complexity.

Read Article
LeetCode 143 Reorder List - Java Solution Explained

LeetCode 143 Reorder List - Java Solution Explained

Learn how to solve LeetCode 143 Reorder List using Fast & Slow Pointer, Reverse Linked List, and Merge techniques in Java. Includes step-by-step dry run, time & space complexity analysis.

Read Article
Ai Assistant Kas