Quick Sort in Java: Complete Guide with Pivot, Partition and Time Complexity Explained

 

Quick Sort in Java (Simple Explanation with Real Life Example)

Level: Beginner to Intermediate
Part 7 of DSA Series

 Introduction

Quick Sort duniya ke sabse popular aur fast sorting algorithms me se ek hai.

Iska naam “Quick” isliye hai kyunki average case me ye kaafi fast hota hai — O(n log n).

Large applications, system libraries, aur interviews me ye frequently poocha jata hai.

🔹 What is Quick Sort? 

Quick Sort is a divide-and-conquer based sorting algorithm that works by selecting a special element called a pivot and rearranging the array so that elements smaller than the pivot come before it and larger elements come after it. This process is called partitioning. After placing the pivot in its correct position, the same process is recursively applied to the left and right subarrays. Due to its efficient average-case time complexity of O(n log n), Quick Sort is widely used in real-world systems.

What is a Pivot? 

A pivot is a selected element in the array that is used as a reference point to divide the array into two parts during Quick Sort. All elements smaller than the pivot are moved to its left, and all larger elements are moved to its right. The pivot ultimately reaches its correct sorted position after partitioning. The choice of pivot directly affects the efficiency of Quick Sort and can influence whether the algorithm performs optimally or degrades to worst-case complexity.


What is Partitioning? 

Partitioning is the process in Quick Sort where the array is reorganized around the pivot element. During partitioning, the algorithm scans through the array and compares each element with the pivot. Elements smaller than the pivot are shifted toward the left side, and larger elements are shifted toward the right side. At the end of this process, the pivot is placed in its correct sorted position. Partitioning ensures that after each step, at least one element (the pivot) is permanently placed in its final sorted location.


What is Divide and Conquer? 

Divide and Conquer is an algorithm design technique where a problem is divided into smaller subproblems, each subproblem is solved independently (usually recursively), and then the results are combined to produce the final solution. In Quick Sort, the array is divided using partitioning, and the same sorting logic is recursively applied to the left and right subarrays until the entire array becomes sorted.

 Core Idea (Simple Language)

Quick Sort 3 steps me kaam karta hai:

  • Choose a Pivot
    Array me se ek element choose karo (usually last ya first element).

  • Partition the Array
    Chhote elements left side
    Bade elements right side

  • Repeat Recursively
    Left aur right part par same process repeat karo.

 Real Life Example (Classroom Example)

Socho teacher class me students ko height ke hisaab se line me lagana chahti hain.

 Ek student ko “pivot” bana diya.
 Jinki height pivot se kam hai → left me khade ho jao.
 Jinki height zyada hai → right me khade ho jao.

Ab left group me fir se ek pivot choose karo.
Same process repeat karo.

Dheere-dheere poori class sorted ho jayegi.

 Technical Example

Given array:

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

Pivot = 5

After partition:

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

Pivot correct position par aa gaya.

Ab left and right par quick sort apply hoga.

 Java Implementation

public class QuickSort {

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {

            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

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

        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;

                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {

        int[] arr = {10, 7, 8, 9, 1, 5};

        quickSort(arr, 0, arr.length - 1);

        for (int num : arr)
            System.out.print(num + " ");
    }
}

 Time Complexity

  • Best Case → O(n log n)
    Jab pivot array ko evenly divide kare.

  • Average Case → O(n log n)
    Normal situation me.

  • Worst Case → O(n²)
    Jab array already sorted ho aur pivot worst choose ho.

 Space Complexity

  • O(log n) due to recursion stack (average case)

  • O(log n) (average case)

  • Recursion stack ke kaaran.

  • Quick Sort in-place sorting karta hai (extra array use nahi karta).


Advantages of Quick Sort

  • Fast in practice
    Real-world me efficient hota hai.

  • In-place sorting
    Extra memory kam use karta hai.

  • Divide and conquer concept strong karta hai

 Disadvantages of Quick Sort

  • Worst case O(n²)
    Galat pivot choice se slow ho sakta hai.

  • Not stable by default
    Equal elements ka order change ho sakta hai.

 Quick Sort vs Merge Sort

  • Merge Sort
    Stable hai
    Extra memory use karta hai (O(n))

  • Quick Sort
    In-place sorting
    Memory kam use karta hai
    Practical systems me zyada fast hota hai

🔹 Why Interviewers Love Quick Sort?

  • Recursion concept test hota hai

  • Partition logic samajhna important hai

  • Worst case ka reasoning poocha jata hai

 Quick Check (Basic Level)

 Quick Sort me pivot ka kya role hota hai?

 Small Practice Question

Given array:

[4, 2, 6, 1]

Agar pivot last element ho (1),
to first partition ke baad array ka order kya hoga?

Socho aur comment me likho 👇

👉 Agar aap Quick Sort ka partition logic manually dry run kar sakte hain, to comment me “DONE” likhiye.

Comments

Post a Comment

Popular posts from this blog

Binary Tree in Data Structures Explained in Depth (Concept, Types and Java Implementation)

  Binary Tree in Data Structures (Deep Concept Guide)  What is a Binary Tree? A Binary Tree is a specialized type of tree data structure in which each node can have at most two children, typically referred to as the left child and the right child. Unlike general trees where a node may have multiple children, a binary tree restricts branching to two directions. This limitation allows structured organization and efficient implementation of many algorithms such as searching, sorting, and expression evaluation. Binary trees form the foundation of advanced structures like Binary Search Trees (BST), Heaps, and AVL Trees. Because of their recursive nature, binary trees are often implemented and traversed using recursion. A Binary Tree is a hierarchical, non-linear data structure in which each node can have at most two children, referred to as the left child and right child. This restriction distinguishes it from a general tree where nodes may have multiple children. A binary tree...
Read more

Binary Tree Traversal Explained in Depth (Preorder, Inorder, Postorder with Java Code)

 Binary Tree Traversals (In Depth Guide) Ye topic bahut important hai kyunki: Tree ko read kaise karna hai — traversal se pata chalta hai 70% tree interview questions traversal based hote hain Recursion ka real use yahi se start hota hai DFS aur BFS concepts yahi se clear hote hain  What is Tree Traversal?  Tree Traversal is the process of visiting every node in a tree data structure exactly once in a specific order. Since a tree is hierarchical and non-linear, we cannot simply iterate over it like arrays or linked lists. Instead, we follow systematic traversal techniques to access nodes. Traversal ensures that all nodes are processed, whether for searching, printing, evaluating expressions, or performing modifications. Traversal techniques are mainly divided into two categories: Depth First Search (DFS) and Breadth First Search (BFS). DFS explores branches deeply before moving to the next branch, while BFS explores level by level. Understanding traversal is essential for...
Read more

Recursion in Java Explained with Examples (Base Case, Recursive Case & Dry Run Guide)

Recursion in Java (Complete Detailed Guide) Introduction  Recursion DSA ka ek powerful concept hai jo beginners ko thoda confusing lag sakta hai, lekin agar ek baar samajh aa gaya to Tree, Graph, Backtracking, Dynamic Programming sab easy ho jate hain. Recursion is a programming technique in which a function solves a problem by calling itself with a smaller or simpler input until a stopping condition is reached. Instead of using loops, recursion repeatedly breaks the problem into smaller subproblems of the same type. Each recursive call waits for the next call to finish before returning its result. Every recursive solution must contain a base case to stop execution and a recursive case to reduce the problem size. Recursion is widely used in tree traversal, divide-and-conquer algorithms, backtracking, and dynamic programming. Aaj hum recursion ko bilkul simple language me samjhenge — real-life example ke saath.  What is Recursion? Recursion is a programming technique in wh...
Read more