सॉर्टिंग (Sorting) का अर्थ है किसी संग्रह के तत्वों को एक निश्चित क्रम में व्यवस्थित करना। यह क्रम आरोही (ascending) या अवरोही (descending) हो सकता है। उदाहरण के लिए, संख्याओं की सूची [7, 2, 9, 1] को आरोही क्रम में सॉर्ट करने पर [1, 2, 7, 9] प्राप्त होती है। सॉर्टिंग कंप्यूटर विज्ञान की एक मौलिक क्रिया है क्योंकि सॉर्ट किया गया डेटा खोज, मर्जिंग और विश्लेषण में अधिक कुशल होता है। बाइनरी सर्च केवल सॉर्ट किए हुए डेटा पर ही कार्य करती है।
पाइथन में सॉर्टिंग के लिए sort() और sorted() जैसी अंतर्निहित विधियाँ हैं, परंतु परीक्षा की दृष्टि से हमें चयन सॉर्ट (Selection Sort), बबल सॉर्ट (Bubble Sort), इंसर्शन सॉर्ट (Insertion Sort) जैसे मूल एल्गोरिथ्मों की समझ आवश्यक है। सॉर्टिंग एल्गोरिथ्मों की दक्षता को उनकी समय जटिलता (Time Complexity) के आधार पर मापा जाता है।
सॉर्टिंग के अनेक लाभ हैं:
चयन सॉर्ट की अवधारणा बहुत सरल है - यह हर बार सूची में से सबसे छोटा (या सबसे बड़ा) तत्व चुनकर उसे सही स्थान पर रखता है। यह क्रमबद्ध सूची को धीरे-धीरे बनाता है। सूची को दो भागों में बाँटा जाता है - सॉर्ट किया हुआ (बायाँ) और असॉर्ट किया हुआ (दायाँ)। हर पास में असॉर्ट भाग से न्यूनतम तत्व चुना जाता है और उसे सॉर्ट भाग के अंत में रखा जाता है।
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
print(selection_sort([64, 25, 12, 22, 11]))
# Output: [11, 12, 22, 25, 64]
बबल सॉर्ट में आसन्न (adjacent) तत्वों की तुलना कर उन्हें स्वैप किया जाता है। पहले पास में सबसे बड़ा तत्व अंतिम स्थान पर पहुँचता है, दूसरे पास में दूसरा सबसे बड़ा, और इसी प्रकार सूची धीरे-धीरे सॉर्ट होती है। यह इसलिए कहलाता है क्योंकि बड़े तत्व "बुलबुले" की तरह ऊपर उठते जाते हैं।
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([64, 25, 12, 22, 11]))
# Output: [11, 12, 22, 25, 64]
यदि किसी पास में कोई स्वैप नहीं होता तो सूची पहले से सॉर्ट है। एक झंडे (flag) से हम लूप को जल्दी समाप्त कर सकते हैं:
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
इंसर्शन सॉर्ट की कल्पना ताश के पत्तों को क्रम से सजाने की तरह की जा सकती है। यह सूची के दूसरे तत्व से प्रारंभ करता है और प्रत्येक तत्व को उसकी सही स्थिति में डालता है, साथ ही बड़े तत्वों को दाईं ओर सरकाता है।
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
print(insertion_sort([64, 25, 12, 22, 11]))
# Output: [11, 12, 22, 25, 64]
पाइथन में सॉर्टिंग के लिए दो अंतर्निहित सुविधाएँ हैं:
sort(): यह सूची को स्थान पर (in-place) सॉर्ट करती है और मूल सूची को बदल देती है।sorted(): यह एक नई सॉर्ट की हुई सूची लौटाती है, मूल सूची अपरिवर्तित रहती है।numbers = [5, 2, 8, 1]
numbers.sort() # in-place, numbers अब [1, 2, 5, 8]
print(numbers)
original = [3, 1, 2]
new_list = sorted(original) # new_list = [1, 2, 3], original अपरिवर्तित
print(new_list)
print(original)
# अवरोही क्रम
numbers.sort(reverse=True)
print(numbers)
# टपल की सूची में कुंजी के आधार पर
students = [("अनु", 85), ("रवि", 92), ("कविता", 78)]
students.sort(key=lambda x: x[1])
print(students)
दोनों विधियों में reverse=True देकर अवरोही क्रम में सॉर्ट किया जा सकता है, और key तर्क से कस्टम मानदंड निर्धारित किया जा सकता है।
| एल्गोरिथ्म | सर्वश्रेष्ठ | औसत | सबसे खराब | स्थिर? |
|---|---|---|---|---|
| बबल सॉर्ट | O(n) | O(n²) | O(n²) | हाँ |
| चयन सॉर्ट | O(n²) | O(n²) | O(n²) | नहीं |
| इंसर्शन सॉर्ट | O(n) | O(n²) | O(n²) | हाँ |
बबल और इंसर्शन सॉर्ट पहले से सॉर्ट की गई सूची पर O(n) में कार्य करते हैं, जबकि चयन सॉर्ट हमेशा O(n²) रहता है।
| एल्गोरिथ्म | मूल विचार | समय जटिलता (सबसे खराब) | स्थिरता |
|---|---|---|---|
| चयन सॉर्ट | न्यूनतम तत्व चुनकर सही स्थान | O(n²) | अस्थिर |
| बबल सॉर्ट | आसन्न तत्वों की तुलना व स्वैप | O(n²) | स्थिर |
| इंसर्शन सॉर्ट | तत्व को सही स्थिति में डालना | O(n²) | स्थिर |
| विधि | कार्य | मूल सूची |
|---|---|---|
list.sort() |
स्थान पर सॉर्ट करना | बदल जाती है |
sorted(list) |
नई सूची लौटाता है | अपरिवर्तित |
reverse=True |
अवरोही क्रम | - |
key=फलन |
कस्टम मानदंड | - |
a, b = b, a सही है, परंतु टेम्परेरी चर से स्वैप करते समय क्रम गलत होने पर डेटा खो जाता है।range(n - 1 - i) की जगह range(n - 1) लिखना - बार-बार सॉर्ट किए तत्वों की तुलना होती है पर परिणाम सही रहता है परंतु अकुशल होता है; उचित सीमा रखना आवश्यक है।arr[i] से arr[j] की तुलना कर स्वैप करना बबल सॉर्ट जैसा हो जाता है; चयन सॉर्ट में केवल न्यूनतम का सूचकांक बदलता है।key की स्थिति: तत्व को सही स्थान पर डालते समय बड़े तत्वों को स्थानांतरित करने के बाद ही arr[j+1] = key करना चाहिए।sort() और sorted() का भ्रम: sort() मूल सूची बदलता है, sorted() नई सूची देता है। यदि आप दोनों का परिणाम प्रिंट करने का प्रयास करें तो sort() का None लौटता है।sort() in-place है और sorted() नई सूची लौटाता है - यह अंतर वस्तुनिष्ठ प्रश्नों में नियमित रूप से आता है।key और reverse तर्कों के साथ अभ्यास करें क्योंकि कोड-लिखने के प्रश्नों में ये आते हैं।सॉर्टिंग डेटा को निश्चित क्रम में व्यवस्थित करने की मौलिक प्रक्रिया है। चयन सॉर्ट न्यूनतम तत्व को सही स्थान पर रखता है, बबल सॉर्ट आसन्न तत्वों की तुलना से सबसे बड़े तत्व को ऊपर लाता है, और इंसर्शन सॉर्ट प्रत्येक तत्व को उसकी सही स्थिति में डालता है। तीनों की औसत समय जटिलता O(n²) है, परंतु बबल और इंसर्शन सॉर्ट पहले से सॉर्ट की सूची पर O(n) में कार्य करते हैं। पाइथन की अंतर्निहित sort() और sorted() विधियाँ सरल और कुशल सॉर्टिंग प्रदान करती हैं। एल्गोरिथ्मों की चरणबद्ध समझ और अभ्यास परीक्षा में सफलता की कुंजी है।