ეს სამი მარტივი O(n²) შედარების დალაგების ალგორითმია. ისინი ნელია დიდ შეყვანებზე, მაგრამ ადვილი გასაგებია და სასარგებლოა დალაგების მექანიკის სწავლებისთვის.
ეს სამი მარტივი 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 |
Insertion sort ნამდვილად სწრაფია მცირე ან თითქმის დახარისხებული მასივებისთვის და გამოიყენება ჰიბრიდული დალაგების შიგნით. თავი შეიკავეთ სამივე ალგორითმისგან დიდი დაუხარისხებელი მონაცემებზე — გამოიყენეთ O(n log n) დალაგება.
ეს დალაგებები აკმაყოფილებს ინტუიციას უცვლელობაზე, ჩანაცვლებაზე და სტაბილურობაზე ხელმისაწვდომი ალგორითმების წინ.
Insertion sort განსაკუთრებით ჩნდება პროდუქციის დალაგებაში (როგორც Timsort) მცირე ქვემასივებისთვის.
კი რატომ არის ისინი O(n²) ხდის O(n log n) დალაგებაზე გადასვლას აზრიანი.