[Παίζει μουσική] DOUG LLOYD: Εντάξει, έτσι bubble sort είναι ένας αλγόριθμος που μπορείτε να χρησιμοποιήσετε για να ταξινομήσετε ένα σύνολο στοιχείων. Ας ρίξουμε μια ματιά στο πώς λειτουργεί. Έτσι, η βασική ιδέα πίσω bubble sort είναι αυτό. Εμείς γενικά θέλουν να κινηθεί υψηλότερα αποτιμώνται τα στοιχεία γενικά προς τα δεξιά, και χαμηλής εκτίμησης γενικά στοιχεία προς τα αριστερά, όπως θα περιμέναμε. Θέλουμε τα κάτω τα πράγματα να είναι σε η αρχή, και τα υψηλότερα πράγματα να είναι στο τέλος. Πώς μπορούμε να το κάνουμε αυτό; Λοιπόν στον κώδικα ψευδοκώδικα, θα μπορούσαμε να πούμε, ας ορίσετε έναν μετρητή swap για μια μη μηδενική τιμή. Θα δούμε γιατί το κάνουμε αυτό σε μια δεύτερη. Και τότε θα επαναλάβω το εξής διαδικασία έως ότου ο μετρητής swap είναι 0, ή έως ότου δεν κάνουμε ανταλλαγές σε όλα. Μηδενίστε το μετρητή του swap σε 0 αν δεν είναι ήδη 0. Στη συνέχεια, εξετάζει κάθε γειτονικό ζεύγος των στοιχείων. Αν αυτά τα δύο στοιχεία όχι με σκοπό, να ανταλλάξουν, και προσθέστε 1 στον πάγκο swap. Εάν σκέφτεστε για την αυτό, πριν να το φανταστείτε, παρατηρήσετε ότι αυτό θα κινηθεί χαμηλότερα αποτιμώνται στοιχεία προς τα αριστερά και υψηλότερες αποτιμώνται στοιχεία προς τα δεξιά, αποτελεσματικά κάνει ό, τι θέλουμε να κάνουμε, η οποία είναι να μετακινήσετε αυτές τις ομάδες των στοιχείων με τον τρόπο αυτό. Ας απεικονίσει το πώς αυτό μπορεί να μοιάζει με τη χρήση συστοιχίας μας ότι χρησιμοποιείται για τη δοκιμή από αυτούς τους αλγορίθμους. Έχουμε μια σειρά αδιαχώριστα και πάλι εδώ, υποδεικνύεται από όλα τα στοιχεία είναι σε κόκκινο. Και εγώ που σε αντίθεση ανταλλαγής μου σε μια μη μηδενική τιμή. Έχω επέλεξε αυθαίρετα αρνητικό 1-- δεν είναι 0. Θέλουμε να επαναλάβετε αυτή τη διαδικασία έως ότου ο μετρητής ανταλλαγής είναι 0. Αυτός είναι ο λόγος που έθεσα ανταλλαγής μου σε αντίθεση με κάποια μη μηδενική τιμή, διότι διαφορετικά η μετρητής ανταλλαγής θα είναι 0. Εμείς δεν θα είναι καν αρχίσει η διαδικασία του αλγορίθμου. Έτσι και πάλι, τα βήματα are-- μηδενίσετε το μετρητή ανταλλαγής 0, στη συνέχεια να εξετάσουμε σε κάθε παρακείμενο ζευγάρι, και αν είναι εκτός λειτουργίας, ανταλλαγής τους, και προσθέστε 1 στον πάγκο swap. Οπότε ας ξεκινήσουμε αυτή τη διαδικασία. Έτσι, το πρώτο πράγμα που κάνουμε είναι θέσαμε το μετρητή του swap σε 0, και στη συνέχεια θα αρχίσει να ψάχνει σε κάθε γειτονικό ζεύγος. Γι 'αυτό πρώτα να αρχίσει να ψάχνει σε 5 και 2. Βλέπουμε ότι είναι έξω από παραγγείλετε και έτσι μπορούμε να τα ανταλλάξουν. Και προσθέτουμε 1 στο μετρητή swap. Έτσι τώρα πάγκο ανταλλαγής μας είναι 1, και 2 και 5 έχουν αλλάξει. Τώρα επαναλάβετε τη διαδικασία. Κοιτάμε το επόμενο γειτονικό ζεύγος, 5 και 1-- είναι επίσης εκτός λειτουργίας, έτσι μπορούμε να τα ανταλλάξουν και να προσθέσετε 1 στον πάγκο swap. Στη συνέχεια, εξετάζουμε 5 και 3. Είναι εκτός λειτουργίας, έτσι ώστε να ανταλλάξετε τους και προσθέτουμε 1 στο μετρητή swap. Στη συνέχεια, εξετάζουμε 5 και 6. Είναι σε σειρά, έτσι δεν το κάνουμε πραγματικότητα Πρέπει να ανταλλάξουν τίποτα αυτή τη φορά. Στη συνέχεια, εξετάζουμε 6 και 4. Είναι, επίσης, εκτός λειτουργίας, έτσι ώστε να ανταλλάξετε τους και προσθέτουμε 1 στο μετρητή swap. Τώρα παρατηρήσετε τι συνέβη. Έχουμε μετακινηθεί 6 σε όλη τη διαδρομή μέχρι το τέλος. Έτσι, στην ταξινόμηση με επιλογή, αν έχετε φαίνεται ότι το βίντεο, αυτό που κάναμε ήταν καταλήξαμε κινείται η μικρότερα στοιχεία για την οικοδόμηση η ταξινομημένο πίνακα ουσιαστικά από αριστερά προς τα δεξιά, το μικρότερο στο μεγαλύτερο. Στην περίπτωση του bubble sort, αν είμαστε μετά από αυτό το συγκεκριμένο αλγόριθμο, είμαστε πραγματικά πρόκειται να είναι η αξιοποίηση η ταξινομημένο πίνακα από δεξιά προς τα αριστερά, μεγαλύτερο προς το μικρότερο. Έχουμε αποτελεσματικά διοχετεύεται 6, το Η μεγαλύτερη αξία, σε όλη τη διαδρομή μέχρι το τέλος. Και έτσι τώρα μπορούμε να δηλώνουμε ότι είναι ταξινομημένο, και στο μέλλον iterations-- που διέρχεται από τη συστοιχία again-- δεν έχουμε να εξετάσουμε 6 πια. Δεν έχουμε παρά να εξετάσουμε τα αδιαχώριστα στοιχεία όταν ψάχνουμε σε γειτονικά ζεύγη. Έτσι έχουμε τελειώσει ένα περνούν μέσα από bubble sort. Έτσι, τώρα πάμε πίσω στο θέμα, επαναλάβετε μέχρι ο μετρητής ανταλλαγής είναι 0. Λοιπόν ο μετρητής ανταλλαγής είναι 4, οπότε θα πάμε να το επαναλαμβάνουμε και πάλι αυτή τη διαδικασία. Εμείς πάμε για να μηδενίσετε το μετρητή ανταλλαγής 0, και να εξετάσουμε σε κάθε γειτονικό ζεύγος. Ξεκινάμε λοιπόν με 2 και 1-- ότι είναι εκτός λειτουργίας, έτσι μπορούμε να τα ανταλλάξουν και προσθέτουμε 1 στο μετρητή swap. 2 και 3, είναι σε τάξη. Δεν χρειάζεται να κάνετε τίποτα. 3 και 5 είναι σε τάξη. Δεν χρειάζεται να κάνετε τίποτα εκεί. 5 και 4, που είναι έξω της τάξης, και γι 'αυτό Πρέπει να τους ανταλλάξουν και να προσθέσετε 1 στον πάγκο swap. Και τώρα έχουμε μετακινηθεί 5, Το επόμενο μεγαλύτερο στοιχείο, στο τέλος του τμήματος αδιαχώριστα. Έτσι μπορούμε να αποκαλούμε σήμερα ότι μέρος του τμήματος ταξινομημένο. Τώρα κοιτάτε το οθόνη και να πείτε ίσως, όπως μπορώ, ότι η διάταξη ταξινομούνται τώρα. Αλλά δεν μπορούμε να αποδείξουμε ότι ακόμα. Δεν έχουμε εγγύηση ότι είναι ταξινομημένο. Αλλά αυτό είναι όπου η ανταλλαγή μετρητή πρόκειται να μπαίνουν στο παιχνίδι. Έτσι, έχουμε ολοκληρώσει ένα πέρασμα. Ο μετρητής swap είναι 2. Έτσι θα πάμε να επαναλάβουμε αυτή η διαδικασία και πάλι, επαναλάβετε μέχρι ο μετρητής ανταλλαγής είναι 0. Μηδενίστε το μετρητή του swap σε 0. Γι 'αυτό και θα το επαναφέρετε. Τώρα κοιτάξτε κάθε γειτονικό ζεύγος. Αυτό είναι σε σειρά, 1 και 2. 2 και 3 είναι σε τάξη. 3 και 4 είναι σε τάξη. Έτσι, σε αυτό το σημείο, να παρατηρήσετε έχουμε ολοκληρώσει κοιτάζοντας κάθε γειτονικό ζεύγος, αλλά ο μετρητής ανταλλαγής είναι ακόμα 0. Αν δεν έχουμε να στραφούν οποιαδήποτε στοιχεία, τότε Πρέπει να είναι εντάξει, με Δυνάμει αυτής της διαδικασίας. Και έτσι η αποτελεσματικότητα του είδους, ότι οι επιστήμονες που αγαπούν τον υπολογιστή, είναι τώρα μπορούμε να δηλώνουμε η όλη διάταξη πρέπει να να ταξινομηθούν, γιατί δεν το κάναμε Πρέπει να ανταλλάξουν κάποια στοιχεία. Αυτό είναι πολύ ωραίο. Έτσι ποια είναι η χειρότερη περίπτωση σενάριο με bubble sort; Στη χειρότερη περίπτωση, η συστοιχία είναι σε εντελώς αντίστροφη σειρά, και έτσι πρέπει να φούσκα κάθε των μεγάλων στοιχείων όλων τον τρόπο σε όλη την σειρά. Και πράγματι πρέπει επίσης να φούσκα όλα τα μικρά στοιχεία πίσω σε όλη τη διαδρομή κατά μήκος της διάταξης, πάρα πολύ. Έτσι, κάθε ένα από τα n στοιχεία πρέπει να κινηθεί σε όλες τις άλλες n στοιχεία. Έτσι, αυτό είναι το χειρότερο σενάριο. Στην καλύτερη περίπτωση σενάριο όμως, αυτό είναι ελαφρώς διαφορετικό από το είδος επιλογής. Η σειρά είναι ήδη ταξινομούνται όταν πάμε στο. Δεν έχουμε να κάνει οποιαδήποτε swaps για το πρώτο πέρασμα. Έτσι, θα μπορούσαμε να πρέπει να κοιτάξουμε σε λιγότερα στοιχεία, σωστά; Δεν έχουμε να επαναλάβουμε επεξεργάζονται αρκετές φορές πάνω. Λοιπόν, τι σημαίνει αυτό; Έτσι ποια είναι η χειρότερη περίπτωση για bubble sort, και τι είναι το καλύτερο σενάριο για bubble sort; Μήπως να μαντέψετε αυτό; Στη χειρότερη περίπτωση, θα πρέπει να επαναλάβει σε όλα τα στοιχεία n n φορές. Έτσι, η χειρότερη περίπτωση είναι n τετράγωνο. Εάν η συστοιχία είναι τέλεια ταξινομημένων όμως, το μόνο που Πρέπει να εξετάσουμε κάθε των στοιχείων φορά. Και αν ο μετρητής swap είναι ακόμα 0, μπορείτε να πείτε αυτός ο πίνακας είναι ταξινομημένο. Και έτσι στην καλύτερη περίπτωση, αυτό είναι στην πραγματικότητα καλύτερα από ό, τι η επιλογή sort-- είναι ωμέγα του ν. Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.