Bubble Αλγόριθμος ταξινόμησης με Python χρησιμοποιώντας Παράδειγμα λίστας
Σάρα Τσεν
Τι είναι ένα Bubble Ταξινόμηση;
Bubble Ταξινόμηση είναι ένας αλγόριθμος ταξινόμησης που χρησιμοποιείται για την ταξινόμηση στοιχείων λίστας σε αύξουσα σειρά συγκρίνοντας δύο γειτονικές τιμές. Εάν η πρώτη τιμή είναι μεγαλύτερη από τη δεύτερη τιμή, η πρώτη τιμή παίρνει τη δεύτερη θέση τιμής, ενώ η δεύτερη τιμή παίρνει τη θέση πρώτης τιμής. Εάν η πρώτη τιμή είναι χαμηλότερη από τη δεύτερη τιμή, τότε δεν γίνεται αλλαγή.
Αυτή η διαδικασία επαναλαμβάνεται έως ότου συγκριθούν όλες οι τιμές σε μια λίστα και αν είναι απαραίτητο. Κάθε επανάληψη συνήθως ονομάζεται πέρασμα. Ο αριθμός των περασμάτων σε μια ταξινόμηση με φυσαλίδες είναι ίσος με τον αριθμό των στοιχείων σε μια λίστα μείον ένα.
Σε αυτή τη Bubble Ταξινόμηση Python φροντιστήριο θα μάθεις:
Εφαρμογή του Bubble Αλγόριθμος ταξινόμησης
Θα αναλύσουμε την υλοποίηση σε τρία (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) Βελτιστοποίηση αλγόριθμου
Αποφύγετε τα περιττά εσωτερικά περάσματα εάν η λίστα ή οι παρακείμενες τιμές είναι ήδη ταξινομημένες. Για παράδειγμα, εάν η παρεχόμενη λίστα περιέχει ήδη στοιχεία που έχουν ταξινομηθεί με αύξουσα σειρά, τότε μπορούμε να σπάσουμε νωρίς τον βρόχο.
βελτιστοποιημένη Bubble Αλγόριθμος ταξινόμησης
Από προεπιλογή, ο αλγόριθμος για την ταξινόμηση με φυσαλίδες Python συγκρίνει όλα τα στοιχεία της λίστας ανεξάρτητα από το αν η λίστα είναι ήδη ταξινομημένη ή όχι. Εάν η δεδομένη λίστα είναι ήδη ταξινομημένη, η σύγκριση όλων των τιμών είναι χάσιμο χρόνου και πόρων.
Η βελτιστοποίηση της ταξινόμησης με φούσκα μας βοηθά να αποφύγουμε περιττές επαναλήψεις και να εξοικονομήσουμε χρόνο και πόρους.
Για παράδειγμα, εάν το πρώτο και το δεύτερο στοιχείο είναι ήδη ταξινομημένα, τότε δεν χρειάζεται να επαναλάβετε τις υπόλοιπες τιμές. Η επανάληψη τερματίζεται και η επόμενη ξεκινά μέχρι να ολοκληρωθεί η διαδικασία όπως φαίνεται παρακάτω Bubble Ταξινόμηση παραδείγματος.
Η βελτιστοποίηση γίνεται χρησιμοποιώντας τα παρακάτω βήματα
Βήμα 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 Αλγόριθμος ταξινόμησης σε Python.
def bubbleSort( theSeq ):
n = len( theSeq )
for i in range( n - 1 ) :
flag = 0
for j in range(n - 1) :
if theSeq[j] > theSeq[j + 1] :
tmp = theSeq[j]
theSeq[j] = theSeq[j + 1]
theSeq[j + 1] = tmp
flag = 1
if flag == 0:
break
return theSeq
el = [21,6,9,33,3]
result = bubbleSort(el)
print (result)
Εκτέλεση του παραπάνω προγράμματος ταξινόμησης με φυσαλίδες Python παράγει τα ακόλουθα αποτελέσματα
[6, 9, 21, 3, 33]
Επεξήγηση κώδικα
Η εξήγηση για το Python Bubble Η ταξινόμηση του κώδικα προγράμματος είναι η εξής
ΕΔΩ,
- Ορίζει μια συνάρτηση bubbleSort που δέχεται μια παράμετρο theSeq. Ο κώδικας δεν βγάζει τίποτα.
- Παίρνει το μήκος του πίνακα και εκχωρεί την τιμή σε μια μεταβλητή n. Ο κώδικας δεν βγάζει τίποτα
- Ξεκινά έναν βρόχο for που εκτελεί τον αλγόριθμο ταξινόμησης με φυσαλίδες (n – 1) φορές. Αυτός είναι ο εξωτερικός βρόχος. Ο κώδικας δεν βγάζει τίποτα
- Καθορίζει μια μεταβλητή σημαίας που θα χρησιμοποιηθεί για να προσδιορίσει εάν έχει πραγματοποιηθεί ή όχι μια ανταλλαγή. Αυτό είναι για λόγους βελτιστοποίησης. Ο κώδικας δεν βγάζει τίποτα
- Ξεκινά τον εσωτερικό βρόχο που συγκρίνει όλες τις τιμές της λίστας από την πρώτη έως την τελευταία. Ο κώδικας δεν βγάζει τίποτα.
- Χρησιμοποιεί τη δήλωση if για να ελέγξει εάν η τιμή στην αριστερή πλευρά είναι μεγαλύτερη από αυτή στην αμέσως δεξιά πλευρά. Ο κώδικας δεν βγάζει τίποτα.
- Εκχωρεί την τιμή του theSeq[j] σε μια χρονική μεταβλητή tmp εάν η συνθήκη αξιολογηθεί ως true. Ο κώδικας δεν βγάζει τίποτα
- Η τιμή του theSeq[j + 1] εκχωρείται στη θέση του theSeq[j]. Ο κώδικας δεν βγάζει τίποτα
- Η τιμή της μεταβλητής tmp εκχωρείται στη θέση theSeq[j + 1]. Ο κώδικας δεν βγάζει τίποτα
- Στη μεταβλητή flag εκχωρείται η τιμή 1 για να υποδείξει ότι έχει πραγματοποιηθεί μια ανταλλαγή. Ο κώδικας δεν βγάζει τίποτα
- Χρησιμοποιεί μια δήλωση if για να ελέγξει αν η τιμή της μεταβλητής σημαίας είναι 0. Ο κώδικας δεν βγάζει τίποτα
- Εάν η τιμή είναι 0, τότε καλούμε την εντολή break που βγαίνει από τον εσωτερικό βρόχο.
- Επιστρέφει την τιμή του theSeq αφού έχει ταξινομηθεί. Ο κώδικας βγάζει την ταξινομημένη λίστα.
- Ορίζει μια μεταβλητή el που περιέχει μια λίστα τυχαίων αριθμών. Ο κώδικας δεν βγάζει τίποτα.
- Εκχωρεί την τιμή της συνάρτησης bubbleSort σε ένα μεταβλητό αποτέλεσμα.
- Εκτυπώνει την τιμή του αποτελέσματος της μεταβλητής.
Bubblπλεονεκτήματα ταξινόμησης
Τα παρακάτω είναι μερικά από τα πλεονεκτήματα του αλγορίθμου ταξινόμησης με φυσαλίδες
- Είναι εύκολο να το καταλάβεις
- Αποδίδει πολύ καλά όταν η λίστα είναι ήδη ή σχεδόν ταξινομημένη
- Δεν απαιτεί εκτεταμένη μνήμη.
- Είναι εύκολο να γράψετε τον κώδικα για τον αλγόριθμο
- Οι απαιτήσεις χώρου είναι ελάχιστες σε σύγκριση με άλλους αλγόριθμους ταξινόμησης.
BubblΕ ταξινόμηση Μειονεκτήματα
Τα παρακάτω είναι μερικά από τα μειονεκτήματα του αλγόριθμου ταξινόμησης με φυσαλίδες
- Δεν έχει καλή απόδοση κατά την ταξινόμηση μεγάλων λιστών. Απαιτεί πάρα πολύ χρόνο και πόρους.
- Χρησιμοποιείται κυρίως για ακαδημαϊκούς σκοπούς και όχι για την εφαρμογή του πραγματικού κόσμου.
- Ο αριθμός των βημάτων που απαιτούνται για την ταξινόμηση της λίστας είναι της σειράς n2
Ανάλυση πολυπλοκότητας του Bubble Ταξινόμηση
Υπάρχουν τρεις τύποι πολυπλοκότητας:
1) Ταξινόμηση πολυπλοκότητας
Η πολυπλοκότητα ταξινόμησης χρησιμοποιείται για να εκφράσει τον αριθμό των χρόνων εκτέλεσης και του χώρου που απαιτείται για την ταξινόμηση της λίστας. Η ταξινόμηση με φούσκα κάνει (n – 1) επαναλήψεις για να ταξινομήσει τη λίστα όπου n είναι ο συνολικός αριθμός στοιχείων στη λίστα.
2) Χρονική πολυπλοκότητα
Η χρονική πολυπλοκότητα της ταξινόμησης με φυσαλίδες είναι O(n2)
Οι χρονικές πολυπλοκότητες μπορούν να κατηγοριοποιηθούν ως εξής:
- Χειρότερη περίπτωση – εδώ η παρεχόμενη λίστα είναι με φθίνουσα σειρά. Ο αλγόριθμος εκτελεί τον μέγιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-O] O(n2)
- καλυτερα case – αυτό συμβαίνει όταν η παρεχόμενη λίστα είναι ήδη ταξινομημένη. Ο αλγόριθμος εκτελεί τον ελάχιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-Omega] Ω(n)
- Μέση περίπτωση – αυτό συμβαίνει όταν η λίστα είναι σε τυχαία σειρά. Η μέση πολυπλοκότητα αντιπροσωπεύεται ως [Big-theta] ⊝(n2)
3) Πολυπλοκότητα χώρου
Η πολυπλοκότητα χώρου μετρά την ποσότητα του επιπλέον χώρου που απαιτείται για την ταξινόμηση της λίστας. Η ταξινόμηση με φυσαλίδες απαιτεί μόνο ένα (1) επιπλέον χώρο για τη χρονική μεταβλητή που χρησιμοποιείται για την εναλλαγή τιμών. Επομένως, έχει χωρική πολυπλοκότητα O (1).
Σύνοψη
- Ο αλγόριθμος ταξινόμησης με φυσαλίδες λειτουργεί συγκρίνοντας δύο γειτονικές τιμές και εναλλάσσοντάς τις εάν η τιμή στα αριστερά είναι μικρότερη από την τιμή στα δεξιά.
- Η εφαρμογή ενός αλγορίθμου ταξινόμησης με φυσαλίδες είναι σχετικά απλή Python. Το μόνο που χρειάζεται να χρησιμοποιήσετε είναι για βρόχους και εντολές if.
- Το πρόβλημα που λύνει ο αλγόριθμος ταξινόμησης με φυσαλίδες είναι η λήψη μιας τυχαίας λίστας στοιχείων και η μετατροπή της σε μια ταξινομημένη λίστα.
- Ο αλγόριθμος ταξινόμησης με φυσαλίδες στη δομή δεδομένων αποδίδει καλύτερα όταν η λίστα είναι ήδη ταξινομημένη καθώς εκτελεί έναν ελάχιστο αριθμό επαναλήψεων.
- Ο αλγόριθμος ταξινόμησης με φυσαλίδες δεν αποδίδει καλά όταν η λίστα είναι με αντίστροφη σειρά.
- Η ταξινόμηση bubbler έχει χρονική πολυπλοκότητα O (n2) και χωρική πολυπλοκότητα O (1)
- Ο αλγόριθμος ταξινόμησης bubbler είναι ο καταλληλότερος για ακαδημαϊκούς σκοπούς και όχι για εφαρμογές πραγματικού κόσμου.
- Η βελτιστοποιημένη ταξινόμηση με φυσαλίδες κάνει τον αλγόριθμο πιο αποτελεσματικό παρακάμπτοντας περιττές επαναλήψεις κατά τον έλεγχο τιμών που έχουν ήδη ταξινομηθεί.
