[Παίζει μουσική] 

DOUG LLOYD: Έτσι ταξινόμηση με εισαγωγή είναι ένα άλλο αλγόριθμο μπορούμε να χρησιμοποιήσουμε για να ταξινομήσετε μια σειρά. Η ιδέα πίσω από αυτόν τον αλγόριθμο είναι να οικοδομήσουμε ταξινομημένο πίνακα σας στη θέση του, μετατοπίζοντας τα στοιχεία από ο τρόπος as you go, για να κάνει χώρο. Αυτό είναι ελαφρώς διαφορετική από το είδος ή την επιλογή φούσκα είδος, για παράδειγμα, όπου είμαστε προσαρμογή των θέσεις, όπου φτιάχνουμε swaps. 

Σε αυτή την περίπτωση αυτό που είμαστε στην πραγματικότητα κάνει είναι συρόμενα στοιχεία πάνω, έξω από το δρόμο. Πώς αυτόν τον αλγόριθμο εργάζονται σε ψευδοκώδικα; Λοιπόν ας αυθαίρετα λένε ότι η πρώτο στοιχείο του πίνακα είναι ταξινομημένο. Είμαστε το κτίριο στη θέση του. 

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

Στη συνέχεια, θα επαναλάβετε αυτή τη διαδικασία until-- Εμείς θα επαναλάβουμε την ακόλουθη διαδικασία έως ότου όλα τα στοιχεία ταξινομούνται. Κοιτάξτε το επόμενο στοιχείο και αδιαχώριστα τοποθετήστε το στο ταξινομημένο τμήμα, μετατοπίζοντας τον απαιτούμενο αριθμό των στοιχείων έξω από το δρόμο. Ας ελπίσουμε ότι αυτή η οπτικοποίηση θα σας βοηθήσει να δείτε ακριβώς τι είναι συμβαίνει με το είδος εισαγωγής. 

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

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

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

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

Και πάλι, ακόμα, έχουμε μόνο ποτέ κοίταξε ένα, δύο και πέντε. Δεν ξέρω τι άλλο έρχεται, αλλά έχουμε ταξινομούνται τα τρία αυτά στοιχεία. 

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

Έξι είναι η επόμενη αδιαχώριστα στοιχείο στη συστοιχία. Και στην πραγματικότητα έξι είναι μεγαλύτερη από πέντε, έτσι Δεν χρειάζεται καν να κάνει οποιαδήποτε εναλλαγή. Μπορούμε να αναστρέψει μόλις έξι δεξιά για να το άκρο του τμήματος ταξινομημένο. 

Τέλος, τέσσερις είναι η τελευταία αδιαχώριστα στοιχείο. Γι 'αυτό και θα το αναιρέσει, μεταβάλλεται με την πάροδο Τα στοιχεία που θα πρέπει να στραφούν πάνω, και στη συνέχεια θα τοποθετούνται τέσσερα όπου ανήκει. Και τώρα να δείτε, έχουμε το είδος όλων των στοιχείων. Ανακοίνωση με την εισαγωγή είδος, δεν είχαμε για να πάει μπροστά και πίσω σε όλη τη σειρά. Το μόνο που πήγαν σε όλη τη σειρά μία φορά, και θα μετατοπιστεί πράγματα ότι είχαμε ήδη συναντήσει, προκειμένου για να κάνουν χώρο για τα νέα στοιχεία. 

Έτσι ποια είναι η χειρότερη περίπτωση σενάριο με ταξινόμηση με εισαγωγή; Στη χειρότερη περίπτωση, η πίνακας είναι σε αντίστροφη σειρά. Θα πρέπει να στρέψουμε κάθε ένα από τα n στοιχεία των θέσεων του Ν, κάθε φορά που κάνει μια εισαγωγή. Αυτό είναι ένα πολύ μετατόπιση. 

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

Αν φανταστείτε ότι μας σειρά ήταν ένα έως έξι, είχαμε ξεκινήσει από δηλώνοντας ότι ο ένας είναι ταξινομημένο. Δύο έρχεται μετά από μία τόσο μπορούμε μόνο πούμε, εντάξει, καλά ένα και δύο είναι ταξινομημένο. Τρεις έρχεται μετά από δύο έτσι, εντάξει, ένα και δύο και τρία είναι ταξινομημένο. 

Εμείς δεν κάνουμε καμία swaps, είμαστε κινείται μόνο αυτό αυθαίρετη γραμμή μεταξύ διαλογή και χωρίς διαλογή όσο προχωράμε. Το ίδιο αποτελεσματικά όπως κάναμε και στο παράδειγμα, μετατρέποντας στοιχεία μπλε, καθώς προχωράμε. Έτσι ποια είναι η χειρότερη περίπτωση χρόνου εκτέλεσης, τότε; Να θυμάστε, αν θα πρέπει να στρέψουμε το καθένα από τα n στοιχεία ενδεχομένως θέσεις n, ελπίζω ότι σας δίνει η ιδέα ότι η χειρότερη περίπτωση runtime είναι Big O Ν τετράγωνο. 

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

Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.