Counting Sort and Radix Sort: Non-Comparison Linear Sorting Notes in Hindi & English : काउंटिंग सॉर्ट और रेडिक्स सॉर्ट: गैर-तुलनात्मक O(n+k) सॉर्टिंग और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Counting Sort and Radix Sort: Non-Comparison Linear Sorting (काउंटिंग सॉर्ट और रेडिक्स सॉर्ट: गैर-तुलनात्मक O(n+k) सॉर्टिंग) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: Counting Sort and Radix Sort bypass the Omega(n log n) comparison sorting lower bound by indexing keys directly into frequency buckets or digit passes, achieving linear O(n + k) and O(d(n + b)) stable sorting.

अध्याय सार: काउंटिंग सॉर्ट व रेडिक्स सॉर्ट तत्वों की आपसी तुलना किए बिना फ्रीक्वेंसी बकेट और अंकों (Digits) के पास द्वारा Omega(n log n) सीमा को पार करते हुए क्रमशः O(n + k) तथा O(d(n + b)) समय में स्टेबल सॉर्टिंग करते हैं।

Counting Sort and Radix Sort: Non-Comparison Linear Sorting: Detailed Notes & Architecture (काउंटिंग सॉर्ट और रेडिक्स सॉर्ट: गैर-तुलनात्मक O(n+k) सॉर्टिंग)

1. Breaking the Omega(n log n) Comparison Lower Bound (Omega(n log n) तुलना सीमा को तोड़ने का सिद्धांत)

[EN] Every comparison-based sorting algorithm (Quick, Merge, Heap, Insertion) corresponds to a binary decision tree with at least n! leaves, proving an unavoidable lower bound of Omega(n log n) comparisons in the worst case. Counting Sort and Radix Sort evade this bound entirely because they NEVER compare two input elements against each other (< or >); instead, they exploit numeric structure—using integer keys or individual digits directly as memory bucket addresses.

[HI] तुलना-आधारित हर सॉर्टिंग एल्गोरिदम का डिसीजन ट्री कम से कम n! पत्तियों वाला होता है, जिससे वर्स्ट केस में कम से कम Omega(n log n) तुलनाएँ अनिवार्य हैं। काउंटिंग और रेडिक्स सॉर्ट तत्वों की आपसी (< या >) तुलना करते ही नहीं; वे संख्यात्मक कुंजियों या उनके अंकों को सीधे एरे इंडेक्स (बकेट) के रूप में उपयोग करके रैखिक समय (Linear Time) में सॉर्ट कर देते हैं।

2. Counting Sort: Frequency, Prefix Sum & Reverse Placement (काउंटिंग सॉर्ट: फ्रीक्वेंसी, प्रीफिक्स योग व उलटा प्लेसमेंट)

[EN] Given n integers within bounded range [0..k], Counting Sort executes three linear phases: (1) count[x] tallies occurrences of each key x in O(n); (2) prefix sums count[i] += count[i-1] over 1..k compute ending positions in O(k); (3) iterating the original input BACKWARD from n-1 down to 0 places output[--count[arr[i]]] = arr[i] in O(n). Reverse traversal guarantees STABILITY for attached satellite data. Total time and auxiliary space are both O(n + k)—ideal when k = O(n), but wasteful if k >> n.

[HI] 0 से k सीमा के n पूर्णांकों पर काउंटिंग सॉर्ट तीन चरण चलाता है: (1) O(n) में हर संख्या की आवृत्ति count[] में गिनना; (2) O(k) में प्रीफिक्स योग (count[i] += count[i-1]) से अंतिम स्थान निकालना; (3) मूल एरे को पीछे से (n-1 से 0 तक) पढ़कर सही स्थान पर रखना। पीछे से चलने के कारण ही समान मानों की स्थिरता (Stability) बनी रहती है। इसका कुल समय व स्पेस O(n + k) है, जो तभी अच्छा है जब k छोटा हो।

3. Radix Sort (LSD): Digit-by-Digit Stable Sorting (रेडिक्स सॉर्ट (LSD): अंक-दर-अंक स्थिर छँटाई)

[EN] When k is huge (e.g., 6-digit or 32-bit integers), Counting Sort alone needs excessive O(k) space. Radix Sort processes d-digit numbers in base b (radix) from Least Significant Digit (LSD) to Most Significant Digit (MSD), sorting all n numbers on one digit per pass using a STABLE inner sort (almost always Counting Sort on range 0..b-1). Because each pass preserves previous lower-digit order via stability, total runtime is O(d * (n + b)) and space is O(n + b).

[HI] जब संख्याओं की सीमा k बहुत बड़ी हो, तो रेडिक्स सॉर्ट संख्याओं को आधार b (Radix) में d अंकों में तोड़कर सबसे कम महत्वपूर्ण अंक (LSD) से सबसे बड़े अंक (MSD) की ओर एक-एक अंक पर सॉर्ट करता है। प्रत्येक अंक के लिए 0 से b-1 रेंज वाला स्टेबल काउंटिंग सॉर्ट चलाया जाता है। स्थिरता के कारण पिछले अंकों का सही क्रम सुरक्षित रहता है और कुल समय O(d * (n + b)) लगता है।

4. Negative Numbers Offset & Base-n Linear Trick (ऋणात्मक संख्याएं व बेस-n द्वारा O(n) सॉर्टिंग)

[EN] Counting Sort easily handles negative integers by finding min_val and shifting every key via index = val - min_val (with k = max_val - min_val). For Radix Sort, choosing a larger base b = n lets us sort any n integers bounded by n^c (e.g., 0 to n^3 - 1) in d = c passes, achieving O(c * (n + n)) = O(n) true linear time! However, neither algorithm is in-place (both need O(n + k) or O(n + b) space) and arbitrary floating-point strings require careful encoding.

[HI] ऋणात्मक संख्याओं के लिए val - min_val का ऑफसेट घटाकर काउंटिंग सॉर्ट चलाया जा सकता है। रेडिक्स सॉर्ट में यदि आधार b = n चुना जाए, तो 0 से n^c - 1 तक के किसी भी डेटा को d = c पास में O(c * n) = O(n) शुद्ध रैखिक समय में सॉर्ट किया जा सकता है। हालांकि दोनों एल्गोरिदम इन-प्लेस नहीं हैं क्योंकि इनमें अतिरिक्त आउटपुट और काउंट बफर लगते हैं।

Syntax, Formula & Technical Example (Counting Sort and Radix Sort: Non-Comparison Linear Sorting)

def counting_sort(arr, k):
    count = [0] * (k + 1)
    output = [0] * len(arr)
    for x in arr: count[x] += 1
    for i in range(1, k + 1): count[i] += count[i - 1]
    # Reverse loop preserves stability!
    for x in reversed(arr):
        count[x] -= 1
        output[count[x]] = x
    return output

Counting Sort and Radix Sort: Non-Comparison Linear Sorting Quick Reference & Comparison Table

Non-Comparison MethodTime & Space ComplexityCritical Prerequisite / Rule
Counting Sort ComplexityO(n + k) time and O(n + k) spaceEfficient only when key range k is O(n) or small
Reverse Placement LoopIterates n-1 down to 0 into output[]Guarantees stability for duplicate keys/records
LSD Radix Sort RuntimeO(d * (n + b)) for d digits, base bRequires a STABLE subroutine like Counting Sort
Comparison Lower BoundEvades Omega(n log n) decision tree limitUses key values/digits as direct bucket indices

Counting Sort and Radix Sort: Non-Comparison Linear Sorting Top 20 Bilingual MCQs with Answers

Q1. Why can Counting Sort and Radix Sort achieve O(n) linear time while Merge Sort and Heap Sort cannot beat Omega(n log n)?

(मर्ज व हीप सॉर्ट Omega(n log n) से नीचे नहीं जा सकते, जबकि काउंटिंग और रेडिक्स सॉर्ट O(n) रैखिक समय कैसे प्राप्त कर लेते हैं?)

(A) They exploit O(1) recursion trees

(B) They discard duplicate keys during sorting

(C) They are non-comparison sorts that index directly by key/digit values instead of binary element comparisons

(D) They use parallel multi-core GPUs by default

Correct Answer: (C)

[EN] The Omega(n log n) decision-tree bound applies strictly to comparison-based sorting; non-comparison algorithms bypass it using integer distribution.

[HI] Omega(n log n) की निचली सीमा केवल तुलना-आधारित एल्गोरिदम पर लागू होती है; काउंटिंग व रेडिक्स बिना तुलना के सीधे बकेट इंडेक्सिंग करते हैं।

Q2. What are the time and auxiliary space complexities of Counting Sort for n elements in range 0..k?

(0 से k सीमा के भीतर n तत्वों पर काउंटिंग सॉर्ट की टाइम व ऑक्सिलरी स्पेस कॉम्प्लेक्सिटी क्या होती है?)

(A) Time: O(n), Space: O(1)

(B) Time: O(n + k), Space: O(n + k)

(C) Time: O(n log k), Space: O(1)

(D) Time: O(n * k), Space: O(k)

Correct Answer: (B)

[EN] Counting + output takes O(n) and prefix-sum array takes O(k), totaling O(n + k) for both time and extra space.

[HI] गिनती और आउटपुट एरे O(n) तथा काउंट बफर O(k) लेता है, अतः समय और स्थान दोनों O(n + k) होते हैं।

Q3. Why does standard Counting Sort iterate BACKWARD (from i = n - 1 down to 0) when placing elements into output[]?

(काउंटिंग सॉर्ट आउटपुट एरे भरते समय मूल एरे को पीछे से (n - 1 से 0 तक) क्यों पढ़ता है?)

(A) To sort the array in descending order

(B) To reduce space complexity from O(n + k) to O(1)

(C) To preserve STABILITY so later duplicates land at the higher pre-summed index first

(D) Because forward traversal produces wrong numeric values

Correct Answer: (C)

[EN] Prefix sum count[x] marks the LAST position of key x; decrementing from right-to-left keeps earlier occurrences to the left (stable).

[HI] प्रीफिक्स योग count[x] किसी मान की अंतिम स्थिति बताता है; पीछे से घटते हुए भरने पर बाद वाला डुप्लीकेट दाईं ओर और पहले वाला बाईं ओर रहता है (स्टेबल)।

Q4. Why MUST the digit-sorting subroutine inside LSD Radix Sort be STABLE?

(LSD रेडिक्स सॉर्ट के अंदर प्रत्येक अंक को सॉर्ट करने के लिए उपयोग किया जाने वाला सब-रूटीन स्टेबल (Stable) होना अनिवार्य क्यों है?)

(A) So ties on the current higher digit keep the already-sorted ordering from earlier lower-digit passes

(B) Otherwise time complexity becomes O(d * n^2)

(C) So negative integers become positive automatically

(D) Otherwise space complexity rises to O(n^2)

Correct Answer: (A)

[EN] If pass 2 (tens digit) scrambles equal tens keys like 21 and 29, the ones-digit sort from pass 1 gets destroyed.

[HI] यदि दहाई के अंक (जैसे 21 और 29 दोनों में 2) पर सॉर्ट करते समय स्थिरता न हो, तो पिछले चरण में इकाई अंक का बनाया गया सही क्रम बिगड़ जाएगा।

Q5. In what direction do standard LSD Radix Sort passes examine digits of decimal numbers like [329, 457, 657, 839]?

(मानक LSD रेडिक्स सॉर्ट [329, 457, 657, 839] जैसी संख्याओं के अंकों को किस क्रम में सॉर्ट करता है?)

(A) Only on the middle digit

(B) From Most Significant Digit to Least Significant Digit only

(C) Randomly across digit positions

(D) From Least Significant Digit (units place) to Most Significant Digit (hundreds place)

Correct Answer: (D)

[EN] LSD starts at units digit (9,7,7,9), then tens (2,5,5,3), then hundreds (3,4,6,8).

[HI] LSD का अर्थ ही Least Significant Digit (इकाई अंक) से शुरू होकर सबसे बड़े अंक (सैकड़ा) तक क्रमिक पास चलाना है।

Q6. Suppose you want to sort n integers whose values lie in [0, n^3 - 1] using Radix Sort with base b = n. What is the total running time?

(यदि n पूर्णांकों के मान [0, n^3 - 1] के बीच हों और रेडिक्स सॉर्ट आधार b = n से चलाया जाए, तो कुल समय कितना लगेगा?)

(A) O(n^2)

(B) O(n^3)

(C) O(n) (because d = 3 passes * O(n + n))

(D) O(n log n)

Correct Answer: (C)

[EN] In base n, any number < n^3 has at most d = 3 digits; each of the 3 passes takes O(n + n) = O(n), so 3 * O(n) = O(n).

[HI] आधार n में n^3 - 1 तक की संख्या अधिकतम d = 3 अंकों की होती है; 3 पास × O(n + n) करने पर कुल समय O(n) आता है।

Q7. When is Counting Sort an INAPPROPRIATE choice despite being O(n + k)?

(O(n + k) होने के बावजूद किस परिस्थिति में काउंटिंग सॉर्ट बहुत खराब विकल्प बन जाता है?)

(A) When sorting ASCII characters (0..255)

(B) When sorting 1,000,000 student marks in range 0..100

(C) When stability of records is required

(D) When sorting a small array of integers with an enormous range, e.g., [5, 2, 1000000000]

Correct Answer: (D)

[EN] For [5, 2, 1000000000], n = 3 yet k = 10^9, allocating gigabytes of zeroed count array and wasting O(k) time.

[HI] जब n बहुत कम (जैसे 3 तत्व) पर मान सीमा k बहुत विशाल (10^9) हो, तो काउंट एरे अरबों बाइट्स मेमोरी व समय बर्बाद कर देता है।

Q8. How can Counting Sort handle negative integers such as [-5, -1, 3, -5, 0]?

([-5, -1, 3, -5, 0] जैसी ऋणात्मक संख्याओं को काउंटिंग सॉर्ट से कैसे सॉर्ट किया जा सकता है?)

(A) Shift every key by subtracting min_val (-5): index = val - min_val with count array size (max_val - min_val + 1)

(B) Store negatives at negative array indices in C

(C) Negative numbers cannot ever be handled by Counting Sort

(D) Ignore negative signs and sort absolute values

Correct Answer: (A)

[EN] Subtracting min_val maps -5 to index 0 and +3 to index 8 cleanly in range [0..8].

[HI] न्यूनतम मान (min_val = -5) घटाकर हर संख्या को 0 से शुरू होने वाले धनात्मक इंडेक्स (val - min_val) पर मैप कर दिया जाता है।

Q9. Given n = 500 four-digit base-10 integers (d = 4, b = 10), roughly how many basic pass-operations does Radix Sort take via O(d(n + b))?

(4-अंकीय दशमलव संख्याओं (d = 4, b = 10) की n = 500 वस्तुओं पर रेडिक्स सॉर्ट की O(d(n + b)) गणना किसके अनुरूप है?)

(A) 4 * (500 + 10) = 2,040 step units

(B) 500 * log2(500) ~ 4,483 step units

(C) 10^4 = 10,000 step units

(D) 500^2 = 250,000 step units

Correct Answer: (A)

[EN] Each of d = 4 passes touches n = 500 elements and b = 10 digit buckets => 4*(500 + 10).

[HI] प्रत्येक 4 अंक पास में n = 500 और आधार b = 10 पर O(d*(n+b)) = 4*(500+10) कार्य होता है।

Q10. Are Counting Sort and Radix Sort in-place algorithms?

(क्या काउंटिंग सॉर्ट और रेडिक्स सॉर्ट इन-प्लेस (In-Place) एल्गोरिदम हैं?)

(A) Both are in-place only when n is prime

(B) No, both require O(n + k) or O(n + b) auxiliary array space

(C) Counting Sort is not in-place, but Radix Sort is O(1) in-place

(D) Yes, both sort in O(1) extra space

Correct Answer: (B)

[EN] Standard stable Counting Sort and LSD Radix Sort require auxiliary output and bucket count arrays.

[HI] स्थिर प्लेसमेंट और बकेट गिनती के लिए दोनों को अतिरिक्त आउटपुट व काउंट एरे चाहिए, अतः ये इन-प्लेस नहीं हैं।

Q11. Trace LSD Radix Sort on [170, 45, 75, 90, 802, 24, 2, 66]. What is the order immediately after Pass 1 (units digit)?

([170, 45, 75, 90, 802, 24, 2, 66] पर पहले पास (इकाई अंक) के ठीक बाद एरे का क्रम क्या होगा?)

(A) [170, 90, 802, 2, 24, 45, 75, 66]

(B) [802, 2, 24, 45, 66, 75, 90, 170]

(C) [170, 802, 2, 24, 45, 66, 75, 90]

(D) [2, 24, 45, 66, 75, 90, 170, 802]

Correct Answer: (A)

[EN] Units digits: 0 (170,90), 2 (802,2), 4 (24), 5 (45,75), 6 (66) — maintaining relative input order on ties.

[HI] इकाई अंक 0 वाले (170, 90), फिर 2 वाले (802, 2), फिर 4 (24), फिर 5 (45, 75), फिर 6 (66) क्रम में आएंगे।

Q12. Which non-comparison sorting algorithm distributes uniformly scattered floating-point numbers in [0.0, 1.0) into equal intervals and sorts each with Insertion Sort?

([0.0, 1.0) अंतराल की समान रूप से वितरित दशमलव संख्याओं को बकेट्स में बांटकर प्रत्येक को इंसर्शन सॉर्ट से सजाने वाला गैर-तुलनात्मक एल्गोरिदम कौन सा है?)

(A) Timsort

(B) Counting Sort

(C) Bucket Sort

(D) Shell Sort

Correct Answer: (C)

[EN] Bucket Sort achieves O(n) average time on uniformly distributed reals in [0, 1) (worst case O(n^2) if all land in one bucket).

[HI] बकेट सॉर्ट [0, 1) की समान वितरित दशमलव संख्याओं को n बकेट्स में रखकर औसत O(n) में सॉर्ट करता है।

Q13. Can Radix Sort be used to sort fixed-length strings (like 5-letter English words)?

(क्या समान लंबाई वाली स्ट्रिंग्स (जैसे 5-अक्षरीय शब्दों) को सॉर्ट करने के लिए रेडिक्स सॉर्ट उपयोग किया जा सकता है?)

(A) Only after hashing strings to floats

(B) Yes, by processing characters from the rightmost index (d-1) to index 0 using base b = 26 or 256

(C) Yes, but only in O(n^2) time

(D) No, Radix Sort works strictly on decimal integers only

Correct Answer: (B)

[EN] Treating each character position as a digit in base 256 (ASCII) lets LSD Radix Sort sort strings in O(d*(n+256)).

[HI] हाँ, प्रत्येक अक्षर को आधार 26 या 256 (ASCII) के अंक की तरह मानकर दाएँ से बाएँ पास चलाकर शब्दों को सॉर्ट किया जा सकता है।

Q14. If two items in Counting Sort have count[5] == 8 before the reverse loop (after prefix sums), what does '8' tell us?

(प्रीफिक्स योग के बाद यदि count[5] == 8 हो, तो इसका क्या अर्थ है?)

(A) The value 5 appears 8 times

(B) Maximum key in array is 8

(C) The value 8 appears 5 times

(D) There are 8 elements in the input with value <= 5 (so the last '5' belongs at output index 7)

Correct Answer: (D)

[EN] Prefix sums accumulate counts of all keys <= x; thus the rightmost copy of 5 goes at 0-based index 8 - 1 = 7.

[HI] प्रीफिक्स योग count[5] बताता है कि एरे में <= 5 वाले कुल 8 तत्व हैं, इसलिए अंतिम 5 इंडेक्स 7 पर जाएगा।

Q15. Which statement is NOT true about Counting Sort and Radix Sort?

(काउंटिंग और रेडिक्स सॉर्ट के बारे में इनमें से कौन सा कथन असत्य है?)

(A) Radix Sort achieves O(d * (n + b)) complexity

(B) Counting Sort runs in O(n + k) time and space

(C) Both algorithms are stable when implemented properly

(D) Both algorithms are in-place and work on arbitrary comparison objects without key ranges

Correct Answer: (D)

[EN] Neither is in-place, and both rely on integer/character bucket ranges rather than arbitrary object comparators.

[HI] ये दोनों न तो इन-प्लेस हैं और न ही बिना की-रेंज वाले मनमाने ऑब्जेक्ट्स की सीधी तुलना पर काम करते हैं।

Q16. Why might Quick Sort still outperform Radix Sort for moderate n (say n = 1,000 32-bit integers) in practice?

(मध्यम आकार के डेटा (जैसे 1,000 इंटीजर) पर सैद्धांतिक O(n) होने पर भी क्विक सॉर्ट रेडिक्स सॉर्ट से तेज क्यों हो सकता है?)

(A) Quick Sort uses no comparisons

(B) Radix Sort performs O(n^2) passes on 32-bit ints

(C) Radix Sort's multi-pass bucket allocations and random scatter writes have larger constant factors and cache overhead for small n

(D) Quick Sort has O(1) worst-case time

Correct Answer: (C)

[EN] For small/medium n, O(n log n) with tight in-place cache hits beats d * (n + b) extra allocations and passes.

[HI] कम n पर रेडिक्स सॉर्ट के कई पास व बफर एलोकेशन के ओवरहेड की तुलना में इन-प्लेस क्विक सॉर्ट का कैश प्रदर्शन बेहतर रहता है।

Q17. Within Counting Sort and Radix Sort: Non-Comparison Linear Sorting, which non-comparison method directly maps to: "O(n + k) time and O(n + k) space"?

(Counting Sort and Radix Sort: Non-Comparison Linear Sorting में कौन सा Non-Comparison Method सीधे "O(n + k) time and O(n + k) space" से संबंधित है?)

(A) Counting Sort Complexity

(B) LSD Radix Sort Runtime

(C) Comparison Lower Bound

(D) Reverse Placement Loop

Correct Answer: (A)

[EN] In Counting Sort and Radix Sort: Non-Comparison Linear Sorting, 'Counting Sort Complexity' handles 'O(n + k) time and O(n + k) space' (Efficient only when key range k is O(n) or small).

[HI] Counting Sort and Radix Sort: Non-Comparison Linear Sorting में 'Counting Sort Complexity' का कार्य/विवरण 'O(n + k) time and O(n + k) space' (Efficient only when key range k is O(n) or small) है।

Q18. Which option accurately describes 'Reverse Placement Loop' in Counting Sort and Radix Sort: Non-Comparison Linear Sorting?

(Counting Sort and Radix Sort: Non-Comparison Linear Sorting के संदर्भ में 'Reverse Placement Loop' की सही विशेषता कौन सी है?)

(A) Iterates n-1 down to 0 into output[]

(B) O(d * (n + b)) for d digits, base b

(C) Evades Omega(n log n) decision tree limit

(D) O(n + k) time and O(n + k) space

Correct Answer: (A)

[EN] 'Reverse Placement Loop' provides 'Iterates n-1 down to 0 into output[]' — key point: Guarantees stability for duplicate keys/records.

[HI] 'Reverse Placement Loop' का मुख्य विवरण 'Iterates n-1 down to 0 into output[]' है (Guarantees stability for duplicate keys/records)।

Q19. In Counting Sort and Radix Sort: Non-Comparison Linear Sorting, identify the correct parameter for the specification: "O(d * (n + b)) for d digits, base b".

(Counting Sort and Radix Sort: Non-Comparison Linear Sorting में "O(d * (n + b)) for d digits, base b" विवरण किस विकल्प के लिए सही है?)

(A) Comparison Lower Bound

(B) Counting Sort Complexity

(C) LSD Radix Sort Runtime

(D) Reverse Placement Loop

Correct Answer: (C)

[EN] 'LSD Radix Sort Runtime' corresponds to 'O(d * (n + b)) for d digits, base b' (Requires a STABLE subroutine like Counting Sort).

[HI] 'LSD Radix Sort Runtime' का संबंध 'O(d * (n + b)) for d digits, base b' (Requires a STABLE subroutine like Counting Sort) से है।

Q20. Considering Counting Sort and Radix Sort: Non-Comparison Linear Sorting, what key behavior defines 'Comparison Lower Bound'?

(Counting Sort and Radix Sort: Non-Comparison Linear Sorting में 'Comparison Lower Bound' की मुख्य भूमिका या मान क्या है?)

(A) Evades Omega(n log n) decision tree limit

(B) Iterates n-1 down to 0 into output[]

(C) O(n + k) time and O(n + k) space

(D) O(d * (n + b)) for d digits, base b

Correct Answer: (A)

[EN] 'Comparison Lower Bound' represents 'Evades Omega(n log n) decision tree limit' (Uses key values/digits as direct bucket indices).

[HI] 'Comparison Lower Bound' का अर्थ/मान 'Evades Omega(n log n) decision tree limit' है (Uses key values/digits as direct bucket indices)।

Counting Sort and Radix Sort: Non-Comparison Linear Sorting — Exam FAQs

Q1: Why isn't Counting Sort used as the default sort in C++ or Python standard libraries?

C++ या Python की मानक लाइब्रेरी में काउंटिंग सॉर्ट डिफ़ॉल्ट क्यों नहीं होता?

[EN] Counting Sort works only on bounded integer keys and allocates O(k) extra memory; general-purpose standard sorts must work on arbitrary data types (floats, strings, custom structs) via a comparison function.

[HI] काउंटिंग सॉर्ट केवल सीमित इंटीजर रेंज पर काम करता है और O(k) अतिरिक्त मेमोरी मांगता है, जबकि मानक लाइब्रेरी को फ्लोट, स्ट्रिंग व कस्टम ऑब्जेक्ट्स सभी को बिना अतिरिक्त रेंज सीमा के सॉर्ट करना होता है।

Q2: What happens if we run Counting Sort's placement loop forward (0 to n-1) instead of backward?

काउंटिंग सॉर्ट का प्लेसमेंट लूप पीछे से चलाने के बजाय आगे से (0 से n-1) चला दें तो क्या होगा?

[EN] All values will still end up sorted numerically, EXCEPT duplicate records will be placed in reverse relative order—destroying stability and breaking LSD Radix Sort!

[HI] संख्याएँ तो सही क्रम में लग जाएंगी, लेकिन समान कुंजियों वाले रिकॉर्ड उलटे क्रम में लग जाएंगे जिससे स्थिरता नष्ट हो जाएगी और रेडिक्स सॉर्ट गलत उत्तर देने लगेगा।

Q3: What is the difference between LSD and MSD Radix Sort?

LSD और MSD रेडिक्स सॉर्ट में क्या अंतर है?

[EN] LSD sorts from Least Significant Digit to Most Significant Digit iteratively in fixed passes and needs a stable sub-sort, whereas MSD starts at Most Significant Digit recursively (natural for variable-length strings) partitioning into buckets.

[HI] LSD छोटे से बड़े अंक की ओर क्रमिक पास चलाता है व स्टेबल सब-सॉर्ट मांगता है, जबकि MSD सबसे बड़े अंक से रिकर्सिवली बकेट विभाजन करता है (अलग-अलग लंबाई की स्ट्रिंग्स में उपयोगी)।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)