Τι είναι το Bubble Sort;
Το Bubble Sort είναι ένας αλγόριθμος ταξινόμησης που χρησιμοποιείται για την ταξινόμηση στοιχείων λίστας με αύξουσα σειρά, συγκρίνοντας δύο παρακείμενες τιμές. Εάν η πρώτη τιμή είναι υψηλότερη από τη δεύτερη τιμή, η πρώτη τιμή παίρνει τη δεύτερη θέση τιμής, ενώ η δεύτερη τιμή παίρνει τη θέση της πρώτης τιμής. Εάν η πρώτη τιμή είναι χαμηλότερη από τη δεύτερη τιμή, τότε δεν γίνεται ανταλλαγή.
Αυτή η διαδικασία επαναλαμβάνεται έως ότου συγκριθούν όλες οι τιμές σε μια λίστα και αντικατασταθούν εάν είναι απαραίτητο. Κάθε επανάληψη ονομάζεται συνήθως πάσο. Ο αριθμός των περάσεων σε ένα είδος φυσαλίδας είναι ίσος με τον αριθμό των στοιχείων σε μια λίστα μείον ένα.
Σε αυτό το σεμινάριο Bubble Sorting in Python θα μάθετε:
- Τι είναι το Bubble Sort;
- Εφαρμογή του αλγόριθμου Bubble Sort
- Βελτιστοποιημένος αλγόριθμος ταξινόμησης φυσαλίδων
- Οπτική αναπαράσταση
- Παραδείγματα Python
- Επεξήγηση κώδικα
- Πλεονεκτήματα ταξινόμησης φυσαλίδων
- Μειονεκτήματα τύπου φούσκα
- Ανάλυση πολυπλοκότητας του Bubble Sort
Εφαρμογή του αλγόριθμου Bubble Sort
Θα χωρίσουμε την εφαρμογή σε τρία (3) βήματα, δηλαδή το πρόβλημα, τη λύση και τον αλγόριθμο που μπορούμε να χρησιμοποιήσουμε για να γράψουμε κώδικα για οποιαδήποτε γλώσσα.
Το πρόβλημα
Μια λίστα αντικειμένων δίνεται σε τυχαία σειρά και θα θέλαμε να τακτοποιήσουμε τα αντικείμενα με κανονικό τρόπο
Εξετάστε την ακόλουθη λίστα:
[21,6,9,33,3]
Η λύση
Επανάληψη μέσω της λίστας συγκρίνοντας δύο παρακείμενα στοιχεία και εναλλαγή τους εάν η πρώτη τιμή είναι υψηλότερη από τη δεύτερη τιμή.
Το αποτέλεσμα πρέπει να έχει ως εξής:
[3,6,9,21,33]
Αλγόριθμος
Ο αλγόριθμος ταξινόμησης φυσαλίδων λειτουργεί ως εξής
Βήμα 1) Λάβετε τον συνολικό αριθμό στοιχείων. Λάβετε τον συνολικό αριθμό στοιχείων στη δεδομένη λίστα
Βήμα 2) Προσδιορίστε τον αριθμό των εξωτερικών περάσεων (n - 1) που πρέπει να γίνουν. Το μήκος του είναι λίστα μείον ένα
Βήμα 3) Εκτελέστε εσωτερικά περάσματα (n - 1) φορές για το εξωτερικό πέρασμα 1. Αποκτήστε την πρώτη τιμή του στοιχείου και συγκρίνετε τη με τη δεύτερη τιμή. Εάν η δεύτερη τιμή είναι μικρότερη από την πρώτη τιμή, αλλάξτε τις θέσεις
Βήμα 4) Επαναλάβετε το βήμα 3 έως ότου φτάσετε στο εξωτερικό πέρασμα (n - 1). Αποκτήστε το επόμενο στοιχείο στη λίστα και επαναλάβετε τη διαδικασία που πραγματοποιήθηκε στο βήμα 3 έως ότου όλες οι τιμές έχουν τοποθετηθεί στη σωστή αύξουσα σειρά τους.
Βήμα 5) Επιστρέψτε το αποτέλεσμα όταν έχουν γίνει όλα τα περάσματα. Επιστρέψτε τα αποτελέσματα της ταξινομημένης λίστας
Βήμα 6) Βελτιστοποίηση αλγορίθμου
Αποφύγετε τα περιττά εσωτερικά περάσματα εάν η λίστα ή οι παρακείμενες τιμές έχουν ήδη ταξινομηθεί. Για παράδειγμα, εάν η παρεχόμενη λίστα περιέχει ήδη στοιχεία που έχουν ταξινομηθεί σε αύξουσα σειρά, τότε μπορούμε να σπάσουμε το βρόχο νωρίς.
Βελτιστοποιημένος αλγόριθμος ταξινόμησης φυσαλίδων
Από προεπιλογή, ο αλγόριθμος για ταξινόμηση φυσαλίδων στο Python συγκρίνει όλα τα στοιχεία της λίστας ανεξάρτητα από το αν η λίστα έχει ήδη ταξινομηθεί ή όχι. Εάν η συγκεκριμένη λίστα έχει ήδη ταξινομηθεί, η σύγκριση όλων των τιμών είναι χάσιμο χρόνου και πόρων.
Η βελτιστοποίηση του τύπου φυσαλίδων μας βοηθά να αποφύγουμε περιττές επαναλήψεις και να εξοικονομούμε χρόνο και πόρους.
Για παράδειγμα, εάν το πρώτο και το δεύτερο στοιχείο έχουν ήδη ταξινομηθεί, τότε δεν χρειάζεται να επαναλάβετε τις υπόλοιπες τιμές. Η επανάληψη τερματίζεται και η επόμενη ξεκινά έως ότου ολοκληρωθεί η διαδικασία όπως φαίνεται στο παρακάτω παράδειγμα Bubble Sort.
Η βελτιστοποίηση γίνεται με τα ακόλουθα βήματα
Βήμα 1) Δημιουργήστε μια μεταβλητή σημαίας που παρακολουθεί εάν έχει συμβεί ανταλλαγή στον εσωτερικό βρόχο
Βήμα 2) Εάν οι τιμές έχουν αλλάξει θέσεις, συνεχίστε στην επόμενη επανάληψη
Βήμα 3) Εάν τα οφέλη δεν έχουν αλλάξει θέσεις, τερματίστε τον εσωτερικό βρόχο και συνεχίστε με τον εξωτερικό βρόχο.
Ένα βελτιστοποιημένο είδος φυσαλίδων είναι πιο αποτελεσματικό καθώς εκτελεί μόνο τα απαραίτητα βήματα και παραλείπει αυτά που δεν απαιτούνται.
Οπτική αναπαράσταση
Λαμβάνοντας υπόψη μια λίστα με πέντε στοιχεία, οι παρακάτω εικόνες απεικονίζουν τον τρόπο με τον οποίο η ταξινόμηση φυσαλίδων επαναλαμβάνεται μέσω των τιμών κατά την ταξινόμησή τους
Η ακόλουθη εικόνα εμφανίζει τη μη ταξινομημένη λίστα
Πρώτη επανάληψη
Βήμα 1)
Οι τιμές 21 και 6 συγκρίνονται για να ελέγξετε ποιο είναι μεγαλύτερο από το άλλο.
Το 21 είναι μεγαλύτερο από το 6, έτσι το 21 παίρνει τη θέση που καταλαμβάνεται από το 6, ενώ το 6 παίρνει τη θέση που καταλαμβάνεται από το 21
Η τροποποιημένη λίστα μας μοιάζει τώρα με την παραπάνω.
Βήμα 2)
Συγκρίνονται οι τιμές 21 και 9.
Το 21 είναι μεγαλύτερο από το 9, οπότε ανταλλάσσουμε τις θέσεις των 21 και 9
Η νέα λίστα είναι τώρα όπως παραπάνω
Βήμα 3)
Οι τιμές 21 και 33 συγκρίνονται για να βρεθούν οι μεγαλύτερες.
Η τιμή 33 είναι μεγαλύτερη από 21, οπότε δεν γίνεται ανταλλαγή.
Βήμα 4)
Οι τιμές 33 και 3 συγκρίνονται για να βρεθούν οι μεγαλύτερες.
Η τιμή 33 είναι μεγαλύτερη από 3, οπότε ανταλλάσσουμε τις θέσεις τους.
Η ταξινομημένη λίστα στο τέλος της πρώτης επανάληψης είναι όπως η παραπάνω
Δεύτερη επανάληψη
Η νέα λίστα μετά τη δεύτερη επανάληψη έχει ως εξής
Τρίτη επανάληψη
Η νέα λίστα μετά την τρίτη επανάληψη έχει ως εξής
Τέταρτη επανάληψη
Η νέα λίστα μετά την τέταρτη επανάληψη έχει ως εξής
Παραδείγματα Python
Ο παρακάτω κώδικας δείχνει πώς να εφαρμόσετε τον αλγόριθμο Bubble Sort στο Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Η εκτέλεση του παραπάνω προγράμματος ταξινόμησης φυσαλίδων στην Python παράγει τα ακόλουθα αποτελέσματα
[6, 9, 21, 3, 33]
Επεξήγηση κώδικα
Η εξήγηση για τον κώδικα προγράμματος Python Bubble Sort έχει ως εξής
ΕΔΩ,
- Ορίζει μια συνάρτηση bubbleSort που δέχεται μια παράμετρο theSeq. Ο κωδικός δεν εξάγει τίποτα.
- Παίρνει το μήκος του πίνακα και εκχωρεί την τιμή σε μια μεταβλητή n. Ο κωδικός δεν εξάγει τίποτα
- Ξεκινά a για βρόχο που εκτελεί τον αλγόριθμο ταξινόμησης φυσαλίδων (n - 1) φορές Αυτός είναι ο εξωτερικός βρόχος. Ο κωδικός δεν εξάγει τίποτα
- Ορίζει μια μεταβλητή σημαίας που θα χρησιμοποιηθεί για να προσδιορίσει εάν έχει γίνει ανταλλαγή ή όχι. Αυτό είναι για σκοπούς βελτιστοποίησης. Ο κωδικός δεν εξάγει τίποτα
- Ξεκινά τον εσωτερικό βρόχο που συγκρίνει όλες τις τιμές στη λίστα από την πρώτη έως την τελευταία. Ο κωδικός δεν εξάγει τίποτα.
- Χρησιμοποιεί τη δήλωση if για να ελέγξει εάν η τιμή στην αριστερή πλευρά είναι μεγαλύτερη από την τιμή στην άμεση δεξιά πλευρά. Ο κωδικός δεν παράγει τίποτα.
- Εκχωρεί την τιμή τουSeq [j] σε μια χρονική μεταβλητή tmp εάν η συνθήκη αξιολογείται ως αληθής Ο κωδικός δεν εξάγει τίποτα
- Η τιμή τουSeq [j + 1] αντιστοιχεί στη θέση τουSeq [j]. Ο κωδικός δεν εξάγει τίποτα
- Η τιμή της μεταβλητής tmp αντιστοιχεί στη θέση theSeq [j + 1]. Ο κωδικός δεν εξάγει τίποτα
- Η μεταβλητή flag έχει την τιμή 1 για να υποδείξει ότι έχει γίνει ανταλλαγή. Ο κωδικός δεν εξάγει τίποτα
- Χρησιμοποιεί μια δήλωση if για να ελέγξει εάν η τιμή της μεταβλητής σημαίας είναι 0. Ο κώδικας δεν εξάγει τίποτα
- Εάν η τιμή είναι 0, τότε καλούμε τη δήλωση διακοπής που βγαίνει από τον εσωτερικό βρόχο.
- Επιστρέφει την τιμή τουSeq μετά την ταξινόμησή του. Ο κωδικός εξάγει την ταξινομημένη λίστα.
- Ορίζει μια μεταβλητή el που περιέχει μια λίστα τυχαίων αριθμών. Ο κωδικός δεν εξάγει τίποτα.
- Εκχωρεί την τιμή της συνάρτησης bubble Ταξινόμηση σε μεταβλητό αποτέλεσμα.
- Εκτυπώνει την τιμή του μεταβλητού αποτελέσματος.
Πλεονεκτήματα ταξινόμησης φυσαλίδων
Τα παρακάτω είναι μερικά από τα πλεονεκτήματα του αλγορίθμου ταξινόμησης φυσαλίδων
- Είναι εύκολο να γίνει κατανοητό
- Λειτουργεί πολύ καλά όταν η λίστα είναι ήδη ή σχεδόν ταξινομημένη
- Δεν απαιτεί εκτεταμένη μνήμη.
- Είναι εύκολο να γράψετε τον κωδικό για τον αλγόριθμο
- Οι απαιτήσεις χώρου είναι ελάχιστες σε σύγκριση με άλλους αλγόριθμους ταξινόμησης.
Μειονεκτήματα τύπου φούσκα
Τα παρακάτω είναι μερικά από τα μειονεκτήματα του αλγορίθμου ταξινόμησης φυσαλίδων
- Δεν λειτουργεί καλά κατά την ταξινόμηση μεγάλων λιστών. Παίρνει πάρα πολύ χρόνο και πόρους.
- Χρησιμοποιείται κυρίως για ακαδημαϊκούς σκοπούς και όχι για την πραγματική εφαρμογή.
- Ο αριθμός των βημάτων που απαιτούνται για την ταξινόμηση της λίστας είναι της τάξης n 2
Ανάλυση πολυπλοκότητας του Bubble Sort
Υπάρχουν τρεις τύποι πολυπλοκότητας είναι:
1) Ταξινόμηση πολυπλοκότητας
Η πολυπλοκότητα ταξινόμησης χρησιμοποιείται για την έκφραση του χρόνου εκτέλεσης και του χώρου που απαιτείται για την ταξινόμηση της λίστας. Η ταξινόμηση φυσαλίδων κάνει (n - 1) επαναλήψεις για ταξινόμηση της λίστας όπου n είναι ο συνολικός αριθμός στοιχείων στη λίστα.
2) Χρόνος πολυπλοκότητας
Η χρονική πολυπλοκότητα του είδους φυσαλίδων είναι O (n 2 )
Οι χρονικές πολυπλοκότητες μπορούν να κατηγοριοποιηθούν ως:
- Χειρότερη περίπτωση - εδώ είναι η λίστα που παρέχεται με φθίνουσα σειρά. Ο αλγόριθμος εκτελεί τον μέγιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-O] O (n 2 )
- Βέλτιστη περίπτωση - αυτό συμβαίνει όταν η παρεχόμενη λίστα έχει ήδη ταξινομηθεί. Ο αλγόριθμος εκτελεί τον ελάχιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-Omega] Ω (n)
- Μέση περίπτωση - αυτό συμβαίνει όταν η λίστα είναι τυχαία. Η μέση πολυπλοκότητα αντιπροσωπεύεται ως [Big-theta] ⊝ (n 2 )
3) Διαστημική πολυπλοκότητα
Η πολυπλοκότητα του διαστήματος μετρά την ποσότητα επιπλέον χώρου που απαιτείται για την ταξινόμηση της λίστας. Η ταξινόμηση φυσαλίδων απαιτεί μόνο έναν (1) επιπλέον χώρο για τη χρονική μεταβλητή που χρησιμοποιείται για την ανταλλαγή τιμών. Επομένως, έχει διαστημική πολυπλοκότητα του O (1).
Περίληψη
- Ο αλγόριθμος ταξινόμησης φυσαλίδων λειτουργεί συγκρίνοντας δύο παρακείμενες τιμές και αλλάζοντάς τις εάν η τιμή στα αριστερά είναι μικρότερη από την τιμή στα δεξιά.
- Η εφαρμογή ενός αλγορίθμου τύπου φούσκας είναι σχετικά ευθεία προς τα εμπρός με την Python. Το μόνο που πρέπει να χρησιμοποιήσετε είναι για βρόχους και εάν δηλώσεις.
- Το πρόβλημα που επιλύει ο αλγόριθμος ταξινόμησης φυσαλίδων είναι η λήψη μιας τυχαίας λίστας στοιχείων και η μετατροπή της σε λίστα με σειρά.
- Ο αλγόριθμος ταξινόμησης φυσαλίδων στη δομή δεδομένων έχει την καλύτερη απόδοση όταν η λίστα έχει ήδη ταξινομηθεί καθώς εκτελεί έναν ελάχιστο αριθμό επαναλήψεων.
- Ο αλγόριθμος ταξινόμησης φυσαλίδων δεν λειτουργεί καλά όταν η λίστα είναι σε αντίστροφη σειρά.
- Το είδος φυσαλίδων έχει μια χρονική πολυπλοκότητα του O (n 2 ) και μια διαστημική πολυπλοκότητα του O (1)
- Ο αλγόριθμος ταξινόμησης φυσαλίδων ταιριάζει καλύτερα για ακαδημαϊκούς σκοπούς και όχι για πραγματικές εφαρμογές.
- Η βελτιστοποιημένη ταξινόμηση φυσαλίδων καθιστά τον αλγόριθμο πιο αποτελεσματικό παραλείποντας περιττές επαναλήψεις κατά τον έλεγχο τιμών που έχουν ήδη ταξινομηθεί.