हे तीन साधे 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]
| Sort | Best | Worst | Stable | In-place |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Yes | Yes |
| Selection | O(n²) | O(n²) | No | Yes |
| Insertion | O(n) | O(n²) | Yes | Yes |
इन्सर्शन सॉर्ट लहान किंवा जवळजवळ सॉर्टेड अॅरे साठी खरोखर वेगवान आहे आणि हायब्रिड सॉर्ट्स मध्ये वापरला जातो. मोठ्या असॉर्टेड डेटावर सर्व तीन टाळा - त्याऐवजी O(n log n) सॉर्ट वापरा.
हे सॉर्ट्स इनव्हेरिएंट्स, स्वॅप्स आणि स्थिरता बद्दल अंतर्ज्ञान तयार करतात प्रत्यक्ष अल्गोरिदमला पूर्ण करण्यापूर्वी.
इन्सर्शन सॉर्ट विशेषतः उत्पादन सॉर्ट्स (जसे Timsort) मध्ये लहान सबअॅरे साठी दिसते.
केन हे O(n²) आहेत हे समजून गणना O(n log n) सॉर्ट्सपर्यंत अर्थपूर्ण बनवते.