Και οι δύο τεχνικές διαλογής, η γρήγορη ταξινόμηση και η συγχώνευση είναι βασισμένες στη μέθοδο διαίρεσης και κατακράτησης στην οποία το σύνολο στοιχείων χωρίζεται και στη συνέχεια συνδυάζεται μετά την αναδιάταξη. Η γρήγορη ταξινόμηση απαιτεί συνήθως περισσότερες συγκρίσεις από ό, τι η συγχώνευση ταξινόμησης για την ταξινόμηση ενός μεγάλου συνόλου στοιχείων.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Γρήγορη ταξινόμηση | Συγχώνευση είδος |
|---|---|---|
| Διαχωρισμός των στοιχείων στη συστοιχία | Ο διαχωρισμός ενός καταλόγου στοιχείων δεν χωρίζεται απαραιτήτως στο μισό. | Η συστοιχία διαιρείται πάντοτε στο μισό (n / 2). |
| Η χειρότερη περίπτωση πολυπλοκότητας | Ο (η2) | O (n log n) |
| Λειτουργεί καλά | Μικρότερη διάταξη | Λειτουργεί πρόστιμο σε οποιοδήποτε τύπο πίνακα. |
| Ταχύτητα | Ταχύτερη από άλλους αλγόριθμους ταξινόμησης για μικρό σύνολο δεδομένων. | Συνεπής ταχύτητα σε όλους τους τύπους συνόλων δεδομένων. |
| Πρόσθετη απαίτηση χώρου αποθήκευσης | Πιο λιγο | Περισσότερο |
| Αποδοτικότητα | Δεν είναι αποτελεσματικό για μεγαλύτερες συστοιχίες. | Πιο αποτελεσματικό. |
| Μέθοδος ταξινόμησης | Εσωτερικός | Εξωτερικός |
Ορισμός της Γρήγορης Ταξινόμησης
Η γρήγορη ταξινόμηση χρησιμοποιείται ευρέως αλγόριθμος ταξινόμησης καθώς είναι γρήγορος για τις σύντομες συστοιχίες. Το σύνολο των στοιχείων χωρίζεται σε μέρη κατ 'επανάληψη μέχρις ότου δεν είναι δυνατό να το διαιρέσουμε περαιτέρω. Η γρήγορη ταξινόμηση είναι επίσης γνωστή ως είδος ανταλλαγής διαμερισμάτων . Χρησιμοποιεί ένα στοιχείο-κλειδί (γνωστό ως άξονα) για τη διαίρεση των στοιχείων. Ένα διαμέρισμα περιέχει εκείνα τα στοιχεία που είναι μικρότερα από το στοιχείο-κλειδί. Ένα άλλο διαμέρισμα περιέχει εκείνα τα στοιχεία που είναι μεγαλύτερα από το βασικό στοιχείο. Τα στοιχεία ταξινομούνται αναδρομικά.
Ας υποθέσουμε ότι A είναι ένας πίνακας A [1], A [2], A [3], ...... .., A [n] n αριθμός που πρέπει να ταξινομηθούν. Ο αλγόριθμος γρήγορης ταξινόμησης αποτελείται από τα ακόλουθα βήματα.
- Το πρώτο στοιχείο ή οποιοδήποτε τυχαίο στοιχείο που επιλέγεται ως κλειδί, υποθέτουμε το κλειδί = A (1).
- Ο "χαμηλός" δείκτης τοποθετείται στον δεύτερο και ο "άνω" δείκτης τοποθετείται στο τελευταίο στοιχείο του πίνακα, δηλαδή χαμηλό = 2 και άνω = n.
- Συνεπώς, αυξήστε τον δείκτη "χαμηλής" κατά μία θέση μέχρι το πλήκτρο (A [low]>).
- Συνεχώς, μειώστε τον δείκτη "προς τα πάνω" κατά μία θέση μέχρι το (A [up] <= key).
- Εάν η ανύψωση είναι μεγαλύτερη από τη χαμηλή εναλλαγή A [χαμηλή] με A [επάνω].
- Επαναλάβετε τα βήματα 3, 4 και 5 έως ότου αποτύχει η κατάσταση στο βήμα 5 (δηλ. Πάνω <= χαμηλό) και στη συνέχεια εναλλάξτε A [up] με το κλειδί.
- Εάν τα στοιχεία που απομένουν από το κλειδί είναι μικρότερα από το κλειδί και τα δεξιά στοιχεία του κλειδιού είναι μεγαλύτερα από το κλειδί τότε ο πίνακας χωρίζεται σε δύο υπο-συστοιχίες.
- Η παραπάνω διαδικασία εφαρμόζεται επανειλημμένα στα υποσυστήματα μέχρι να ταξινομηθεί ολόκληρη η συστοιχία.
Πλεονεκτήματα και μειονεκτήματα
Έχει μια καλή μέση περίπτωση συμπεριφορά. Η πολυπλοκότητα του χρόνου εκτέλεσης της γρήγορης ταξινόμησης είναι καλή, δηλαδή είναι ταχύτερη από αλγορίθμους, όπως τύπος φυσαλίδων, είδος τοποθέτησης και είδος επιλογής. Ωστόσο, είναι περίπλοκο και πολύ επαναλαμβανόμενο, γι 'αυτό δεν είναι κατάλληλο για μεγάλες σειρές.
Ορισμός της Ταξινόμησης συγχώνευσης
Η συγχώνευση είναι ένας εξωτερικός αλγόριθμος που βασίζεται επίσης στη στρατηγική διαίρεσης και κατακράτησης. Τα στοιχεία χωρίζονται ξανά και ξανά σε υπο-συστοιχίες (n / 2) μέχρις ότου παραμείνει μόνο ένα στοιχείο, πράγμα που μειώνει σημαντικά τον χρόνο διαλογής. Χρησιμοποιεί επιπλέον αποθηκευτικό χώρο για την αποθήκευση του βοηθητικού πίνακα. Η επιλογή Συγχώνευση χρησιμοποιεί τρεις συστοιχίες όπου χρησιμοποιούνται δύο για την αποθήκευση κάθε ημίσεος και το τρίτο για την αποθήκευση της τελικής ταξινομημένης λίστας. Κατόπιν, κάθε συστοιχία ταξινομείται αναδρομικά. Επιτέλους, τα υποσυγκροτήματα συγχωνεύονται για να καταστήσουν το μέγεθος στοιχείου n του πίνακα. Ο κατάλογος διαιρείται πάντοτε σε μόλις μισό (n / 2) ανόμοιο με το γρήγορο είδος.
Έστω Α η σειρά των n στοιχείων που πρέπει να ταξινομηθούν A [1], A [2], ........., A [n]. Η ταξινόμηση συγχώνευσης ακολουθεί τα συγκεκριμένα βήματα.
- Διαχωρίστε τη συστοιχία A σε κατά προσέγγιση n / 2 ταξινομημένη υπο-συστοιχία κατά 2, πράγμα που σημαίνει ότι τα στοιχεία στα (A [1], A [2]), (A [3], A [4] k], A [k + 1]), οι υπο-πίνακες A [n-1], A [n]) πρέπει να είναι ταξινομημένες.
- Συνδυάστε κάθε ζεύγος ζευγαριών για να αποκτήσετε τον κατάλογο των ταξινομημένων υποσυγκροτημάτων μεγέθους 4. (A [1], A [2], A [3], A [4]), ......, A [k-1] [k + 1], A [k + 2]), ..., (A [n-3], A [n-2], A [n-1], A [n]).
- Το βήμα 2 εκτελείται επανειλημμένα μέχρις ότου υπάρχει μόνο μία ταξινομημένη συστοιχία μεγέθους η.
Πλεονεκτήματα και μειονεκτήματα
Ο αλγόριθμος ταξινόμησης συγχώνευσης εκτελεί με τον ίδιο ακριβώς και ακριβή τρόπο ανεξάρτητα από τον αριθμό των στοιχείων που συμμετέχουν στη διαλογή. Δουλεύει καλά ακόμα και με το μεγάλο σύνολο δεδομένων. Ωστόσο, καταναλώνει μεγαλύτερο μέρος της μνήμης.
Βασικές διαφορές μεταξύ ταχείας ταξινόμησης και συγχώνευσης
- Στο είδος συγχώνευσης, ο πίνακας πρέπει να χωριστεί σε μόλις δύο μισά (δηλ. N / 2). Αντίθετα, με γρήγορο τρόπο, δεν υπάρχει κανένας καταναγκασμός να διαιρείται ο κατάλογος σε ίσα στοιχεία.
- Η χειρότερη περίπτωση πολυπλοκότητας της ταχείας ταξινόμησης είναι το O (n2) καθώς απαιτεί πολύ περισσότερες συγκρίσεις στη χειρότερη κατάσταση. Αντίθετα, η συγχώνευση έχει την ίδια χειρότερη περίπτωση και τη μέση περίπλοκη περίπτωση, δηλαδή O (n log n).
- Το είδος συγχώνευσης μπορεί να λειτουργήσει καλά σε οποιοδήποτε τύπο δεδομένων, είτε είναι μεγάλο είτε μικρό. Αντίθετα, το γρήγορο είδος δεν μπορεί να λειτουργήσει καλά με μεγάλα σύνολα δεδομένων.
- Η ταχεία ταξινόμηση είναι ταχύτερη από τη συγχώνευση σε ορισμένες περιπτώσεις, όπως για μικρά σύνολα δεδομένων.
- Η συγχώνευση απαιτεί πρόσθετο χώρο μνήμης για την αποθήκευση των βοηθητικών συστοιχιών. Από την άλλη πλευρά, η γρήγορη ταξινόμηση δεν απαιτεί πολύ χώρο για επιπλέον αποθήκευση.
- Το είδος συγχώνευσης είναι πιο αποτελεσματικό από το γρήγορο είδος.
- Η γρήγορη ταξινόμηση είναι η εσωτερική μέθοδος ταξινόμησης όπου τα δεδομένα που πρόκειται να ταξινομηθούν προσαρμόζονται τη φορά στην κύρια μνήμη. Αντιστρόφως, η ταξινόμηση συγχώνευσης είναι εξωτερική μέθοδος ταξινόμησης στην οποία τα δεδομένα που πρόκειται να ταξινομηθούν δεν μπορούν να προσαρμοστούν στη μνήμη ταυτόχρονα και κάποια πρέπει να διατηρηθούν στη βοηθητική μνήμη.
συμπέρασμα
Η γρήγορη ταξινόμηση είναι ταχύτερες περιπτώσεις αλλά είναι αναποτελεσματική σε ορισμένες περιπτώσεις και επίσης πραγματοποιεί πολλές συγκρίσεις σε σύγκριση με τη συγχώνευση. Αν και η συγχώνευση απαιτεί λιγότερη σύγκριση, χρειάζεται ένας πρόσθετος χώρος μνήμης 0 (n) για την αποθήκευση της πρόσθετης συστοιχίας ενώ η γρήγορη ταξινόμηση χρειάζεται χώρο του O (log n).
