Οι προγραμματιστές που αλλάζουν από την ανάπτυξη υπολογιστών και ιστού στην κωδικοποίηση για κινητές συσκευές ή ενσωματωμένα συστήματα διαπιστώνουν ότι αφιερώνεται περισσότερος χρόνος στην επιλογή και την κωδικοποίηση των δικών τους δομών δεδομένων και αλγορίθμων. Με λιγότερη μνήμη και περιορισμένη αποθήκευση δεδομένων, δεν υπάρχει χώρος για προκατασκευασμένες βιβλιοθήκες ή πλαίσια. Έτσι, για όσους πρέπει να γράψουν τις δικές τους ρουτίνες ταξινόμησης, ακολουθούν ορισμένες σκέψεις σχετικά με την επιλογή της χαμηλής ταξινόμησης με φούσκα.
Ιστορικό
Η ταξινόμηση με φυσαλίδες είναι ένας απλός αλγόριθμος που ταξινομεί μια λίστα στοιχείων στη μνήμη. Με δεδομένο έναν πίνακα, ο κώδικας συγκρίνει επανειλημμένα κάθε ζεύγος γειτονικών στοιχείων και τα ανταλλάσσει εάν δεν είναι σε τάξη. Η διαδικασία επαναλαμβάνεται μέχρι να μην πραγματοποιηθούν άλλες ανταλλαγές. Εάν ήταν δυνατή η προβολή του πίνακα ενώ η ταξινόμηση είναι σε εξέλιξη, οι χαμηλές τιμές θα "μπουκάρονταν" στην κορυφή ενώ οι μεγάλες τιμές θα βυθίζονταν στο κάτω μέρος. Εδώ είναι ο σχετικός κώδικας στη Visual Basic 2010:
Το βίντεο της ημέρας
Ενώ swap = True swap = False Για i = 0 έως tbl.length - 2 Αν tbl (i) > tbl (i + 1) Τότε tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End while
Πότε να επιλέξετε την ταξινόμηση με φυσαλίδες
Αυτός ο αλγόριθμος έχει πολλά πλεονεκτήματα. Είναι απλό στη γραφή, κατανοητό και χρειάζεται μόνο μερικές γραμμές κώδικα. Τα δεδομένα ταξινομούνται στη θέση τους, ώστε να υπάρχει μικρή επιβάρυνση μνήμης και, μόλις ταξινομηθούν, τα δεδομένα είναι στη μνήμη, έτοιμα για επεξεργασία. Το σημαντικότερο μειονέκτημα είναι ο χρόνος που χρειάζεται για την ταξινόμηση. Ο μέσος χρόνος αυξάνεται σχεδόν εκθετικά καθώς αυξάνεται ο αριθμός των στοιχείων του πίνακα. Το δεκαπλάσιο του αριθμού των αντικειμένων χρειάζεται σχεδόν εκατό φορές περισσότερο για να ταξινομηθεί.
Άλλες ταξινομήσεις πίνακα
Οι αλγόριθμοι ταξινόμησης ποικίλλουν ως προς την πολυπλοκότητα, την ταχύτητα και την επιβάρυνση. Το είδος φούσκας είναι το λιγότερο περίπλοκο αλλά και ένα από τα πιο αργά. Άλλες ταξινομήσεις που βασίζονται σε πίνακα, όπως η ταξινόμηση εισαγωγής και η ταξινόμηση ανταλλαγής είναι λίγο πιο γρήγορες, αλλά λαμβάνουν περισσότερο κώδικα (δείτε τις παραπομπές παρακάτω). Το κύριο πλεονέκτημα των ταξινομήσεων που βασίζονται σε πίνακες είναι ότι χρησιμοποιούν τον λιγότερο κώδικα και καταλαμβάνουν τη μικρότερη ποσότητα μνήμης εργασίας. Εξετάστε αυτά τα είδη για απλούς πίνακες με λιγότερα από μερικές εκατοντάδες στοιχεία.
Σύνθετοι αλγόριθμοι ταξινόμησης
Τα μεγαλύτερα σύνολα δεδομένων απαιτούν πιο περίπλοκο κώδικα και περισσότερη μνήμη. Η γρήγορη ταξινόμηση και η ταξινόμηση σωρών διαχωρίζουν και αντιγράφουν τα σύνολα δεδομένων για βελτιστοποίηση του αριθμού των συγκρίσεων. Η γρήγορη ταξινόμηση διαιρεί συνεχώς τη λίστα και, στη συνέχεια, τη συναρμολογεί ξανά με ταξινόμηση. Η ταξινόμηση σωρού αντιγράφει τα δεδομένα σε μια δομή δέντρου και στη συνέχεια διασχίζει το δέντρο για να αντιγράψει τα δεδομένα ξανά στη σειρά. Και οι δύο είναι γρήγορες και αποτελεσματικές, αλλά χρειάζονται περισσότερο κώδικα και πολύ περισσότερο λειτουργικό χώρο αποθήκευσης. Επιλέξτε αυτούς τους αλγόριθμους για μεγάλα σύνολα δεδομένων.
