[Powered by Google Translate] [SORT BUBBLE] [JACKSON Steinkamp Πανεπιστήμιο Χάρβαρντ] [ΑΥΤΟ ΕΙΝΑΙ CS50. CS50TV] Ταξινόμηση φυσαλίδας είναι ένα παράδειγμα ενός αλγορίθμου διαλογής - δηλαδή, μια διαδικασία για τη διαλογή ενός συνόλου στοιχείων αύξουσα ή φθίνουσα σειρά. Για παράδειγμα, αν θέλετε να ταξινομήσετε μια σειρά που αποτελείται από τους αριθμούς [3, 5, 2, 9], η ορθή εφαρμογή των Ταξινόμηση Bubble θα επιστρέψει το ταξινομημένο πίνακα [2, 3, 5, 9], σε αύξουσα σειρά. Τώρα, είμαι πρόκειται να εξηγήσω πώς σε ψευδοκώδικα ο αλγόριθμος λειτουργεί. Ας πούμε ότι είμαστε διαλογή μια λίστα από 5 ακέραιοι - 3, 2, 9, 6, και 5. Ο αλγόριθμος αρχίζει με μια ματιά τα δύο πρώτα στοιχεία, 3 και 2, και τον έλεγχο αν είναι εκτός σειράς σε σχέση προς το άλλο. Είναι - 3 είναι μεγαλύτερος από 2. Για να είναι σε αύξουσα σειρά, θα πρέπει να είναι ο άλλος τρόπος γύρω. Έτσι, μπορούμε να τους ανταλλάξει. Τώρα ο κατάλογος μοιάζει με αυτό: [2, 3, 9, 6, 5]. Στη συνέχεια, θα εξετάσουμε το δεύτερο και το τρίτο στοιχείο, 3 και 9. Είναι στην σωστή σειρά ως προς το άλλο. Δηλαδή, το 3 είναι μικρότερο από 9, ώστε ο αλγόριθμος δεν τους ανταλλάξει. Στη συνέχεια, θα δούμε στις 9 και 6. Είναι εκτός λειτουργίας. Έτσι, θα πρέπει να τους ανταλλάξουν επειδή 9 είναι μεγαλύτερο από 6. Τέλος, θα εξετάσουμε τα τελευταία δύο ακέραιους αριθμούς, 9 και 5. Είναι εκτός λειτουργίας, οπότε θα πρέπει να ανταλλαχθούν. Μετά την πρώτη πλήρη διόδου μέσω του καταλόγου, μοιάζει με αυτό: [2, 3, 6, 5, 9]. Δεν είναι κακό. Είναι σχεδόν ταξινομημένο. Αλλά θα πρέπει να τρέχει μέσα από τη λίστα και πάλι να το πάρει εντελώς ταξινομημένο. Δύο είναι λιγότερο από 3, οπότε δεν τα ανταλλάξουν. Τρεις είναι λιγότερο από 6, γι 'αυτό δεν τα ανταλλάξουν. Έξι είναι μεγαλύτερο από 5. Έχουμε ανταλλάξει. Έξι είναι λιγότερο από 9. Δεν ανταλλάξουν. Μετά από το δεύτερο πέρασμα μέσω, μοιάζει με αυτό: [2, 3, 5, 6, 9]. Τέλεια. Τώρα, ας γράψω σε ψευδοκώδικα. Βασικά, για κάθε στοιχείο στη λίστα, θα πρέπει να το δει κανείς και το στοιχείο απευθείας προς τα δεξιά της. Αν αυτά είναι εκτός σειράς σε σχέση προς το άλλο - δηλαδή, εάν το στοιχείο στην αριστερή είναι μεγαλύτερη από τη μία στη δεξιά - θα πρέπει να ανταλλάξουν τα δύο στοιχεία. Το κάνουμε αυτό για κάθε στοιχείο της λίστας, και έχουμε κάνει ένα πέρασμα μέσα. Τώρα απλά πρέπει να κάνουμε τα pass-through αρκετές φορές για να εξασφαλιστεί η λίστα πλήρως, σωστά ταξινομημένο. Αλλά πόσες φορές θα πρέπει να περάσει μέσα από τη λίστα για να εγγυηθεί ότι τελειώσαμε; Λοιπόν, το χειρότερο σενάριο είναι αν έχουμε ένα εντελώς προς τα πίσω λίστα. Τότε παίρνει έναν αριθμό περνούν-throughs ίσο με τον αριθμό των στοιχείων ν-1. Αν αυτό δεν έχει νόημα διαισθητικά, σκεφτείτε μια απλή υπόθεση - ο κατάλογος [2, 1]. Αυτό πρόκειται να λάβει ένα pass-through για να ταξινομήσετε σωστά. [3, 2, 1] - Η χειρότερη περίπτωση είναι ότι με 3 στοιχεία ταξινόμηση προς τα πίσω, πρόκειται να πάρει 2 επαναλήψεις σε είδος. Μετά από μία επανάληψη, είναι [2, 1, 3]. Η δεύτερη δίδει την ταξινόμηση array [1, 2, 3]. Έτσι, ξέρετε ότι ποτέ δεν πρέπει να περάσουν από τη σειρά, σε γενικές γραμμές, περισσότερο από n-1 φορές, όπου n είναι ο αριθμός των στοιχείων της συστοιχίας. Λέγεται Ταξινόμηση Bubble, διότι τα μεγαλύτερα στοιχεία τείνουν να «φούσκα-up» προς τα δεξιά αρκετά γρήγορα. Στην πραγματικότητα, αυτός ο αλγόριθμος έχει πολύ ενδιαφέρουσα συμπεριφορά. Μετά από m επαναλήψεις διαμέσου ολόκληρου συστοιχίας, είναι εγγυημένα τα δεξιά στοιχεία m να ταξινομηθούν σε σωστή θέση τους. Αν θέλετε να δείτε αυτό για τον εαυτό σας, μπορούμε να προσπαθήσουμε για μια εντελώς προς τα πίσω λίστα [9, 6, 5, 3, 2]. Μετά από μία διέλευση μέσω της ολόκληρη τη λίστα, [Ήχος της γραφής] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] το δεξιότερο στοιχείο 9 είναι στην κατάλληλη θέση της. Μετά τη δεύτερη pass-through, τα 6 θα έχει «φυσαλίδες προς τα πάνω» για το δεύτερος δεξιά θέση. Τα δύο αυτά στοιχεία σχετικά με το δικαίωμα - 6 και 9 - θα είναι σε σωστές θέσεις τους μετά τα δύο πρώτα pass-throughs. Έτσι, πώς μπορούμε να χρησιμοποιήσουμε αυτό για να βελτιστοποιήσει τον αλγόριθμο; Λοιπόν, μετά από μια επανάληψη διαμέσου της συστοιχίας δεν πρέπει πραγματικά να ελέγξετε το δεξιότερο στοιχείο γιατί ξέρουμε ότι είναι ταξινομημένο. Μετά από δύο επαναλήψεις, γνωρίζουμε με βεβαιότητα τα δεξιά δύο στοιχεία είναι στη θέση τους. Έτσι, σε γενικές γραμμές, μετά από k επαναλήψεις μέσω της πλήρους συστοιχίας, ελέγχοντας τα τελευταία στοιχεία k είναι περιττή αφού γνωρίζουμε ότι είναι στη σωστή θέση ήδη. Έτσι, εάν είστε διαλογή μια σειρά από n στοιχεία, για την πρώτη επανάληψη - εσείς πρέπει να ταξινομηθούν όλα τα στοιχεία - το πρώτο ν-0. Με τη δεύτερη επανάληψη, θα πρέπει να εξετάσουμε όλα τα στοιχεία, αλλά η τελευταία - η πρώτη ν-1. Μια άλλη βελτιστοποίηση θα μπορούσε να είναι να ελέγξετε αν η λίστα έχει ήδη ταξινομημένο μετά από κάθε επανάληψη. Αν είναι ήδη ταξινομημένο, δεν χρειάζεται να προβούν σε οποιαδήποτε περισσότερες επαναλήψεις μέσω του καταλόγου. Πώς μπορούμε να το κάνουμε αυτό; Λοιπόν, αν δεν κάνουμε κανένα swaps για τη μετακύλιση του καταλόγου, Είναι σαφές ότι ο κατάλογος ήταν ήδη ταξινομημένο γιατί δεν αλλάζετε τίποτα. Γι 'αυτό και σίγουρα δεν πρέπει να ταξινομήσετε και πάλι. Ίσως θα μπορούσατε να προετοιμάσει μια μεταβλητή που ονομάζεται σημαία »δεν ταξινομημένο» να false και αλλάξτε την σε πραγματική, αν έχετε να ανταλλάξουν στοιχεία σχετικά με οποιεσδήποτε μία επανάληψη διαμέσου της συστοιχίας. Ή ομοίως, να κάνει ένα μετρητή να μετρήσει πόσες swaps που κάνετε σε οποιαδήποτε δεδομένη επανάληψη. Στο τέλος της μιας επανάληψης, αν δεν ανταλλάξουν οποιοδήποτε από τα στοιχεία, γνωρίζετε ότι η λίστα είναι ήδη ταξινομημένο και είστε έτοιμοι. Ταξινόμηση φούσκα, όπως και οι άλλοι αλγόριθμοι ταξινόμησης, μπορεί να είναι tweaked να εργαστούν για οποιαδήποτε στοιχεία τα οποία έχουν μια μέθοδος παραγγελίας. Δηλαδή, δύο στοιχεία που έχετε έναν τρόπο να πει εάν η πρώτη είναι μεγαλύτερη από, ίση ή μικρότερη από τη δεύτερη. Για παράδειγμα, μπορείτε να ταξινομήσετε τα γράμματα του αλφαβήτου με το ρητό ότι α