Η ταξινόμηση είναι μια βασική λειτουργία στην οποία τα στοιχεία ενός πίνακα διατάσσονται με κάποια συγκεκριμένη σειρά για να βελτιώσουν την δυνατότητα αναζήτησης. Με απλά λόγια, τα δεδομένα ταξινομούνται έτσι ώστε να μπορούν εύκολα να αναζητηθούν.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Ταξινόμηση εισαγωγής | Ταξινόμηση επιλογής |
|---|---|---|
| Βασικός | Τα δεδομένα ταξινομούνται με την εισαγωγή των δεδομένων σε ένα υπάρχον ταξινομημένο αρχείο. | Τα δεδομένα ταξινομούνται επιλέγοντας και τοποθετώντας τα διαδοχικά στοιχεία σε μια ταξινομημένη τοποθεσία. |
| Φύση | Σταθερός | Ασταθής |
| Διαδικασία που πρέπει να ακολουθηθεί | Τα στοιχεία είναι γνωστά εκ των προτέρων ενώ αναζητείται η θέση για να τα τοποθετήσετε. | Η τοποθεσία είναι ήδη γνωστή κατά την αναζήτηση των στοιχείων. |
| Άμεσα δεδομένα | Το είδος εισαγωγής είναι μια τεχνική διαλογής που μπορεί να αντιμετωπίσει άμεσα δεδομένα. | Δεν μπορεί να ασχοληθεί με τα άμεσα δεδομένα, πρέπει να είναι παρούσα στην αρχή. |
| Βέλτιστη πολυπλοκότητα περιπτώσεων | Επί) | Ο (η2) |
Ορισμός της Ταξινόμησης Εισαγωγής
Η ταξινόμηση παρεμβολών λειτουργεί εισάγοντας το σύνολο τιμών στο υπάρχον ταξινομημένο αρχείο. Κατασκευάζει τη διατεταγμένη συστοιχία εισάγοντας ένα μόνο στοιχείο τη φορά. Αυτή η διαδικασία συνεχίζεται μέχρι να ταξινομηθεί ολόκληρη η συστοιχία με κάποια σειρά. Η κύρια έννοια πίσω από το είδος εισαγωγής είναι να εισαγάγετε κάθε στοιχείο στην κατάλληλη θέση του στον τελικό κατάλογο. Η μέθοδος ταξινόμησης εισαγωγής αποθηκεύει μια αποτελεσματική ποσότητα μνήμης.
Εργασία του είδους εισαγωγής
- Χρησιμοποιεί δύο σύνολα συστοιχιών όπου αποθηκεύονται τα ταξινομημένα δεδομένα και άλλα σε μη διαλεγμένα δεδομένα.
- Ο αλγόριθμος ταξινόμησης λειτουργεί μέχρι να υπάρχουν στοιχεία στο σύνολο.
- Ας υποθέσουμε ότι υπάρχουν στοιχεία 'n' στον πίνακα. Αρχικά, το στοιχείο με δείκτη 0 (LB = 0) υπάρχει στο ταξινομημένο σύνολο. Τα υπόλοιπα στοιχεία βρίσκονται στο μη διαχωρισμένο τμήμα της λίστας.
- Το πρώτο στοιχείο του μη διατεταγμένου τμήματος έχει δείκτη συστοιχίας 1 (Αν LB = 0).
- Μετά από κάθε επανάληψη, επιλέγει το πρώτο στοιχείο του διαχωρισμένου διαμερίσματος και το εισάγει στη σωστή θέση στο ταξινομημένο σύνολο.
Πλεονεκτήματα του είδους εισαγωγής
- Εύκολη εφαρμογή και πολύ αποτελεσματική όταν χρησιμοποιείται με μικρά σύνολα δεδομένων.
- Η πρόσθετη απαίτηση χώρου μνήμης του είδους εισαγωγής είναι μικρότερη (δηλ., O (1)).
- Θεωρείται ότι είναι τεχνική ζωντανής διαλογής καθώς ο κατάλογος μπορεί να ταξινομηθεί καθώς λαμβάνονται τα νέα στοιχεία.
- Είναι πιο γρήγορος από άλλους αλγόριθμους διαλογής.
Παράδειγμα:
Ορισμός της ταξινόμησης επιλογής
Το είδος επιλογής πραγματοποιεί τη διαλογή αναζητώντας τον αριθμό ελάχιστης τιμής και τοποθετώντας την στην πρώτη ή την τελευταία θέση σύμφωνα με τη σειρά (προς τα πάνω ή προς τα κάτω). Η διαδικασία αναζήτησης του ελάχιστου κλειδιού και τοποθέτησή του στη σωστή θέση συνεχίζεται μέχρις ότου όλα τα στοιχεία τοποθετηθούν στη σωστή θέση.
Εργασία της ταξινόμησης επιλογής
- Υποθέστε ένα ARR πίνακα με στοιχεία N στη μνήμη.
- Στο πρώτο πέρασμα, το μικρότερο πλήκτρο αναζητείται μαζί με τη θέση του, τότε το ARR [POS] αντικαθίσταται με ARR [0]. Επομένως, το ARR [0] ταξινομείται.
- Στο δεύτερο πέρασμα, και πάλι η θέση της μικρότερης τιμής προσδιορίζεται στο υποσύστημα των στοιχείων Ν-1. Ανταλλάξτε το ARR [POS] με ARR [1].
- Στο πέρασμα Ν-1, εκτελείται η ίδια διαδικασία για να ταξινομηθεί ο αριθμός Ν των στοιχείων.
Παράδειγμα:
Βασικές διαφορές μεταξύ της ταξινόμησης εισόδου και της ταξινόμησης επιλογής
- Το είδος εισαγωγής συνήθως εκτελεί τη λειτουργία εισαγωγής. Αντίθετα, το είδος επιλογής διεξάγει την επιλογή και την τοποθέτηση των απαιτούμενων στοιχείων.
- Ο τύπος εισαγωγής λέγεται ότι είναι σταθερός, ενώ η επιλογή δεν είναι σταθερός αλγόριθμος.
- Στο αλγόριθμο ταξινόμησης εισαγωγής τα στοιχεία είναι παλαιότερα γνωστά. Σε αντίθεση, η επιλογή επιλογής περιέχει τη θέση εκ των προτέρων.
- Το είδος εισαγωγής είναι μια τεχνική ζωντανής διαλογής, όπου τα στοιχεία που φθάνουν ταξινομούνται αμέσως στη λίστα, ενώ η επιλογή των επιλογών δεν μπορεί να λειτουργήσει καλά με τα άμεσα δεδομένα.
- Το είδος εισαγωγής έχει τον χρόνο λειτουργίας O (n) στην καλύτερη περίπτωση. Αντιθέτως, η καλύτερη πολυπλοκότητα του χρόνου εκτέλεσης του υποδείγματος είναι το O (n2).
Πολυπλοκότητα του είδους εισαγωγής
Η καλύτερη πολυπλοκότητα του τύπου εισαγωγής είναι οι O (n) φορές, δηλαδή όταν η συστοιχία έχει προηγουμένως ταξινομηθεί. Με τον ίδιο τρόπο, όταν η συστοιχία ταξινομείται με αντίστροφη σειρά, το πρώτο στοιχείο του μη διατεταγμένου πίνακα πρέπει να συγκριθεί με κάθε στοιχείο του ταξινομημένου συνόλου. Έτσι, στη χειρότερη περίπτωση, ο χρόνος λειτουργίας του είδους Εισαγωγής είναι τετραγωνικός, δηλαδή, O (n2) . Κατά μέσο όρο, πρέπει επίσης να κάνει τις ελάχιστες (k-1) / 2 συγκρίσεις. Ως εκ τούτου, η μέση περίπτωση έχει επίσης τετραγωνικό χρόνο λειτουργίας O (n2).
Πολυπλοκότητα της ταξινόμησης επιλογής
Δεδομένου ότι η λειτουργία της επιλογής, η ταξινόμηση δεν εξαρτάται από την αρχική σειρά των στοιχείων στη συστοιχία, έτσι δεν υπάρχει μεγάλη διαφορά μεταξύ της βέλτιστης περίπτωσης και της χειρότερης περίπλοκης περίπτωσης του είδους επιλογής.
Η επιλογή επιλογής επιλέγει το στοιχείο ελάχιστης τιμής, στη διαδικασία επιλογής ελέγχονται όλοι οι αριθμοί 'n' των στοιχείων. Επομένως οι n-1 συγκρίσεις γίνονται στο πρώτο πέρασμα. Στη συνέχεια, τα στοιχεία ανταλλάσσονται. Παρόμοια, στο δεύτερο πέρασμα, για να βρούμε και το δεύτερο μικρότερο στοιχείο, απαιτούμε τη σάρωση των στοιχείων n-1 ανάπαυσης και η διαδικασία συνεχίζεται μέχρι να ταξινομηθεί ολόκληρη η συστοιχία.
Έτσι, η πολυπλοκότητα του χρόνου εκτέλεσης της επιλογής είναι O (n2) .
= (η-1) + (η-2) + ......... .. + 2 + 1
= η (η-1) / 2 = Ο (η2)
συμπέρασμα
Μεταξύ των δύο αλγορίθμων ταξινόμησης, το είδος εισαγωγής είναι γρήγορο, αποτελεσματικό, σταθερό, ενώ η ταξινόμηση των επιλογών λειτουργεί αποτελεσματικά μόνο όταν εμπλέκεται η μικρή ομάδα στοιχείων ή η λίστα έχει προηγουμένως ταξινομηθεί. Ο αριθμός των συγκρίσεων που έγιναν με την επιλογή των επιλογών είναι μεγαλύτερος από τις πραγματοποιηθείσες κινήσεις, ενώ στην ταξινόμηση εισαγωγής ο αριθμός των φορών που ένα στοιχείο μετακινείται ή ανταλλάσσεται είναι μεγαλύτερο από τις συγκρίσεις που έγιναν.
