ये तीन सरल O(n²) तुलना सॉर्ट हैं। वे बड़े इनपुट पर धीमे हैं लेकिन समझने में आसान हैं और सॉर्टिंग मैकेनिक्स सिखाने के लिए उपयोगी हैं।
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # element to place
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift bigger elements right
j -= 1
arr[j + 1] = key # drop key into the gap
return arr
insertion_sort([5, 2, 4, 1]) # -> [1, 2, 4, 5]
| सॉर्ट | सर्वोत्तम | सबसे बुरा | स्थिर | स्थान में |
|---|---|---|---|---|
| बबल | O(n) | O(n²) | हाँ | हाँ |
| सिलेक्शन | O(n²) | O(n²) | नहीं | हाँ |
| इन्सर्शन | O(n) | O(n²) | हाँ | हाँ |
इन्सर्शन सॉर्ट छोटी या लगभग-सॉर्ट की गई सरणियों के लिए सच में तेज़ है और हाइब्रिड सॉर्ट के अंदर उपयोग किया जाता है। बड़े अनसॉर्ट किए गए डेटा पर इन तीनों से बचें — इसके बजाय O(n log n) सॉर्ट का उपयोग करें।
ये सॉर्ट उन्नत एल्गोरिदम से निपटने से पहले इनवेरिएंट्स, स्वैप और स्थिरता के लिए अंतर्ज्ञान बनाते हैं।
इन्सर्शन सॉर्ट विशेष रूप से उत्पादन सॉर्ट (जैसे Timsort) के अंदर छोटी सबएरे के लिए दिखाई देता है।
यह जानना कि वे क्यों O(n²) हैं, O(n log n) सॉर्ट तक छलांग को अर्थपूर्ण बनाता है।