Αλγόριθμοι ταξινόμησης — Bubble, Merge και Quick Sort σε σύγκριση

Ένας αλγόριθμος ταξινόμησης αναδιατάσσει τα ίδια στοιχεία σε σειρά, όπως από το μικρότερο στο μεγαλύτερο. Αν θέλεις πρώτα τη σύντομη απάντηση, το bubble sort είναι απλό αλλά συνήθως πολύ αργό για μεγάλες λίστες, το merge sort δίνει αξιόπιστη απόδοση $O(n \log n)$, και το quick sort είναι συχνά γρήγορο στην πράξη όταν οι διαμερίσεις του παραμένουν αρκετά ισορροπημένες.

Η σωστή ερώτηση δεν είναι «ποια ταξινόμηση είναι η καλύτερη;» αλλά «καλύτερη υπό ποιες συνθήκες;». Το bubble sort διδάσκει τις τοπικές ανταλλαγές, το merge sort δείχνει καθαρά τη μέθοδο διαίρει και βασίλευε, και το quick sort δείχνει γιατί η μέση απόδοση μπορεί να είναι πολύ καλή ακόμη και χωρίς εγγύηση για τη χειρότερη περίπτωση.

Τι κάνουν οι αλγόριθμοι ταξινόμησης

Δοσμένης μιας λίστας όπως η $[5, 1, 4, 2]$, ο αλγόριθμος πρέπει να επιστρέψει τις ίδιες τιμές σε σειρά:

$$[1, 2, 4, 5]$$

Αυτό ακούγεται απλό, αλλά διαφορετικοί αλγόριθμοι φτάνουν σε αυτό το αποτέλεσμα με πολύ διαφορετικούς τρόπους. Οι βασικές διαφορές είναι:

• πώς μετακινούν τα στοιχεία
• πόσες συγκρίσεις ή ανταλλαγές τείνουν να χρησιμοποιούν
• πόση επιπλέον μνήμη χρειάζονται
• πόσο ευαίσθητοι είναι σε δυσμενή μοτίβα εισόδου

Bubble Sort: Επαναλαμβανόμενες ανταλλαγές γειτονικών στοιχείων

Το bubble sort διατρέχει τη λίστα και ανταλλάσσει γειτονικά στοιχεία που είναι εκτός σειράς. Μετά από ένα πλήρες πέρασμα, το μεγαλύτερο μη ταξινομημένο στοιχείο έχει «ανέβει» στο τέλος.

Στη λίστα $[5, 1, 4, 2]$, το πρώτο πέρασμα μοιάζει ως εξής:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Έπειτα επαναλαμβάνεται στο υπόλοιπο μη ταξινομημένο τμήμα μέχρι να μη χρειάζονται άλλες ανταλλαγές.

Το bubble sort είναι κυρίως χρήσιμο για μάθηση. Γενικά, έχει χρονική πολυπλοκότητα $O(n^2)$, οπότε ο αριθμός των συγκρίσεων αυξάνεται γρήγορα όσο μεγαλώνει η λίστα. Για μικρά παραδείγματα στην τάξη αυτό είναι εντάξει. Για σοβαρή εργασία ταξινόμησης, συνήθως δεν είναι η σωστή επιλογή.

Merge Sort: Διαίρεση, ταξινόμηση και μετά συγχώνευση

Το merge sort χρησιμοποιεί την ιδέα του διαίρει και βασίλευε. Χωρίζει τη λίστα σε μικρότερα μέρη, ταξινομεί αυτά τα μέρη και μετά συγχωνεύει ξανά τα ταξινομημένα κομμάτια.

Για τη λίστα $[5, 1, 4, 2]$, μια καθαρή εικόνα είναι:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Ταξινόμησε κάθε μισό:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Έπειτα συγχώνευσε τα δύο ταξινομημένα μισά:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Το βασικό πλεονέκτημα του merge sort είναι η προβλεψιμότητα. Ο χρόνος εκτέλεσής του είναι $O(n \log n)$ στη συνήθη ανάλυση, όχι μόνο κατά μέσο όρο. Το βασικό κόστος είναι η μνήμη: οι συνηθισμένες υλοποιήσεις με πίνακες χρησιμοποιούν επιπλέον χώρο κατά τη συγχώνευση.

Quick Sort: Διαμέριση γύρω από ένα pivot

Το quick sort χρησιμοποιεί επίσης τη μέθοδο διαίρει και βασίλευε, αλλά με διαφορετικό τρόπο. Επιλέγει ένα pivot, τοποθετεί τα μικρότερα στοιχεία στη μία πλευρά και τα μεγαλύτερα στην άλλη, και μετά ταξινομεί αναδρομικά τις δύο πλευρές.

Χρησιμοποιώντας pivot το $4$ στη λίστα $[5, 1, 4, 2]$, μία πιθανή διαμέριση είναι:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Τώρα το αριστερό και το δεξί μέρος είναι πολύ μικρότερα, οπότε η ταξινόμηση ολοκληρώνεται γρήγορα.

Το quick sort είναι συχνά γρήγορο στην πράξη, επειδή πολλές υλοποιήσεις κάνουν τη διαμέριση επιτόπου και μειώνουν γρήγορα το πρόβλημα όταν το pivot χωρίζει τη λίστα αρκετά καλά. Όμως αυτή η συνθήκη έχει σημασία. Αν οι επιλογές του pivot είναι επανειλημμένα κακές, όπως όταν παράγουν ξανά και ξανά μία πολύ μικρή πλευρά και μία σχεδόν πλήρη πλευρά, τότε η χειρότερη περίπτωση γίνεται $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Αλγόριθμος	Βασική ιδέα	Τυπικός χρόνος	Χρόνος στη χειρότερη περίπτωση	Επιπλέον μνήμη
Bubble sort	Επαναλαμβανόμενες ανταλλαγές γειτονικών στοιχείων	$O(n^2)$	$O(n^2)$	Μικρή
Merge sort	Διαίρεση, ταξινόμηση των μισών, συγχώνευση	$O(n \log n)$	$O(n \log n)$	Μεγαλύτερη στις συνηθισμένες υλοποιήσεις με πίνακες
Quick sort	Διαμέριση γύρω από ένα pivot	Συχνά $O(n \log n)$	$O(n^2)$	Συχνά μικρότερη από του merge sort

Αν θέλεις ένα πρακτικό συμπέρασμα, είναι το εξής: το bubble sort είναι αλγόριθμος διδασκαλίας, το merge sort είναι η σταθερή και προβλέψιμη επιλογή, και το quick sort είναι συχνά η πρακτική επιλογή για ταχύτητα όταν η υλοποίηση χειρίζεται καλά τα pivot.

Ένα ολοκληρωμένο παράδειγμα στην ίδια λίστα

Χρησιμοποίησε την ίδια λίστα:

$$[5, 1, 4, 2]$$

Το bubble sort συνεχίζει να διορθώνει τοπικά λάθη. Δεν «βλέπει» όλη τη δομή, οπότε μπορεί να χρειαστεί πολλά περάσματα.

Το merge sort πρώτα σπάει το πρόβλημα σε μικρότερα ταξινομημένα κομμάτια και μετά τα συνδυάζει. Αυτή η δομή είναι ο λόγος που η απόδοσή του παραμένει αξιόπιστη όσο μεγαλώνει η λίστα.

Το quick sort προσπαθεί να κάνει νωρίς μία ισχυρή διαίρεση. Αν η διαίρεση είναι αρκετά ισορροπημένη, το υπόλοιπο έργο μικραίνει γρήγορα.

Γι’ αυτό οι μαθητές συχνά θυμούνται καλύτερα τους αριθμούς πολυπλοκότητας αφού δουν μία λίστα να περνά από κάθε μέθοδο. Οι αριθμοί δεν είναι αυθαίρετες ετικέτες. Αντανακλούν το πώς ο αλγόριθμος μειώνει την αταξία.

Συνηθισμένα λάθη όταν συγκρίνουμε αλγορίθμους ταξινόμησης

Υποθέτοντας ότι το Quick Sort είναι πάντα ταχύτερο

Το quick sort είναι συχνά γρήγορο στην πράξη, όχι εγγυημένα το ταχύτερο σε κάθε περίπτωση. Η κακή συμπεριφορά του pivot μπορεί να το βλάψει σοβαρά.

Αντιμετωπίζοντας τους αλγορίθμους $O(n \log n)$ ως ίδιους

Το merge sort και το quick sort μπορεί να έχουν τον ίδιο μέσο ρυθμό αύξησης χωρίς να συμπεριφέρονται με τον ίδιο τρόπο ως προς τη χρήση μνήμης, τις εγγυήσεις για τη χειρότερη περίπτωση ή τις λεπτομέρειες υλοποίησης.

Χρήση του Bubble Sort επειδή είναι εύκολο να κωδικοποιηθεί

Η ευκολία στον κώδικα δεν είναι το ίδιο με την καταλληλότητα. Για πολύ μικρές επιδείξεις το bubble sort είναι εντάξει. Για μεγαλύτερες πραγματικές εισόδους, συνήθως κάνει περιττή δουλειά.

Ξεχνώντας το μοντέλο εισόδου

Αυτές οι συγκρίσεις συνήθως υποθέτουν ταξινόμηση βασισμένη σε συγκρίσεις για γενικές εισόδους. Αν τα δεδομένα έχουν ειδική δομή, αλγόριθμοι ταξινόμησης χωρίς συγκρίσεις, όπως το counting sort, μπορεί να αλλάξουν εντελώς την απόφαση.

Πότε χρησιμοποιείται κάθε αλγόριθμος ταξινόμησης

Το bubble sort χρησιμοποιείται κυρίως για διδασκαλία, ιχνηλάτηση και πολύ μικρά παραδείγματα όπου η σαφήνεια έχει μεγαλύτερη σημασία από την απόδοση.

Το merge sort χρησιμοποιείται όταν έχει σημασία η σταθερή συμπεριφορά $O(n \log n)$ και η επιπλέον μνήμη είναι αποδεκτή. Είναι επίσης φυσική επιλογή για συνδεδεμένες λίστες και για περιπτώσεις όπου έχει σημασία η σταθερή ταξινόμηση, ανάλογα με την υλοποίηση.

Το quick sort χρησιμοποιείται όταν η πρακτική ταχύτητα είναι σημαντική και η υλοποίηση έχει καλή στρατηγική επιλογής pivot ή μηχανισμούς προστασίας. Πολλές στρατηγικές ταξινόμησης σε τυπικές βιβλιοθήκες χρησιμοποιούν ιδέες του quick sort μαζί με δικλίδες ασφαλείας, αντί για μια αφελή εκδοχή βιβλίου.

Ένας γρήγορος τρόπος να θυμάσαι τη διαφορά

Θυμήσου τα από την κίνηση:

• το bubble sort διορθώνει γειτονικά στοιχεία
• το merge sort χτίζει ταξινομημένα μισά
• το quick sort χωρίζει γύρω από ένα pivot

Αυτή η νοητική εικόνα είναι πιο χρήσιμη από το να απομνημονεύεις τρία ονόματα και τρεις τύπους.

Δοκίμασε τη δική σου εκδοχή

Πάρε τη λίστα $[7, 3, 6, 1]$ και ιχνηλάτησε ένα πέρασμα του bubble sort, έναν κύκλο διαίρεσης και συγχώνευσης του merge sort και μία διαμέριση pivot για το quick sort. Αν μπορείς να εξηγήσεις γιατί η λίστα αλλάζει διαφορετικά σε κάθε περίπτωση, τότε έχεις καταλάβει την έννοια.