Μια άλλη σημαντική διαφορά μεταξύ των δύο είναι ότι το bubble sort είναι σταθερός αλγόριθμος, ενώ η επιλογή είναι ένας ασταθής αλγόριθμος. Ένας αλγόριθμος θεωρείται σταθερός τα στοιχεία με το ίδιο κλειδί που εμφανίζονται στην ίδια σειρά με αυτά που προέκυψαν πριν ταξινομηθούν στη λίστα ή στον πίνακα. Γενικά, οι πιο σταθεροί και γρήγοροι αλγόριθμοι χρησιμοποιούν πρόσθετη μνήμη.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Τύπος φούσκα | Επιλογή είδους |
|---|---|---|
| Βασικός | Το παρακείμενο στοιχείο συγκρίνεται και αντικαθίσταται | Το μεγαλύτερο στοιχείο επιλέγεται και αντικαθίσταται με το τελευταίο στοιχείο (σε περίπτωση αύξουσας τάξης). |
| Βέλτιστη πολυπλοκότητα χρόνου | Επί) | Ο (η2) |
| Αποδοτικότητα | Ανεπαρκής | Βελτιωμένη απόδοση σε σύγκριση με το είδος φυσαλίδων |
| Σταθερός | Ναί | Οχι |
| Μέθοδος | Ανταλλαγή | Επιλογή |
| Ταχύτητα | Αργός | Γρήγορη σε σύγκριση με το είδος φυσαλίδων |
Ορισμός ταξινόμησης φούσκας
Η ταξινόμηση των φυσαλίδων είναι ο απλούστερος επαναληπτικός αλγόριθμος που λειτουργεί συγκρίνοντας κάθε στοιχείο ή στοιχείο με το στοιχείο δίπλα του και αντικαθιστώντας τα, αν χρειαστεί. Με απλά λόγια, συγκρίνει το πρώτο και το δεύτερο στοιχείο της λίστας και τις ανταλλάσσει, εκτός εάν δεν βρίσκονται σε συγκεκριμένη σειρά. Παρομοίως, το δεύτερο και το τρίτο στοιχείο συγκρίνονται και ανταλλάσσονται, και αυτή η σύγκριση και η ανταλλαγή συνεχίζονται στο τέλος της λίστας. Ο αριθμός των συγκρίσεων στην πρώτη επανάληψη είναι n-1 όπου n είναι τα αριθμητικά στοιχεία ενός πίνακα. Το μεγαλύτερο στοιχείο θα ήταν στην nη θέση μετά την πρώτη επανάληψη. Και μετά από κάθε επανάληψη, ο αριθμός των συγκρίσεων μειώνεται και στην τελευταία επανάληψη λαμβάνει χώρα μόνο μία σύγκριση.
Αυτός ο αλγόριθμος είναι ο πιο αργός αλγόριθμος ταξινόμησης. Η πολυπλοκότητα της καλύτερης περίπτωσης (όταν η λίστα είναι κανονική) της κατηγορίας Bubble είναι της τάξης n ( O (n) ), και η πολυπλοκότητα της χειρότερης περίπτωσης είναι O (n2) . Στην καλύτερη περίπτωση, είναι της τάξης n επειδή συγκρίνει μόνο τα στοιχεία και δεν τα ανταλλάσσει. Αυτή η τεχνική απαιτεί επιπλέον χώρο για την αποθήκευση της προσωρινής μεταβλητής.
Ορισμός της ταξινόμησης επιλογής
Το είδος επιλογής έχει επιτύχει ελαφρώς καλύτερη απόδοση και είναι αποτελεσματικό από τον αλγόριθμο ταξινόμησης φυσαλίδων. Ας υποθέσουμε ότι θέλουμε να κανονίσουμε έναν πίνακα σε αύξουσα σειρά, τότε λειτουργεί με την εύρεση του μεγαλύτερου στοιχείου και την ανταλλαγή του με το τελευταίο στοιχείο και επαναλαμβάνουμε την ακόλουθη διαδικασία στις υπο-συστοιχίες μέχρι να ταξινομηθεί ολόκληρη η λίστα.
Βασικές διαφορές μεταξύ ταξινόμησης φυσαλίδων και ταξινόμησης επιλογής
- Στο είδος των φυσαλίδων, κάθε στοιχείο και το παρακείμενο του στοιχείο συγκρίνονται και αντικαθίστανται εάν απαιτείται. Από την άλλη πλευρά, η επιλογή επιλογής λειτουργεί επιλέγοντας το στοιχείο και αντικαθιστώντας το συγκεκριμένο στοιχείο με το τελευταίο στοιχείο. Το επιλεγμένο στοιχείο θα μπορούσε να είναι μεγαλύτερο ή μικρότερο, ανάλογα με τη σειρά, δηλαδή την άνοδο ή την κατεύθυνση.
- Η πολυπλοκότητα της χειρότερης περίπτωσης είναι ίδια και στους δύο αλγορίθμους, δηλαδή στο O (n2), αλλά η καλύτερη πολυπλοκότητα είναι διαφορετική. Η ταξινόμηση των φυσαλίδων παίρνει μια σειρά n, ενώ το είδος επιλογής καταναλώνει μια σειρά n2 χρόνου.
- Το είδος φυσαλίδων είναι ένας σταθερός αλγόριθμος, αντίθετα, το είδος επιλογής είναι ασταθές.
- Ο αλγόριθμος επιλογής επιλογής είναι γρήγορος και αποτελεσματικός σε σύγκριση με τον τύπο φυσαλίδων, ο οποίος είναι πολύ αργός και αναποτελεσματικός.
συμπέρασμα
Ο αλγόριθμος ταξινόμησης φυσαλίδων θεωρείται ο πιο απλός και αναποτελεσματικός αλγόριθμος, αλλά ο αλγόριθμος επιλογής επιλογής είναι αποτελεσματικός σε σύγκριση με το είδος φυσαλίδων. Το είδος φυσαλίδων καταναλώνει επιπλέον χώρο για την αποθήκευση της προσωρινής μεταβλητής και χρειάζεται περισσότερες ανταλλαγές.
