[Powered by Google Translate] [Ταξινόμηση Insertion] [Tommy MacWilliam] [Πανεπιστήμιο του Χάρβαρντ] [Αυτό είναι CS50.TV] Ας ρίξουμε μια ματιά στο είδος εισαγωγής, ένας αλγόριθμος για τη λήψη μια λίστα με τους αριθμούς και τη διαλογή τους. Ένας αλγόριθμος, να θυμάστε, είναι απλά ένα βήμα-προς-βήμα διαδικασία για την ολοκλήρωση μιας εργασίας. Η βασική ιδέα πίσω από ταξινόμηση με εισαγωγή, είναι να διαιρέσει λίστα μας σε δύο τμήματα, ένα ταξινομημένο τμήμα και ένα τμήμα αδιαχώριστα. 

Σε κάθε βήμα του αλγορίθμου, ένας αριθμός κινείται αδιαχώριστων από το τμήμα προς το τμήμα ταξινόμηση έως ότου τελικά ολόκληρη η λίστα είναι ταξινομημένη. Αυτή είναι η λίστα των έξι αδιαχώριστα αριθμών - 23, 42, 4, 16, 8, και 15. Δεδομένου ότι οι αριθμοί αυτοί δεν είναι όλοι σε αύξουσα σειρά, από όπου και αν έχουν υποστεί διαλογή. Από τη στιγμή που δεν έχουν ξεκινήσει ακόμη τη διαλογή, θα εξετάσουμε και τα έξι στοιχεία αδιαχώριστα τμήμα μας. 

Μόλις αρχίζουμε τη διαλογή, θα βάλουμε αυτούς τους αριθμούς ταξινόμηση προς τα αριστερά από αυτά. Λοιπόν, ας ξεκινήσουμε με το 23, το πρώτο στοιχείο στη λίστα μας. Δεν έχουμε κανένα στοιχείο σε ταξινομημένο τμήμα μας ακόμη, οπότε ας θεωρούν απλά 23 να είναι η αρχή και το τέλος της ταξινομημένο τμήμα μας. Τώρα, ταξινομημένο τμήμα μας έχει έναν αριθμό, 23, και αδιαχώριστα τμήμα μας έχει αυτά τα πέντε αριθμούς. Ας προστεθεί τώρα τον επόμενο αριθμό μαζί με τα υπόλοιπα τμήμα μας, 42, μέσα στο ταξινομημένο τμήμα. 

Για να γίνει αυτό, θα πρέπει να συγκρίνετε το 42 έως το 23 - το μόνο στοιχείο ταξινομημένο τμήμα μας μέχρι τώρα. Σαράντα δύο είναι μεγαλύτερο από 23, έτσι ώστε να μπορούμε απλά να προσθέσει 42 έως το τέλος του τμήματος ταξινόμηση της λίστας. Μεγάλη! Τώρα ταξινομημένο τμήμα μας έχει δύο στοιχεία, και αδιαχώριστα τμήμα μας έχει τέσσερα στοιχεία. Λοιπόν, ας προχωρήσουμε τώρα στο 4, το επόμενο στοιχείο της αδιαχώριστα τμήμα. Έτσι, όπου θα πρέπει αυτό να τοποθετείται στο ταξινομημένο τμήμα; 

Θυμηθείτε, θέλουμε να τοποθετήσετε τον αριθμό αυτό σε ταξινομημένη σειρά έτσι ταξινομημένο τμήμα μας παραμένει σωστά ταξινομημένο ανά πάσα στιγμή. Αν τοποθετήσετε τα 4 στα δεξιά του 42, τότε λίστα μας θα είναι εκτός λειτουργίας. Έτσι, ας συνεχίσει να κινείται από δεξιά προς τα αριστερά σε τμήμα του είδους μας. Καθώς προχωράμε, ας στραφούν κάθε αριθμό κάτω από ένα μέρος για να κάνει χώρο για το νέο αριθμό. Εντάξει, 4 είναι επίσης μικρότερη από 23, έτσι δεν μπορούμε να το τοποθετήσετε είτε εδώ. Ας προχωρήσουμε το 23 σωστό μέρος. 

Αυτό σημαίνει ότι θα θέλαμε να τοποθετήσετε τα 4 στην πρώτη υποδοχή στο ταξινομημένο τμήμα. Παρατηρήστε πως ο χώρος αυτός στον κατάλογο ήταν ήδη άδειο, επειδή έχουμε ήδη κινείται ταξινομημένο κάτω στοιχεία, όπως τους έχουμε συναντήσει. Εντάξει. Έτσι, είμαστε στα μισά του δρόμου εκεί. Ας συνεχίσουμε τον αλγόριθμο μας εισάγοντας το 16 στο ταξινομημένο τμήμα. Δεκαέξι είναι μικρότερη από 42, οπότε ας μετατόπιση των 42 προς τα δεξιά. Δεκαέξι είναι επίσης μικρότερη από 23, οπότε ας αλλάξει επίσης το στοιχείο αυτό. 

Τώρα, 16 είναι μεγαλύτερο από 4. Έτσι, μοιάζει θα θέλαμε να εισάγετε το 16 μεταξύ του 4 και του 23. Ενώ κινούνται διαμέσου του τμήματος με ταξινόμηση του καταλόγου από δεξιά προς αριστερά, 4 είναι ο πρώτος αριθμός που έχουμε δει που είναι μικρότερος από τον αριθμό προσπαθούμε να εισάγετε. Έτσι, τώρα μπορούμε να εισάγουμε το 16 σε αυτή την κενή θέση, η οποία, θυμάστε, έχουμε δημιουργήσει με κινούμενα στοιχεία στο τμήμα είδος πάνω όπως έχουμε τους συναντήσει. 

Εντάξει. Τώρα, έχουμε τέσσερις ταξινομημένο στοιχεία και δύο αδιαχώριστα στοιχεία. Έτσι, ας προχωρήσουμε τα 8 στο ταξινομημένο τμήμα. Οκτώ είναι μικρότερη από 42. Οκτώ είναι μικρότερο από 23. Και 8 είναι μικρότερη από 16. Αλλά 8 είναι μεγαλύτερο από 4. Έτσι, θα θέλαμε να εισάγετε τα 8 μεταξύ του 4 και του 16. Και τώρα έχουμε μόνο ένα ακόμη στοιχείο για να ταξινομήσετε αριστερά - το 15. Δεκαπέντε είναι μικρότερη από 42, Δεκαπέντε είναι μικρότερο από 23. Και 15 είναι μικρότερο από 16. Αλλά 15 είναι μεγαλύτερη από 8. 

Έτσι, εδώ είναι που θέλουμε να κάνουν την τελική εισαγωγή μας. Και τελειώσαμε. Εμείς δεν έχουμε περισσότερα στοιχεία στο τμήμα αδιαχώριστα, και ταξινομημένο τμήμα μας είναι στη σωστή σειρά. Οι αριθμοί διέταξε από το μικρότερο στο μεγαλύτερο. Έτσι, ας ρίξουμε μια ματιά σε μερικά ψευδοκώδικα που περιγράφει τα βήματα που μόλις πραγματοποιήθηκε. 

On line 1, μπορούμε να δούμε ότι θα χρειαστεί να επαναλάβει πάνω από κάθε στοιχείο στη λίστα εκτός από το πρώτο, δεδομένου ότι το πρώτο στοιχείο στο τμήμα αδιαχώριστων θα γίνει απλά το πρώτο στοιχείο στην ταξινόμηση τμήμα. Στις γραμμές 2 και 3, είμαστε παρακολουθώντας σημερινή μας θέση στο τμήμα αδιαχώριστα. Στοιχείο αντιπροσωπεύει τον αριθμό αυτή τη στιγμή κινείται στο ταξινομημένο τμήμα, και j αντιπροσωπεύει δείκτη μας στο τμήμα αδιαχώριστα. 

Στις γραμμή 4, είμαστε επανάληψη μέσω της ταξινομημένο τμήμα από τα δεξιά προς τα αριστερά. Θέλουμε να σταματήσουμε την επανάληψη αφού το στοιχείο προς τα αριστερά της τρέχουσας θέσης μας είναι μικρότερο από το στοιχείο προσπαθούμε να εισάγετε. Στη γραμμή 5, είμαστε μετατόπιση κάθε στοιχείο που συναντάμε ένα χώρο προς τα δεξιά. Με αυτόν τον τρόπο, θα έχουμε μια σαφή χώρο για να τοποθετήσετε μέσα όταν βρίσκουμε το πρώτο στοιχείο λιγότερο από ό, τι το στοιχείο κινούμαστε. On line 6, είμαστε ενημέρωση μετρητή μας να συνεχίσει να κινείται αριστερά από το ταξινομημένο τμήμα. Τέλος, επί της γραμμής 7, είμαστε εισαγωγή του στοιχείου εντός του τμήματος ταξινόμηση της λίστας. 

Γνωρίζουμε ότι είναι εντάξει για να εισάγετε στο j θέση, επειδή έχουμε ήδη μετακινηθεί το στοιχείο που χρησιμοποιείται για να υπάρχει ένα διάστημα προς τα δεξιά. Θυμηθείτε, είμαστε κινείται μέσα από την ταξινομημένο τμήμα από τα δεξιά προς τα αριστερά, αλλά είμαστε διακινούνται μέσω του τμήματος αδιαχώριστα από τα αριστερά προς τα δεξιά. Εντάξει. Ας ρίξουμε τώρα μια ματιά στο πώς λειτουργεί καιρό ότι ο αλγόριθμος πήρε. Θα ρωτήσω πρώτα το ερώτημα πόσο καιρό παίρνει για αυτό τον αλγόριθμο για να τρέξει στη χειρότερη περίπτωση. Υπενθυμίζουμε ότι εμείς εκπροσωπούμε αυτό το χρόνο λειτουργίας με μεγάλο συμβολισμό O. Για να ταξινομήσετε τη λίστα μας, είχαμε να επαναλάβει τα στοιχεία πάνω στα μικτά τμήμα, και για καθένα από τα στοιχεία αυτά, ενδεχομένως πάνω από όλα τα στοιχεία στο ταξινομημένο τμήμα. Διαισθητικά, αυτό ακούγεται σαν ένα O (n ^ 2) λειτουργία. 

Κοιτάζοντας ψευδοκώδικα μας, έχουμε ένα βρόχο ένθετα μέσα σε ένα άλλο βρόχο, η οποία, μάλιστα, ακούγεται σαν ένα O (n ^ 2) λειτουργία. Ωστόσο, η ταξινόμηση τμήμα του καταλόγου δεν περιέχουν ολόκληρη τη λίστα μέχρι το τέλος. Ακόμα, θα μπορούσαμε ενδεχομένως να προστεθεί ένα νέο στοιχείο στην αρχή του τμήματος ταξινόμηση σε κάθε επανάληψη του αλγορίθμου, πράγμα που σημαίνει ότι εμείς θα πρέπει να εξετάσουμε κάθε στοιχείο σήμερα στο ταξινομημένο τμήμα. Έτσι, αυτό σημαίνει ότι θα μπορούσε να κάνει ενδεχομένως μια σύγκριση για το δεύτερο στοιχείο, δύο συγκρίσεις για το τρίτο στοιχείο, και ούτω καθεξής. Έτσι, ο συνολικός αριθμός των βημάτων είναι το άθροισμα των ακεραίων από 1 έως το μήκος του καταλόγου μείον 1. Μπορούμε να αντιπροσωπεύει αυτό με μια άθροιση. 

Δεν θα υπεισέλθω σε αθροίσματα εδώ, αλλά αποδεικνύεται ότι αυτό το άθροισμα είναι ίσο με n (n - 1) πάνω από 2, το οποίο είναι ισοδύναμο ν ^ 2/2 - n / 2. Όταν μιλάμε για ασυμπτωτική runtime, αυτή n ^ 2 όρο αυτό πρόκειται να κυριαρχήσει αυτό το ν όρο. Έτσι, είναι είδος εισαγωγής Big O (n ^ 2). Τι θα συμβεί αν τρέξαμε είδος εισαγωγής σε ήδη ταξινομημένη λίστα. Σε αυτή την περίπτωση, θα είχαμε απλώς δημιουργήσει το ταξινομημένο τμήμα από τα αριστερά προς τα δεξιά. Έτσι, θα πρέπει μόνο της τάξης του n βήματα. 

Αυτό σημαίνει ότι το είδος εισαγωγής έχει καλύτερη απόδοση περίπτωση του n, την οποία εμείς εκπροσωπούμε με Ω (n). Και αυτό είναι το είδος για την εισαγωγή, μόνο ένας από τους πολλούς αλγόριθμους που μπορούμε να χρησιμοποιήσουμε για να ταξινομήσετε μια λίστα. Το όνομά μου είναι ο Tommy, και αυτό είναι CS50. [CS50.TV] Ω, απλά δεν μπορεί να σταματήσει ότι μόλις ξεκινά. Ω, κάναμε ότι - Boom! >>