Ταξινόμηση με φυσαλίδες έναντι Ταξινόμησης Επιλογής
Η ταξινόμηση με φυσαλίδες είναι ένας αλγόριθμος ταξινόμησης που λειτουργεί περνώντας από τη λίστα που πρόκειται να ταξινομηθεί επανειλημμένα ενώ συγκρίνει ζεύγη στοιχείων που είναι γειτονικά. Εάν ένα ζεύγος στοιχείων είναι σε λάθος σειρά, ανταλλάσσονται για να τα τοποθετήσουν στη σωστή σειρά. Αυτή η διέλευση επαναλαμβάνεται μέχρι να μην απαιτηθούν περαιτέρω ανταλλαγές. Η επιλογή ταξινόμησης είναι επίσης ένας αλγόριθμος ταξινόμησης, ο οποίος ξεκινά με την εύρεση του ελάχιστου στοιχείου στη λίστα και την εναλλαγή του με το πρώτο στοιχείο. Αυτή η διαδικασία επαναλαμβάνεται για το υπόλοιπο της λίστας τοποθετώντας τα ανταλλαγμένα στοιχεία στη σειρά.
Τι είναι η ταξινόμηση με φυσαλίδες;
Η ταξινόμηση με φυσαλίδες είναι ένας αλγόριθμος ταξινόμησης που λειτουργεί περνώντας από τη λίστα που πρόκειται να ταξινομηθεί επανειλημμένα ενώ συγκρίνει ζεύγη στοιχείων που είναι γειτονικά. Εάν ένα ζεύγος στοιχείων είναι σε λάθος σειρά, ανταλλάσσονται για να τα τοποθετήσουν στη σωστή σειρά. Αυτή η διέλευση επαναλαμβάνεται μέχρι να μην απαιτηθούν περαιτέρω ανταλλαγές (που σημαίνει ότι η λίστα έχει ταξινομηθεί). Δεδομένου ότι τα μικρότερα στοιχεία στη λίστα έρχονται στην κορυφή καθώς μια φούσκα βγαίνει στην επιφάνεια, της δίνεται το όνομα ταξινόμηση με φυσαλίδες. Η ταξινόμηση με φυσαλίδες είναι ένας πολύ απλός αλγόριθμος ταξινόμησης, αλλά έχει μέση πολυπλοκότητα χρόνου περίπτωσης O(n2) όταν ταξινομεί μια λίστα με n στοιχεία. Λόγω αυτού, η ταξινόμηση με φυσαλίδες δεν είναι κατάλληλη για ταξινόμηση λιστών με μεγάλο αριθμό στοιχείων. Αλλά λόγω της απλότητάς της, η ταξινόμηση με φυσαλίδες διδάσκεται κατά την εισαγωγή στους αλγόριθμους.
Τι είναι η ταξινόμηση επιλογών;
Η ταξινόμηση επιλογής είναι επίσης ένας άλλος αλγόριθμος ταξινόμησης που ξεκινά με την εύρεση του ελάχιστου στοιχείου στη λίστα και την εναλλαγή του με το πρώτο στοιχείο. Στη συνέχεια, το ελάχιστο στοιχείο βρίσκεται από το υπόλοιπο της λίστας (από το δεύτερο στοιχείο μέχρι το τελευταίο στοιχείο στη λίστα) και ανταλλάσσεται με το δεύτερο στοιχείο. Αυτή η διαδικασία επαναλαμβάνεται για το υπόλοιπο της λίστας τοποθετώντας τα ανταλλαγμένα στοιχεία στη σειρά. Έτσι, στην ταξινόμηση επιλογής, σε οποιοδήποτε βήμα του αλγορίθμου, η λίστα χωρίζεται σε δύο μέρη όπου το ένα μέρος περιέχει ταξινομημένα στοιχεία και το άλλο μέρος περιέχει μη ταξινομημένα στοιχεία. Καθώς προχωρά ο αλγόριθμος, η ταξινομημένη λίστα μεγαλώνει από αριστερά προς τα δεξιά. Η ταξινόμηση επιλογής έχει επίσης μια μέση πολυπλοκότητα χρόνου περίπτωσης O(n2). Επομένως, δεν είναι επίσης κατάλληλο για ταξινόμηση μεγάλων λιστών.
Ποια είναι η διαφορά μεταξύ Ταξινόμησης με φυσαλίδες και Ταξινόμησης Επιλογής;
Αν και τόσο ο αλγόριθμος ταξινόμησης με φυσαλίδες όσο και οι αλγόριθμοι ταξινόμησης επιλογής έχουν μέση πολυπλοκότητα χρόνου περίπτωσης O(n2), η ταξινόμηση με φυσαλίδες υπερέχει σχεδόν σε όλες τις περιπτώσεις από την ταξινόμηση επιλογής. Αυτό οφείλεται στον αριθμό των ανταλλαγών που χρειάζονται οι δύο αλγόριθμοι (τα είδη με φυσαλίδες χρειάζονται περισσότερες ανταλλαγές). Αλλά λόγω της απλότητας της ταξινόμησης με φυσαλίδες, το μέγεθος του κώδικα είναι πολύ μικρό. Η σταθερότητα είναι μια άλλη διαφορά σε αυτούς τους δύο αλγόριθμους. Ένας σταθερός αλγόριθμος ταξινόμησης, είναι ένας αλγόριθμος ταξινόμησης που διατηρεί τη σειρά των εγγραφών εάν η λίστα περιέχει στοιχεία με ίση τιμή. Υπό αυτή την έννοια, η ταξινόμηση επιλογής δεν είναι ένας σταθερός αλγόριθμος, ενώ η ταξινόμηση με φυσαλίδες είναι ένας σταθερός αλγόριθμος.
