Counting Sort क्या है

Counting sort एक scoreboard पर हर number कितनी बार है यह tally करने और फिर tallies को order में पढ़ने जैसा है, बिना किसी comparison के।

In this page:

Basic Idea
Step by Step
Small Array
Practice
Summary

Syntax

markup

count = [0] * (max_value + 1)
for x in arr:
    count[x] += 1
result = []
for value in range(len(count)):
    result.extend([value] * count[value])

Basic Idea

Counting sort comparisons से पूरी तरह बचता है: यह count करता है कि हर distinct value कितनी बार दिखती है, फिर उन counts उपयोग करके हर value को सीधे इसकी सही sorted position में रखता है — यह सिर्फ तब काम करता है जब values integers की एक छोटी, known range में आती हैं।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int n = 7, maxVal = 8;
	int count[9] = {0};
	for (int i = 0; i < n; i++) count[arr[i]]++;
	for (int i = 0; i <= maxVal; i++)
		for (int j = 0; j < count[i]; j++) cout << i << " ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 2, 2, 8, 3, 3, 1};
		int maxVal = 8;
		int[] count = new int[9];
		for (int x : arr) count[x]++;
		for (int i = 0; i <= maxVal; i++)
			for (int j = 0; j < count[i]; j++) System.out.print(i + " ");
	}
}

arr = [4, 2, 2, 8, 3, 3, 1]
max_val = 8
count = [0] * (max_val + 1)
for x in arr:
    count[x] += 1
result = []
for i, c in enumerate(count):
    result += [i] * c
print(result)

#include <stdio.h>
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int n = 7, maxVal = 8;
	int count[9] = {0};
	for (int i = 0; i < n; i++) count[arr[i]]++;
	for (int i = 0; i <= maxVal; i++)
		for (int j = 0; j < count[i]; j++) printf("%d ", i);
	return 0;
}

Step by Step

Algorithm value से indexed एक count array बनाता है, input पर एक pass से occurrences tally करता है, फिर उन counts को starting positions में convert करता है (एक running total से) ताकि हर value को किसी से compare किए बिना सीधे output array में रखा जा सके।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value");
	}
}

print("Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value")

#include <stdio.h>
int main() {
	printf("Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value");
	return 0;
}

Small Array

[4, 2, 2, 8, 3, 3, 1] जैसे छोटे integers के एक छोटे array पर counting sort trace करना दिखाता है कि count array कैसे भरता है, फिर वे counts हर value के लिए exact output positions में कैसे translate होते हैं।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int count[9] = {0};
	for (int i = 0; i < 7; i++) count[arr[i]]++;
	for (int i = 0; i <= 8; i++) if (count[i] > 0) cout << "value " << i << " occurs " << count[i] << " times" << endl;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 2, 2, 8, 3, 3, 1};
		int[] count = new int[9];
		for (int x : arr) count[x]++;
		for (int i = 0; i <= 8; i++) if (count[i] > 0) System.out.println("value " + i + " occurs " + count[i] + " times");
	}
}

arr = [4, 2, 2, 8, 3, 3, 1]
count = [0] * 9
for x in arr:
    count[x] += 1
for i, c in enumerate(count):
    if c > 0:
        print("value", i, "occurs", c, "times")

#include <stdio.h>
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int count[9] = {0};
	for (int i = 0; i < 7; i++) count[arr[i]]++;
	for (int i = 0; i <= 8; i++) if (count[i] > 0) printf("value %d occurs %d times\n", i, count[i]);
	return 0;
}

Practice

Values की एक wide range वाले array पर counting sort try करें एक narrow range वाले की तुलना में — एक huge range एक छोटे input के लिए भी एक oversized count array बनाने में बहुत सारी space और time waste करती है, जो बिल्कुल इसकी main limitation है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "A narrow value range makes counting sort very fast; a huge range wastes space and time";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A narrow value range makes counting sort very fast; a huge range wastes space and time");
	}
}

print("A narrow value range makes counting sort very fast; a huge range wastes space and time")

#include <stdio.h>
int main() {
	printf("A narrow value range makes counting sort very fast; a huge range wastes space and time");
	return 0;
}

Summary

Counting sort O(n + k) time और space में चलता है, जहां k possible values की range है — यह comparison-based sorts के O(n log n) lower bound को हराता है, लेकिन सिर्फ इसलिए क्योंकि यह comparisons से पूरी तरह बचता है, उस range के छोटे और पहले से known होने की ज़रूरत की कीमत पर।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)");
	}
}

print("Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)")

#include <stdio.h>
int main() {
	printf("Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)");
	return 0;
}

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Heap Sort Next Lesson → Radix Sort