Πολυπλοκότητα χρόνου ταξινόμησης εισαγωγής

Σκεφτείτε τους παρακάτω αριθμούς:

50 60 30 10 80 70 20 40

Εάν αυτή η λίστα ταξινομηθεί με αύξουσα σειρά, θα είναι:

10 20 30 40 50 60 70 80

Εάν ταξινομηθεί με φθίνουσα σειρά, θα είναι:

80 70 60 50 40 30 20 10

Η ταξινόμηση εισαγωγής είναι ένας αλγόριθμος ταξινόμησης που χρησιμοποιείται για την ταξινόμηση της λίστας με αύξουσα ή φθίνουσα σειρά. Αυτό το άρθρο ασχολείται μόνο με την ταξινόμηση κατά αύξουσα σειρά. Η ταξινόμηση με φθίνουσα σειρά ακολουθεί την ίδια λογική που δίνεται σε αυτό το έγγραφο. Ο στόχος αυτού του άρθρου είναι να εξηγήσει το είδος εισαγωγής. Ο προγραμματισμός γίνεται στο ακόλουθο παράδειγμα στο C. Η ταξινόμηση εισαγωγής εξηγείται εδώ χρησιμοποιώντας έναν πίνακα.

Αλγόριθμος για Ταξινόμηση Εισαγωγής

Δίνεται μια λίστα χωρίς ταξινόμηση. Ο στόχος είναι να ταξινομήσετε τη λίστα με αύξουσα σειρά χρησιμοποιώντας την ίδια λίστα. Η ταξινόμηση ενός μη ταξινομημένου πίνακα χρησιμοποιώντας τον ίδιο πίνακα λέγεται ότι ταξινομεί επιτόπου. Εδώ χρησιμοποιείται η μηδενική ευρετηρίαση. Τα βήματα είναι τα εξής:

• • Η λίστα σαρώνεται από την αρχή.
  • Ενώ η σάρωση συνεχίζεται, οποιοσδήποτε αριθμός μικρότερος από τον προκάτοχό του ανταλλάσσεται με τον προκάτοχό του.
  • Αυτή η εναλλαγή συνεχίζεται στη λίστα, έως ότου δεν είναι πλέον δυνατή η ανταλλαγή.
  • Όταν η σάρωση φτάσει στο τέλος, η ταξινόμηση έχει ολοκληρωθεί.

Εικονογράφηση ταξινόμησης εισαγωγής

Όταν αντιμετωπίζουμε την πολυπλοκότητα του χρόνου, είναι η χειρότερη περίπτωση που συνήθως λαμβάνεται υπόψη. Η χειρότερη διάταξη για την προηγούμενη λίστα είναι:

80 70 60 50 40 30 20 10

Υπάρχουν οκτώ στοιχεία με δείκτες από μηδέν έως 7.

Στο μηδέν δείκτη, η σάρωση πηγαίνει στο 80. Αυτή είναι μια κίνηση. Αυτή η κίνηση είναι μια επέμβαση. Υπάρχει συνολικά μία επέμβαση μέχρι στιγμής (μία κίνηση, καμία σύγκριση και καμία ανταλλαγή). Το αποτέλεσμα είναι:

| 80 70 60 50 40 30 20 10

Στον δείκτη ένα, υπάρχει μια κίνηση στο 70. Το 70 συγκρίνεται με το 80. Το 70 και το 80 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Μια σύγκριση είναι επίσης μια λειτουργία. Μια εναλλαγή είναι επίσης μια λειτουργία. Αυτή η ενότητα παρέχει τρεις λειτουργίες. Υπάρχουν συνολικά τέσσερις πράξεις μέχρι στιγμής (1 + 3 = 4). Το αποτέλεσμα είναι το εξής:

70 | 80 60 50 40 30 20 10

Στον δείκτη δύο, υπάρχει μια κίνηση στο 60. Το 60 συγκρίνεται με το 80, μετά το 60 και το 80 ανταλλάσσονται. Το 60 συγκρίνεται με το 70, μετά το 60 και το 70 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Δύο συγκρίσεις είναι δύο πράξεις. Δύο ανταλλαγές είναι δύο λειτουργίες. Αυτή η ενότητα παρέχει πέντε λειτουργίες. Υπάρχουν συνολικά εννέα επεμβάσεις μέχρι στιγμής (4 + 5 = 9). Το αποτέλεσμα είναι το εξής:

60 70 | 80 50 40 30 20 10

Στον δείκτη τρία, υπάρχει μια κίνηση στο 50. Το 50 συγκρίνεται με το 80, μετά το 50 και το 80 ανταλλάσσονται. Το 50 συγκρίνεται με το 70, μετά το 50 και το 70 ανταλλάσσονται. Το 50 συγκρίνεται με το 60, μετά το 50 και το 60 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Τρεις συγκρίσεις είναι τρεις πράξεις. Τρεις ανταλλαγές είναι τρεις λειτουργίες. Αυτή η ενότητα παρέχει επτά λειτουργίες. Υπάρχουν συνολικά δεκαέξι επεμβάσεις μέχρι στιγμής (9 + 7 = 16). Το αποτέλεσμα είναι το εξής:

50 60 70 | 80 40 30 20 10

Στον δείκτη τέσσερα, υπάρχει μια κίνηση στο 40. Το 40 συγκρίνεται με το 80, μετά το 40 και το 80 ανταλλάσσονται. Το 40 συγκρίνεται με το 70, μετά το 40 και το 70 ανταλλάσσονται. Το 40 συγκρίνεται με το 60, μετά το 40 και το 60 ανταλλάσσονται. Το 40 συγκρίνεται με το 50, μετά το 40 και το 50 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Τέσσερις συγκρίσεις είναι τέσσερις πράξεις. Τέσσερις ανταλλαγές είναι τέσσερις πράξεις. Αυτή η ενότητα παρέχει εννέα λειτουργίες. Υπάρχουν συνολικά είκοσι πέντε επεμβάσεις μέχρι στιγμής (16 + 9 = 25). Το αποτέλεσμα είναι το εξής:

40 50 60 70 80 | 30 20 10

Στον δείκτη πέντε, υπάρχει μια κίνηση στο 30. Το 30 συγκρίνεται με το 80, μετά το 30 και το 80 ανταλλάσσονται. Το 30 συγκρίνεται με το 70, μετά το 30 και το 70 ανταλλάσσονται. Το 30 συγκρίνεται με το 60, μετά το 30 και το 60 ανταλλάσσονται. Το 30 συγκρίνεται με το 50, μετά το 30 και το 50 ανταλλάσσονται. Το 30 συγκρίνεται με το 40, μετά το 30 και το 40 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Πέντε συγκρίσεις είναι πέντε πράξεις. Πέντε ανταλλαγές είναι πέντε πράξεις. Αυτή η ενότητα παρέχει έντεκα λειτουργίες. Υπάρχουν συνολικά τριάντα έξι επεμβάσεις μέχρι στιγμής (25 + 11 = 36). Το αποτέλεσμα είναι το εξής:

30 40 50 60 70 80 | 20 10

Στον δείκτη έξι, υπάρχει μια κίνηση στο 20. Το 20 συγκρίνεται με το 80, μετά το 20 και το 80 ανταλλάσσονται. Το 20 συγκρίνεται με το 70, μετά το 20 και το 70 ανταλλάσσονται. Το 20 συγκρίνεται με το 60, μετά το 20 και το 60 ανταλλάσσονται. Το 20 συγκρίνεται με το 50, μετά το 20 και το 50 ανταλλάσσονται. Το 20 συγκρίνεται με το 40, μετά το 20 και το 40 ανταλλάσσονται. Το 20 συγκρίνεται με το 30, μετά το 20 και το 30 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Έξι συγκρίσεις είναι έξι πράξεις. Έξι ανταλλαγές είναι έξι πράξεις. Αυτή η ενότητα παρέχει δεκατρείς λειτουργίες. Υπάρχουν συνολικά σαράντα εννέα επεμβάσεις μέχρι στιγμής (36 + 13 = 49). Το αποτέλεσμα είναι το εξής:

20 30 40 50 60 70 80 | 10

Στον δείκτη επτά, υπάρχει μια κίνηση στο 10. Το 10 συγκρίνεται με το 80, μετά το 10 και το 80 ανταλλάσσονται. Το 10 συγκρίνεται με το 70, μετά το 10 και το 70 ανταλλάσσονται. Το 10 συγκρίνεται με το 60, μετά το 10 και το 60 ανταλλάσσονται. Το 10 συγκρίνεται με το 50, μετά το 10 και το 50 ανταλλάσσονται. Το 10 συγκρίνεται με το 30, μετά το 10 και το 40 ανταλλάσσονται. Το 10 συγκρίνεται με το 30, μετά το 10 και το 30 ανταλλάσσονται. Το 10 συγκρίνεται με το 20, μετά το 10 και το 20 ανταλλάσσονται. Μια κίνηση είναι μια λειτουργία. Επτά συγκρίσεις είναι επτά πράξεις. Επτά ανταλλαγές είναι επτά πράξεις. Αυτή η ενότητα παρέχει δεκαπέντε λειτουργίες. Υπάρχουν συνολικά εξήντα τέσσερις επεμβάσεις μέχρι στιγμής (49 + 15 = 64). Το αποτέλεσμα είναι το εξής:

10 20 30 40 50 60 70 80 10 |

Η δουλειά έγινε! Συμμετείχαν 64 επιχειρήσεις.

64 = 8 x 8 = 8 ^δύο

Πολυπλοκότητα χρόνου για ταξινόμηση εισαγωγής

Εάν υπάρχουν n στοιχεία για ταξινόμηση με Ταξινόμηση Εισαγωγής, ο μέγιστος αριθμός πιθανών πράξεων θα είναι n2, όπως αποδείχθηκε προηγουμένως. Η πολυπλοκότητα του χρόνου ταξινόμησης εισαγωγής είναι:

O(n ^δύο )

Αυτό χρησιμοποιεί τη σημείωση Big-O. Ο συμβολισμός Big-O ξεκινά με κεφαλαία O, ακολουθούμενο από παρενθέσεις. Μέσα στις παρενθέσεις υπάρχει η έκφραση για τον μέγιστο δυνατό αριθμό πράξεων.

Κωδικοποίηση σε C

Στην αρχή της σάρωσης, το πρώτο στοιχείο δεν μπορεί να αλλάξει τη θέση του. Το πρόγραμμα είναι ουσιαστικά το εξής:

Ο ορισμός της συνάρτησης insertionSort() χρησιμοποιεί τον αλγόριθμο όπως περιγράφεται. Σημειώστε τις συνθήκες για τον βρόχο while. Μια κατάλληλη κύρια λειτουργία C για αυτό το πρόγραμμα είναι:

συμπέρασμα

Η χρονική πολυπλοκότητα για την Ταξινόμηση Εισαγωγής δίνεται ως εξής:

O(n ^δύο )

Ο αναγνώστης μπορεί να έχει ακούσει για χρονική πολυπλοκότητα χειρότερης περίπτωσης, πολυπλοκότητα χρόνου μέσης περίπτωσης και χρονική πολυπλοκότητα στην καλύτερη περίπτωση. Αυτές οι παραλλαγές της πολυπλοκότητας χρόνου ταξινόμησης εισαγωγής συζητούνται στο επόμενο άρθρο στον ιστότοπό μας.