Quick Sort क्या है

Quick sort एक kid को marker के रूप में चुनने जैसा है और shorter kids को एक side और taller kids को दूसरी में भेजना, फिर हर group में वही करना।

In this page:

Basic Idea
Step by Step
Small Array
Practice
Summary

Syntax

markup

def quick_sort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)

Basic Idea

Quicksort एक pivot element चुनता है, array को partition करता है ताकि छोटी values इसके पहले और बड़ी values इसके बाद आएं, और फिर हर side recursively sort करता है — एक और divide-and-conquer algorithm, लेकिन एक जो merge के बजाय split के दौरान अपना main work करता है।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
	int pivot = arr[high], i = low - 1;
	for (int j = low; j < high; j++)
		if (arr[j] < pivot) swap(arr[++i], arr[j]);
	swap(arr[i + 1], arr[high]);
	return i + 1;
}
void quickSort(int arr[], int low, int high) {
	if (low >= high) return;
	int pi = partition(arr, low, high);
	quickSort(arr, low, pi - 1);
	quickSort(arr, pi + 1, high);
}
int main() {
	int arr[] = {7, 2, 1, 6, 8, 5};
	quickSort(arr, 0, 5);
	for (int x : arr) cout << x << " ";
	return 0;
}

public class Main {
	static int partition(int[] arr, int low, int high) {
		int pivot = arr[high], i = low - 1;
		for (int j = low; j < high; j++)
			if (arr[j] < pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
		int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
		return i + 1;
	}
	static void quickSort(int[] arr, int low, int high) {
		if (low >= high) return;
		int pi = partition(arr, low, high);
		quickSort(arr, low, pi - 1);
		quickSort(arr, pi + 1, high);
	}
	public static void main(String[] args) {
		int[] arr = {7, 2, 1, 6, 8, 5};
		quickSort(arr, 0, 5);
		System.out.println(java.util.Arrays.toString(arr));
	}
}

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low >= high:
        return
    pi = partition(arr, low, high)
    quick_sort(arr, low, pi - 1)
    quick_sort(arr, pi + 1, high)

arr = [7, 2, 1, 6, 8, 5]
quick_sort(arr, 0, 5)
print(arr)

#include <stdio.h>
int partition(int arr[], int low, int high) {
	int pivot = arr[high], i = low - 1;
	for (int j = low; j < high; j++)
		if (arr[j] < pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
	int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
	return i + 1;
}
void quickSort(int arr[], int low, int high) {
	if (low >= high) return;
	int pi = partition(arr, low, high);
	quickSort(arr, low, pi - 1);
	quickSort(arr, pi + 1, high);
}
int main() {
	int arr[] = {7, 2, 1, 6, 8, 5};
	quickSort(arr, 0, 5);
	for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

Partitioning array से चलता है हर element को चुने pivot से compare करते हुए, elements swap करते हुए ताकि pivot से छोटी हर चीज़ इसके left में और बड़ी हर चीज़ इसके right में आए, pivot को इसकी final sorted position में खत्म करते हुए।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last");
	}
}

print("Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last")

#include <stdio.h>
int main() {
	printf("Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last");
	return 0;
}

Small Array

[7, 2, 1, 6, 8, 5] जैसे array पर आखिरी element को pivot के रूप में एक partition step trace करना दिखाता है कि 'pivot से छोटा' और 'अभी तक न जांचा गया' के बीच boundary scan आगे बढ़ने के साथ एक समय में एक element कैसे shift होती है।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	int arr[] = {7, 2, 1, 6, 8, 5};
	int pivot = arr[5], i = -1;
	for (int j = 0; j < 5; j++)
		if (arr[j] < pivot) cout << "swap " << arr[++i] << " and " << arr[j] << endl;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {7, 2, 1, 6, 8, 5};
		int pivot = arr[5], i = -1;
		for (int j = 0; j < 5; j++)
			if (arr[j] < pivot) System.out.println("swap " + arr[++i] + " and " + arr[j]);
	}
}

arr = [7, 2, 1, 6, 8, 5]
pivot = arr[5]
i = -1
for j in range(5):
    if arr[j] < pivot:
        i += 1
        print("swap", arr[i], "and", arr[j])

#include <stdio.h>
int main() {
	int arr[] = {7, 2, 1, 6, 8, 5};
	int pivot = arr[5], i = -1;
	for (int j = 0; j < 5; j++)
		if (arr[j] < pivot) { i++; printf("swap %d and %d\n", arr[i], arr[j]); }
	return 0;
}

Practice

Quicksort की performance pivot choice पर बहुत निर्भर करती है: median के करीब एक pivot work evenly split करता है और fast performance देता है, जबकि एक consistently खराब pivot (जैसे हमेशा सबसे छोटा या सबसे बड़ा element चुनना) uneven splits और कहीं ज़्यादा धीमा behavior का कारण बनता है — एक छोटे array पर दोनों cases trace करने की कोशिश करें।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)");
	}
}

print("A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)")

#include <stdio.h>
int main() {
	printf("A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)");
	return 0;
}

Summary

Quicksort average में O(n log n) time लेता है, merge sort से मेल खाते हुए, लेकिन इसका worst case O(n²) तक degrade होता है जब pivot choice बार-बार unbalanced partitions produce करती है — practice में यह अब भी अक्सर merge sort से तेज़ है क्योंकि यह बिना extra arrays की ज़रूरत के जगह पर sort करता है।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice");
	}
}

print("Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice")

#include <stdio.h>
int main() {
	printf("Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice");
	return 0;
}

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Merge Sort Next Lesson → Heap Sort