← Back to DSA Course | Chapter 9: Sorting Algorithms | Lesson 8 of 9

Radix Sort क्या है

Radix sort mail को पहले आखिरी digit से sort करने जैसा है, फिर अगली digit से, और वगैरह जब तक पूरा pile sort न हो जाए।

In this page:

  1. Basic Idea
  2. Step by Step
  3. Small Array
  4. Practice
  5. Summary
Syntax
markup 
exp = 1
while max_value // exp > 0:
    counting_sort_by_digit(arr, exp)
    exp *= 10

Basic Idea

Radix sort numbers को digit by digit sort करता है, least significant digit से most significant तक, हर digit position पर एक stable sort जैसे counting sort को एक subroutine के रूप में उपयोग करते हुए — यह पूरे numbers को सीधे compare करने से बचता है।

उदाहरण: Basic Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {170, 45, 75, 90, 802, 24};
	int n = 6;
	for (int exp = 1; 802 / exp > 0; exp *= 10) {
		int output[6], count[10] = {0};
		for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
		for (int i = 1; i < 10; i++) count[i] += count[i - 1];
		for (int i = n - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; output[--count[d]] = arr[i]; }
		for (int i = 0; i < n; i++) arr[i] = output[i];
	}
	for (int x : arr) cout << x << " ";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {170, 45, 75, 90, 802, 24};
		int n = arr.length;
		for (int exp = 1; 802 / exp > 0; exp *= 10) {
			int[] output = new int[n], count = new int[10];
			for (int x : arr) count[(x / exp) % 10]++;
			for (int i = 1; i < 10; i++) count[i] += count[i - 1];
			for (int i = n - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; output[--count[d]] = arr[i]; }
			arr = output;
		}
		System.out.println(java.util.Arrays.toString(arr));
	}
}
arr = [170, 45, 75, 90, 802, 24]
exp = 1
while 802 // exp > 0:
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for x in arr:
        count[(x // exp) % 10] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for i in range(n - 1, -1, -1):
        d = (arr[i] // exp) % 10
        count[d] -= 1
        output[count[d]] = arr[i]
    arr = output
    exp *= 10
print(arr)
#include <stdio.h>
int main() {
	int arr[] = {170, 45, 75, 90, 802, 24};
	int n = 6;
	for (int exp = 1; 802 / exp > 0; exp *= 10) {
		int output[6], count[10] = {0};
		for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
		for (int i = 1; i < 10; i++) count[i] += count[i - 1];
		for (int i = n - 1; i >= 0; i--) { int d = (arr[i] / exp) % 10; output[--count[d]] = arr[i]; }
		for (int i = 0; i < n; i++) arr[i] = output[i];
	}
	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
	return 0;
}

Step by Step

हर pass पूरे array को बस एक digit position से sort करता है जबकि पिछले pass से बराबर digits का relative order संरक्षित रखता है (यही कारण है कि subroutine stable होना चाहिए) — हर digit position process करने के बाद, array पूरी तरह sorted हो जाता है।

उदाहरण: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order");
	}
}
print("Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order")
#include <stdio.h>
int main() {
	printf("Sort by ones digit first using counting sort, then tens digit, then hundreds, preserving prior order");
	return 0;
}

Small Array

[170, 45, 75, 90, 802, 24] जैसे छोटे numbers पर radix sort trace करना दिखाता है कि पहले ones digit से sort करना, फिर tens digit, फिर hundreds digit, धीरे-धीरे order को refine करता है जब तक final pass array को पूरी तरह sorted न छोड़ दे।

उदाहरण: Small Array

#include <iostream>
using namespace std;
int main() {
	int arr[] = {170, 45, 75, 90, 802, 24};
	for (int x : arr) cout << "ones digit of " << x << " is " << x % 10 << endl;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {170, 45, 75, 90, 802, 24};
		for (int x : arr) System.out.println("ones digit of " + x + " is " + x % 10);
	}
}
arr = [170, 45, 75, 90, 802, 24]
for x in arr:
    print("ones digit of", x, "is", x % 10)
#include <stdio.h>
int main() {
	int arr[] = {170, 45, 75, 90, 802, 24};
	for (int i = 0; i < 6; i++) printf("ones digit of %d is %d\n", arr[i], arr[i] % 10);
	return 0;
}

Practice

Radix sort को उसी data पर counting sort से compare करना worth है: counting sort को सीधे largest value के size का एक count array चाहिए, जबकि radix sort उसी value को digit by digit process करता है, एक huge range को passes की एक bounded संख्या से trade करते हुए।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit");
	}
}
print("Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit")
#include <stdio.h>
int main() {
	printf("Counting sort needs a count array sized to the largest value; radix sort avoids that by sorting per digit");
	return 0;
}

Summary

Radix sort O(d * (n + k)) time में चलता है, जहां d digits की संख्या है और k प्रति digit उपयोग किया base है (आमतौर पर 10) — fixed-width numbers के लिए यह effectively linear है, इसे सही तरह के data पर comparison sorts से तेज़ बनाते हुए।

उदाहरण: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)");
	}
}
print("Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)")
#include <stdio.h>
int main() {
	printf("Radix sort: O(d * (n + k)) time, where d is the number of digits and k is the base (usually 10)");
	return 0;
}
Related Topics

Counting Sort क्या है · Heap Sort क्या है · Quick Sort क्या है · Merge Sort क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. हर digit pass के लिए एक unstable sort उपयोग करना, जो पहले के passes से ordering तोड़ता है।
  2. Least significant digit के method के साथ most significant digit से शुरू करना।
  3. exp loop बहुत जल्दी रोकना, इसलिए maxVal से ज़्यादा digits वाले numbers पूरी तरह sort नहीं होते।
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Counting Sort Next Lesson → Sorting Comparison

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.