Sorting Algorithms की तुलना

Sorting comparison एक trip के लिए सही vehicle चुनने जैसा है: हर sorting method certain jobs के लिए सबसे अच्छी है, और आप सीखते हैं कि हर एक कब उपयोग करनी है।

In this page:

Basic Idea
Step by Step
Small Array
Practice
Summary

Basic Idea

कई sorting algorithms cover हो चुके, natural अगला सवाल है कि हर एक असल में कब उपयोग करनी है — सही choice data size, input पहले से कितना nearly-sorted है, memory constraints, और stability (बराबर elements का relative order संरक्षित रखना) मायने रखता है या नहीं इस पर निर्भर करता है।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
int main() {
	cout << "The right sort depends on data size, whether it is nearly sorted, and memory constraints";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("The right sort depends on data size, whether it is nearly sorted, and memory constraints");
	}
}

print("The right sort depends on data size, whether it is nearly sorted, and memory constraints")

#include <stdio.h>
int main() {
	printf("The right sort depends on data size, whether it is nearly sorted, and memory constraints");
	return 0;
}

Step by Step

Bubble, selection, और insertion sort सभी worst case में O(n²) में चलते हैं, लेकिन insertion sort nearly-sorted data पर genuinely fast है, जबकि bubble और selection sort को वह advantage नहीं — छोटे arrays के लिए, तीनों में से किसी की simplicity अक्सर वैसे भी काफी है।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data");
	}
}

print("Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data")

#include <stdio.h>
int main() {
	printf("Bubble, selection, and insertion sort are all O(n^2) worst case; insertion sort is fastest on nearly-sorted data");
	return 0;
}

Small Array

Merge sort extra memory की कीमत पर हर case में O(n log n) की गारंटी देता है, quicksort जगह पर वही speed average करता है लेकिन adversarial input पर O(n²) का जोखिम उठाता है, और heap sort O(1) extra space के साथ O(n log n) की गारंटी देता है लेकिन practice में एक well-tuned quicksort से धीमा होता है।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	cout << "Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place");
	}
}

print("Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place")

#include <stdio.h>
int main() {
	printf("Merge sort guarantees O(n log n) with extra memory; quicksort averages the same speed in-place");
	return 0;
}

Practice

Counting sort और radix sort O(n log n) comparison-sort lower bound को पूरी तरह हराते हैं, लेकिन सिर्फ integers (या integer-जैसी keys) के लिए काम करते हैं एक bounded range के अंदर — वे general-purpose replacements नहीं हैं, बस faster options हैं जब आपका data उनके constraints में fit हो।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys");
	}
}

print("Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys")

#include <stdio.h>
int main() {
	printf("Counting sort and radix sort beat the O(n log n) comparison-sort lower bound but only work for integer-like keys");
	return 0;
}

Summary

Practice में, ज़्यादातर language standard libraries एक hybrid default करती हैं: quicksort जैसी कोई चीज़ या एक tuned merge/insertion-sort combination जो input size के आधार पर strategy बदलती है, हर case के लिए एक single algorithm commit करने के बजाय।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs");
	}
}

print("Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs")

#include <stdio.h>
int main() {
	printf("Most standard libraries default to a hybrid of quicksort, merge sort, and insertion sort for small runs");
	return 0;
}

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Radix Sort Next Lesson → Linear Search