[Παίζει μουσική] DOUG LLOYD: Επιλογή του είδους είναι μια αλγόριθμο που, όπως μπορείτε να φανταστείτε, ταξινομεί ένα σύνολο στοιχείων. Και αλγόριθμος ανάκληση είναι ένα βήμα-προς-βήμα σύνολο οδηγιών για την ολοκλήρωση μιας εργασίας. 

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

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

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

Αυτή τη στιγμή, και πάλι, το σύνολο συστοιχία είναι αδιαχώριστα το μέρος. Όλα τα κόκκινα στοιχεία δεν έχουν υποστεί διαλογή. Έτσι ψάχνουμε μέσα και βρίσκουμε τη μικρότερη τιμή. Θα ξεκινήσουμε από την αρχή, πάμε στο τέλος, βρίσκουμε η μικρότερη τιμή είναι ένα. Έτσι, αυτό είναι το πρώτο μέρος. Και στη συνέχεια μέρος δύο, swap agreement που έχει αξία με Το πρώτο στοιχείο της αδιαχώριστα μέρος, ή η πρώτη κόκκινη στοιχείο. 

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

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

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

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

Ψάχνουμε μέσα και πάλι, και εμείς βρείτε το μικρότερο στοιχείο είναι τέσσερις. Εμείς το swap με το πρώτο στοιχείο της αδιαχώριστα μέρος, και τώρα τέσσερις είναι ταξινομημένο. 

Θεωρούμε ότι είναι πέντε το μικρότερο στοιχείο. Εμείς το swap με την πρώτη στοιχείο του αδιαχώριστα μέρος. Και τώρα πέντε είναι ταξινομημένο. 

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

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

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

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

Έτσι σκέφτεται πίσω στο μας υπολογιστική πολυπλοκότητα εργαλειοθήκη, τι νομίζετε ότι είναι η χειρότερη περίπτωση εκτέλεσης για ταξινόμηση με επιλογή; Ποια νομίζετε ότι είναι η καλύτερη περίπτωση εκτέλεσης για ταξινόμηση με επιλογή; 

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

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