Αυτές είναι τρεις απλές συγκριτικές ταξινομήσεις 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]
| Ταξινόμηση | Καλύτερο | Χειρότερο | Σταθερή | Στη θέση |
|---|---|---|---|---|
| Bubble | O(n) | O(n²) | Ναι | Ναι |
| Selection | O(n²) | O(n²) | Όχι | Ναι |
| Insertion | O(n) | O(n²) | Ναι | Ναι |
Το Insertion sort είναι πραγματικά γρήγορο για μικρούς ή σχεδόν ταξινομημένους πίνακες και χρησιμοποιείται μέσα σε υβριδικές ταξινομήσεις. Αποφύγετε και τα τρία σε μεγάλα αταξινόμητα δεδομένα — χρησιμοποιήστε αντί αυτού O(n log n) ταξινομήσεις.
Αυτές οι ταξινομήσεις χτίζουν διαίσθηση για αναλλοίωτα, ανταλλαγές και σταθερότητα πριν προχωρήσετε σε προηγμένους αλγορίθμους.
Το Insertion sort ιδιαίτερα εμφανίζεται μέσα σε ταξινομήσεις παραγωγής (όπως Timsort) για μικροσκοπικές υποπίνακες.
Το γεγονός ότι ξέρετε γιατί είναι O(n²) κάνει το άλμα σε O(n log n) ταξινομήσεις ουσιαστικό.