तुलना-रहित क्रमबद्धकरण और Python का sort()
पूर्णांक ऐरे के लिए counting sort और radix sort समझिए तथा जानिए कि अंतर्निहित sort कॉल के पीछे Python का Timsort कैसे काम करता है।
तुलना-रहित क्रमबद्धकरण और Python का sort(), CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
तुलनाओं के लिए O(n log n) की निचली सीमा
कोई भी क्रमबद्धता एल्गोरिदम जो क्रम निर्धारित करने के लिए केवल तत्वों की तुलनाओं का उपयोग करता है, उसे सबसे खराब स्थिति में कम-से-कम Ω(n log n) तुलनाएँ करनी पड़ती हैं। यह निर्णय वृक्ष तर्क से सिद्ध होता है: n तत्वों को क्रमबद्ध करने के लिए n! संभावित क्रमों के बीच अंतर करना आवश्यक है। एक द्विआधारी निर्णय वृक्ष (जिसका प्रत्येक नोड एक तुलना है) को कम-से-कम log₂(n!) ≈ n log₂(n) स्तरों की आवश्यकता होती है। इस सीमा को पार करने के लिए हमें तत्वों के बारे में अतिरिक्त जानकारी चाहिए — जैसे कि वे सीमित परास वाले पूर्णांक हों।
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingकाउंटिंग सॉर्ट: आवृत्ति के आधार पर क्रमबद्धता
काउंटिंग सॉर्ट प्रत्येक मान की आवृत्ति गिनकर और फिर उन गिनतियों से क्रमबद्ध ऐरे का पुनर्निर्माण करके काम करता है। इसके लिए मानों की सीमा [0, k) पहले से ज्ञात होना आवश्यक है। समय जटिलता: O(n + k); स्थान जटिलता: O(k)। जब n की तुलना में k छोटा हो (जैसे 0-120 की आयु या एकल अंकों को क्रमबद्ध करना), तो काउंटिंग सॉर्ट सभी तुलना-आधारित सॉर्ट से बेहतर प्रदर्शन करता है। बड़े k के लिए O(k) स्थान लागत इसे अव्यावहारिक बना देती है।
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)संचयी गणनाओं के साथ स्थिर काउंटिंग sort
स्थिर काउंटिंग sort (किसी कुंजी के आधार पर वस्तुओं को क्रमबद्ध करते समय महत्वपूर्ण) के लिए संचयी गणनाएँ इस तरह निकालिए कि cum[v] परिणाम में v मान की शुरुआती स्थिति दे। आगत ऐरे को दाएँ से बाएँ स्कैन कीजिए, प्रत्येक तत्व को cum[key] - 1 स्थिति पर रखिए और उस स्थिति का मान घटाते जाइए। इससे स्थिर sort प्राप्त होता है—समान कुंजी वाले तत्व अपने मूल सापेक्ष क्रम में रहते हैं।
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]रेडिक्स sort: अंक-दर-अंक sort करें
रेडिक्स sort पूर्णांकों को कम महत्वपूर्ण अंक (LSD) से अधिक महत्वपूर्ण अंक (MSD) तक, प्रत्येक अंक-स्थिति पर एक स्थिर sort (जैसे काउंटिंग sort) का उपयोग करके, अंक-दर-अंक क्रमबद्ध करता है। d चरणों के बाद (प्रत्येक अंक के लिए एक चरण) ऐरे पूरी तरह क्रमबद्ध हो जाता है। समय जटिलता: O(d × (n + k)), जहाँ d = अंकों की संख्या और k = आधार (आमतौर पर 10)। W से सीमित n पूर्णांकों के लिए d = log_k(W), इसलिए कुल जटिलता O(n log_k(W)) होती है।
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]बकेट sort: बकेट में बाँटें
बकेट sort मान-सीमा के आधार पर तत्वों को निश्चित संख्या में बकेट में बाँटता है, प्रत्येक बकेट को क्रमबद्ध करता है (छोटे बकेट के लिए इन्सर्शन sort का उपयोग करके), और फिर उन्हें जोड़ देता है। [0, 1) में समान रूप से वितरित डेटा के लिए, n बकेट औसत O(n) समय देते हैं। औसत समय: O(n + k), सबसे खराब स्थिति में O(n²) (जब सभी तत्व एक ही बकेट में हों)। यह तब सबसे उपयोगी होता है जब डेटा का वितरण ज्ञात और लगभग समान हो।
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listPython का टिमसॉर्ट पर्दे के पीछे
Python का sorted() और list.sort() टिमसॉर्ट का उपयोग करते हैं, जिसे Tim Peters ने 2002 में डिज़ाइन किया था। टिमसॉर्ट मर्ज sort और इन्सर्शन sort का मिश्रण है। यह 'स्वाभाविक रन' (पहले से क्रमबद्ध उप-अनुक्रम) खोजता है और 64 तत्वों तक के रन बनाने के लिए इन्सर्शन sort का उपयोग करता है। फिर यह मर्ज sort की सहायता से कई अनुकूलनों के साथ रनों को मिलाता है: तेज़ छलाँग (जब कोई एक रन स्पष्ट रूप से बड़ा हो तो तत्वों को समूहों में छोड़ना) और रन-लंबाई स्टैकिंग।
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Python के sort() और sorted() में मुख्य अंतर
list.sort() उसी सूची में क्रमबद्ध करता है, None लौटाता है और केवल सूचियों पर काम करता है। sorted(iterable) किसी भी पुनरावर्तनीय वस्तु (ट्यूपल, जनरेटर या शब्दकोश) पर काम करता है और एक नई सूची लौटाता है। दोनों key और reverse पैरामीटर स्वीकार करते हैं। एक सामान्य त्रुटि यह है कि lst.sort() के लौटाए हुए मान को किसी चर में रखकर यह सोचा जाए कि वह None क्यों है। जब आपको क्रमबद्ध प्रति चाहिए और मूल सूची को बनाए रखना हो, तो हमेशा sorted() का उपयोग कीजिए।
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)साक्षात्कारों में कस्टम sort कुंजियाँ
Python का sort एक key फ़ंक्शन स्वीकार करता है, जिसका मूल्यांकन प्रत्येक तत्व के लिए एक बार किया जाता है (C के उस तुलनाकर्ता के विपरीत जिसे प्रत्येक जोड़ी के लिए बुलाया जाता है)। साक्षात्कारों में सामान्य sort कुंजियाँ हैं: स्ट्रिंग की लंबाई के लिए len, अवरोही क्रम के लिए lambda x: -x, बहु-कुंजी sort के लिए lambda x: (x[1], x[0]), और अक्षर-रूप की अनदेखी करने के लिए str.lower। Python का sort स्थिर होने की गारंटी देता है, इसलिए बहु-कुंजी sort सही ढंग से काम करते हैं।
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]साक्षात्कारों में प्रत्येक sort का उपयोग कब करें
परिस्थिति के अनुसार सही sort चुनिए:
- Python के sorted()/list.sort() का उपयोग करें: सभी साक्षात्कार समस्याओं के लिए डिफ़ॉल्ट विकल्प—टिमसॉर्ट सर्वोत्तम है
- काउंटिंग sort: जब मान छोटी सीमा वाले पूर्णांक हों (0 से k तक और k छोटा हो)
- रेडिक्स sort: जब ज्ञात बिट-चौड़ाई या अंकों की संख्या वाले बहुत-से पूर्णांकों को क्रमबद्ध करना हो
- बकेट sort: जब डेटा किसी ज्ञात सीमा में समान रूप से वितरित फ्लोटिंग-पॉइंट मान हों
- मर्ज sort लागू करें: जब शुरू से एक स्थिर O(n log n) sort लिखने को कहा जाए
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]sort के बिना sort: हीप से शीर्ष-k
साक्षात्कार की कई समस्याएँ पूरी तरह sort किए बिना 'sort-जैसे' परिणाम माँगती हैं। शीर्ष-k तत्व खोजने के लिए आकार k का min-heap O(n log k) समय लेता है—जब k << n हो, तो यह O(n log n) से तेज़ है। kth_largest तत्व खोजने के लिए quickselect की औसत जटिलता O(n) है। माध्यिका खोजने के लिए दो-हीप वाली विधि प्रत्येक प्रविष्टि पर O(log n) समय लेती है। पूर्ण sort के तेज़ विकल्प के रूप में इन आंशिक-sort विधियों को जानना उपयोगी है।
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
if lo >= hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]; i = lo - 1
for j in range(lo, hi):
if nums[j] >= pivot: i+=1; nums[i],nums[j]=nums[j],nums[i]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5बहु-कुंजी sorting में sort की स्थिरता
स्थिरता सही बहु-कुंजी sorting को संभव बनाती है: पहले द्वितीयक कुंजी के अनुसार स्थिर रूप से sort कीजिए, फिर प्राथमिक कुंजी के अनुसार स्थिर रूप से sort कीजिए। प्राथमिक कुंजी में समान मान होने पर द्वितीयक क्रम सुरक्षित रहता है। इस तकनीक का उपयोग डेटाबेस में (ORDER BY col1, col2) और radix sort में किया जाता है (समग्र एल्गोरिदम के सही होने के लिए प्रत्येक अंक-चरण स्थिर होना चाहिए)। Python का sort हमेशा स्थिर होता है, इसलिए यह तरीका विश्वसनीय रूप से काम करता है।
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)त्वरित जाँच
इस पाठ में Data Structures & Algorithms — Coding Interview Prep की अवधारणाओं की अपनी समझ जाँचिए।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: तुलना-आधारित sort की निचली सीमा O(n log n) होती है—इस सीमा को तोड़ने के लिए सीमित पूर्णांकों जैसी गैर-तुलनात्मक जानकारी आवश्यक है, काउंटिंग sort आवृत्तियों की गणना करके O(n + k) प्राप्त करता है, radix sort अंकों को संसाधित करके कुल O(d × (n + k)) लेता है, और बकेट sort समान वितरण का लाभ उठाकर औसतन O(n) प्राप्त करता है, और Python का टिमसॉर्ट व्यावहारिक डिफ़ॉल्ट विकल्प है—स्थिर, सबसे खराब स्थिति में O(n log n), सर्वोत्तम स्थिति में O(n), और वास्तविक डेटा पर हाथ से लिखे किसी भी विकल्प से तेज़। अब हम पारंपरिक binary search में निपुण होंगे।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “तुलना-रहित क्रमबद्धकरण और Python का sort()” पाठ निःशुल्क है?
हाँ—“तुलना-रहित क्रमबद्धकरण और Python का sort()” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“तुलना-रहित क्रमबद्धकरण और Python का sort()” में मैं क्या सीखूँगा?
पूर्णांक ऐरे के लिए counting sort और radix sort समझिए तथा जानिए कि अंतर्निहित sort कॉल के पीछे Python का Timsort कैसे काम करता है। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।
“तुलना-रहित क्रमबद्धकरण और Python का sort()” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Bubble Sort और Insertion Sort
- Merge Sort: विभाजित करें, क्रमबद्ध करें, मिलाएँ
- Quick Sort और Pivot चयन
- तुलना-रहित क्रमबद्धकरण और Python का sort()