MARK GROZEN-SMITH: Γεια σου, είμαι ο Mark Grozen-Smith, και αυτό είναι Quicksort. Ακριβώς όπως το είδος εισαγωγής και φούσκα ταξινόμησης, Quicksort είναι ένας αλγόριθμος για διαλογής μιας λίστας ή μία συστοιχία των πραγμάτων. Για λόγους απλότητας, ας υποθέσουμε ότι οι τα πράγματα είναι ακέραιοι αριθμοί, αλλά Γνωρίζουμε ότι Quicksort λειτουργεί για κάτι περισσότερο από αριθμούς. Γρήγορης εκκίνησης είναι λίγο πιο περίπλοκη από την εισαγωγή ή φούσκα, αλλά είναι Επίσης, πολύ πιο αποδοτική στις περισσότερες περιπτώσεις. Περιμένετε ένα δευτερόλεπτο. Μήπως είπε "οι περισσότεροι περιπτώσεις, "όχι" όλα "; Είναι ενδιαφέρον, όχι. Όχι όλες τις περιπτώσεις είναι η ίδια. Μην ανησυχείτε για αυτή τη λεπτομέρεια, αν Δεν έχω δει μεγάλη O συμβολισμός ακόμα, αλλά Quicksort είναι O (n τετράγωνο) αλγόριθμο στη χειρότερη περίπτωση, όπως ακριβώς εισαγωγή ή bubble sort. Ωστόσο, ενεργεί συνήθως πολύ πιο σαν ένα παλιό αναλογικό m αλγόριθμο. Γιατί; Θα επιστρέψουμε σε αυτό αργότερα. Αλλά για τώρα, ας μάθουμε πώς λειτουργεί Quicksort. 

Έτσι, ας δούμε τις Quicksorting αυτό array ακεραίων από το μικρότερο στην μεγαλύτερη. Εδώ έχουμε τους ακέραιους αριθμούς 6, 5, 1, 3, 8, 4, 7, 9, και 2. Πρώτον, έχουμε πάρει το τελευταίο στοιχείο της αυτή η διάταξη - στην προκειμένη περίπτωση, δύο - και καλέστε ότι το «άξονα». Στη συνέχεια, έχουμε αρχίζουν να δούμε δύο πράγματα - ένα, το χαμηλότερο δείκτη, η οποία θα αναφερθώ ως διαμένουν στα δεξιά του το τοίχωμα, και, δύο, η αριστερότερη στοιχείο, το οποίο θα καλέσω το "ρεύμα στοιχείο. «Αυτό που πάμε να κάνουμε είναι φαίνονται όλα τα άλλα στοιχεία, άλλες από τον άξονα, και να θέσει όλα τα στοιχεία μικρότερο από το στροφέα προς την αριστερά του τείχους και όλους εκείνους μεγαλύτερο από το στροφέα προς την δεξιά του τοίχου. Στη συνέχεια, τέλος, θα πέσει το pivot ακριβώς πάνω από το τείχος για να το θέσω μεταξύ όλοι οι αριθμοί μικρότεροι από ό, τι και όλοι οι αριθμοί μεγαλύτερο. 

Οπότε ας το κάνουμε αυτό. Σήκωσε το 2, βάλτε τον τοίχο κατά τη αρχίζει, και καλέστε το 6 το «ρεύμα στοιχείου. "Έτσι θέλουμε να δούμε τρέχον στοιχείο μας, το 6. Και δεδομένου ότι είναι μεγαλύτερο από ό, τι η 2, το αφήνουμε εκεί για να το δεξιά του τοίχου. Στη συνέχεια, θα προχωρήσουμε να εξετάσουμε το 5 όπως μας τρέχον στοιχείο και να δούμε ότι αυτή η είναι, πάλι, μεγαλύτερο από το στροφέα, έτσι αφήστε το όταν είναι σχετικά με το δικαίωμα πλευρά του τοίχου. Προχωράμε. Τρέχον στοιχείο μας είναι τώρα 1, και - ω. Αυτό είναι διαφορετικό τώρα. Το τρέχον στοιχείο είναι σήμερα μικρότερη από ό, τι ο άξονας, έτσι θέλουμε να το θέσω στα αριστερά του τοίχου. Για να το κάνετε αυτό, ας αλλάξουν το τρέχουσα στοιχείου με το χαμηλότερο δείκτη να κάθεται στα δεξιά του τοίχου. Τώρα, προχωράμε στον τοίχο μέχρι ένα δείκτη έτσι ώστε το 1 είναι στα αριστερά πλευρά του τοιχώματος τώρα. 

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

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

Στη συνέχεια, επαναλάβετε αυτή τη διαδικασία για την υποπαρατάξεων αριστερά και δεξιά του στροφέα. Δεδομένου ότι η τελευταία υπο-συστοιχίας είναι μόνο μία στοιχείο καιρό, γνωρίζουμε ότι είναι ήδη ταξινομημένη, γιατί πώς μπορείς να είσαι έξω από διατάξει αν είστε μόνο ένα στοιχείο; Για τη δεξιά πλευρά του υπο-συστοιχίας, εμείς δείτε ότι ο στροφέας είναι 5, και ο τοίχος είναι ακριβώς αριστερά από το 6. Και το τρέχον στοιχείο, επίσης, ξεκινά ως το 6. Έτσι 6 είναι μεγαλύτερο από 5. Το αφήνουμε όπου είναι σχετικά με την δεξιά πλευρά του τοίχου. Τώρα, κινείται, 3 είναι μικρότερη από 5. Γι 'αυτό και το διακόπτη με το πρώτο στοιχείο ακριβώς δεξιά από τον τοίχο. Τώρα, πήγα τον τοίχο μέχρι ένα. Τώρα, κινείται προς την 8. 8 είναι μεγαλύτερο από 5, και γι 'αυτό αφήστε το. Το 4 είναι μικρότερη από 5, έτσι ώστε να το ενεργοποιήσετε. Και. Και. 

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

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

Πώς μπορεί να βελτιωθεί η μέθοδος; Ένας καλός τρόπος για να βελτιωθεί η μέθοδος είναι να μειώσει την πιθανότητα ότι ο χρόνος εκτέλεσης είναι ποτέ πραγματικά o κ τετράγωνο. Θυμηθείτε αυτό το χειρότερο, το χειρότερο σενάριο μπορεί να συμβεί μόνο όταν η pivot επιλεγεί είναι πάντα η υψηλότερη ή χαμηλότερη τιμή στη συστοιχία. Για να εξασφαλιστεί αυτό είναι λιγότερο πιθανό να συμβεί, μπορούμε να βρούμε τον άξονα του επιλέγοντας πολλαπλά στοιχεία και λαμβάνοντας τη μέση τιμή. 

Το όνομά μου είναι Mark Grozen-Smith, και αυτό είναι CS50. 

Για λόγους απλότητας, ας υποθέσουμε ότι οι τα πράγματα είναι ακέραιοι αριθμοί, αλλά Γνωρίζουμε ότι Quicksert - Quicksert; Λυπάμαι. 

Εδώ έχουμε τους ακέραιους 6, 5, 1, 3, 8, 4, 9. 

ΟΜΙΛΗΤΗΣ 1: Αλήθεια; 

ΟΜΙΛΗΤΗΣ 2: Μην σταματάς εκεί. 

ΟΜΙΛΗΤΗΣ 1: Αλήθεια;