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