Βασική διαφορά – Ταξινόμηση εισαγωγής έναντι ταξινόμησης επιλογής
Η ταξινόμηση εισαγωγής και η ταξινόμηση επιλογής είναι δύο αλγόριθμοι ταξινόμησης που χρησιμοποιούνται για την ταξινόμηση μιας συλλογής δεδομένων. Μερικές φορές είναι απαραίτητο να τακτοποιήσετε τα δεδομένα με μια συγκεκριμένη σειρά. Οι αλγόριθμοι ταξινόμησης είναι μηχανισμοί για την ταξινόμηση ενός συνόλου δεδομένων. Κατά τη διαλογή, τα δεδομένα ταξινομούνται σύμφωνα με αριθμητική ή λεξικογραφική σειρά. Εάν τα δεδομένα ταξινομηθούν σωστά, τότε θα ήταν εύκολο να αναζητήσετε δεδομένα πιο γρήγορα. Εάν οι αριθμοί τηλεφώνου σε έναν τηλεφωνικό κατάλογο δεν είναι ταξινομημένοι, τότε θα ήταν δύσκολο να βρείτε έναν συγκεκριμένο αριθμό τηλεφώνου. Με τον ίδιο τρόπο, εάν οι λέξεις στο λεξικό δεν είναι ταξινομημένες με αλφαβητική σειρά, θα ήταν πολύ δύσκολο να βρεθούν λέξεις. Επομένως, η ταξινόμηση είναι χρήσιμη στην καθημερινή ζωή. Στην Επιστήμη Υπολογιστών, υπάρχουν αλγόριθμοι ταξινόμησης για την ταξινόμηση μιας συλλογής δεδομένων. Δύο τέτοιοι αλγόριθμοι είναι η ταξινόμηση εισαγωγής και η ταξινόμηση επιλογής. Η ταξινόμηση εισαγωγής είναι ο αλγόριθμος ταξινόμησης που ταξινομεί τον πίνακα μετατοπίζοντας στοιχεία ένα προς ένα. Η ταξινόμηση επιλογής είναι ο αλγόριθμος ταξινόμησης που βρίσκει το μικρότερο στοιχείο στον πίνακα και ανταλλάσσει το στοιχείο με την πρώτη θέση, στη συνέχεια βρίσκει το δεύτερο μικρότερο στοιχείο και το ανταλλάσσει με το στοιχείο στη δεύτερη θέση και συνεχίζει τη διαδικασία μέχρι να ταξινομηθεί ολόκληρος ο πίνακας. Η βασική διαφορά μεταξύ της ταξινόμησης εισαγωγής και της ταξινόμησης επιλογής είναι ότι η ταξινόμηση εισαγωγής συγκρίνει δύο στοιχεία κάθε φορά, ενώ η ταξινόμηση επιλογής επιλέγει το ελάχιστο στοιχείο από ολόκληρο τον πίνακα και το ταξινομεί.
Τι είναι Ταξινόμηση Εισαγωγής;
Η ταξινόμηση εισαγωγής είναι ένας επιτόπιος αλγόριθμος ταξινόμησης που βασίζεται σε σύγκριση. Σε αυτή τη μέθοδο, ο πίνακας αναζητείται βήμα προς βήμα. Τα μη ταξινομημένα στοιχεία μετακινούνται και εισάγονται στην ταξινομημένη υπολίστα του πίνακα. Ο αλγόριθμος ταξινόμησης εισαγωγής μπορεί να εξηγηθεί χρησιμοποιώντας το ακόλουθο παράδειγμα.
Για παράδειγμα, πάρτε τον αρχικό πίνακα ως 77, 33, 44, 11, 88. Σε αυτόν τον αλγόριθμο ταξινόμησης, το πρώτο βήμα είναι να επιλέξετε το τρέχον στοιχείο.
Το τρέχον στοιχείο είναι 77. Το τρέχον στοιχείο συγκρίνεται με όλα τα στοιχεία στην αριστερή πλευρά. Το 77, είναι το πρώτο στοιχείο και δεν υπάρχουν στοιχεία στην αριστερή πλευρά. Ο δείκτης της τρέχουσας θέσης είναι 0.
Τότε ο δείκτης της τρέχουσας θέσης αυξάνεται κατά 1. Τώρα ο δείκτης είναι 1 και το τρέχον στοιχείο είναι 33. Όταν το συγκρίνουμε με το στοιχείο στα αριστερά, είναι μικρότερο από 77. Τότε και οι δύο αυτές τιμές ανταλλάσσονται. Τώρα το 33 βρίσκεται στον δείκτη 0 και το 77 στον δείκτη 1.
Τώρα ο πίνακας είναι 33, 77, 44, 11, 88.
Και πάλι, ο δείκτης αυξάνεται. Ο δείκτης είναι 2 και το τρέχον στοιχείο είναι 44. Συγκρίνεται με τα στοιχεία στην αριστερή πλευρά. Το 44 είναι μικρότερο από το 77. Έτσι αυτές οι δύο τιμές ανταλλάσσονται. Τώρα ο πίνακας είναι 33, 44, 77, 11, 88. Είναι απαραίτητο να συγκρίνουμε όλα τα στοιχεία στα αριστερά. Έτσι, το 44 συγκρίνεται με το 33. Το 33 είναι μικρότερο από το 44. Επομένως, αυτά τα στοιχεία δεν χρειάζεται να ανταλλάσσονται.
Τώρα ο πίνακας είναι 33, 44, 77, 11, 88.
Και πάλι, ο δείκτης αυξάνεται. Ο δείκτης είναι 3 και το τρέχον στοιχείο είναι 11. Συγκρίνεται με όλα τα στοιχεία στα αριστερά. Το 11 είναι μικρότερο από το 77, επομένως αυτά τα δύο ανταλλάσσονται. Τώρα ο πίνακας είναι 33, 44, 11, 77, 88. Όταν συγκρίνουμε το 11 και το 44, το 11 είναι μικρότερο από 44. Άρα αυτά τα δύο ανταλλάσσονται. Τώρα οι πίνακες είναι 33, 11, 44, 77, 88. Και πάλι το 11 συγκρίνεται με το 33. Το 11 είναι μικρότερο από 33, επομένως αυτές οι δύο τιμές ανταλλάσσονται.
Τώρα ο πίνακας είναι 11, 33, 44, 77, 88.
Αυξάνοντας τον δείκτη θα γίνει ο δείκτης στο 4. Η τιμή είναι 88. Είναι υψηλότερη από 77. Επομένως, δεν χρειάζεται αλλαγή. Τέλος, ο ταξινομημένος πίνακας είναι 11, 33, 44, 77, 88.
Εικόνα 01: Παράδειγμα ταξινόμησης εισαγωγής
Η υλοποίηση της ταξινόμησης εισαγωγής είναι όπως παραπάνω. Ο αρχικός πίνακας ήταν 77, 33, 44, 11, 88. Μετά την ταξινόμηση, δίνει την έξοδο 11, 33, 44, 77, 88.
Τι είναι η ταξινόμηση επιλογής;
Η ταξινόμηση επιλογής είναι ένας επιτόπιος αλγόριθμος ταξινόμησης που βασίζεται σε σύγκριση. Οι πίνακες χωρίζονται σε τμήματα. Το ταξινομημένο τμήμα βρίσκεται στο αριστερό άκρο. Το μη ταξινομημένο τμήμα βρίσκεται στο δεξί άκρο. Αρχικά, πρέπει να βρεθεί η μικρότερη τιμή. Στη συνέχεια, ανταλλάσσεται με το αριστερό στοιχείο. Τώρα αυτό το στοιχείο βρίσκεται στον ταξινομημένο πίνακα. Αυτή η διαδικασία συνεχίζει να μετακινεί μη ταξινομημένο όριο πίνακα από ένα στοιχείο προς τα δεξιά. Ο αλγόριθμος ταξινόμησης επιλογής μπορεί να εξηγηθεί χρησιμοποιώντας το ακόλουθο παράδειγμα.
Για παράδειγμα, πάρτε τον αρχικό πίνακα ως 77, 33, 44, 11, 88, 22. Σε αυτόν τον αλγόριθμο ταξινόμησης, βρίσκεται ο μικρότερος στον πίνακα. Το μικρότερο στοιχείο είναι 11. Ανταλλάσσεται με το στοιχείο στον δείκτη 0 του πίνακα.
Τώρα ο πίνακας είναι 11, 33, 44, 77, 88, 22.
Το μικρότερο στοιχείο βρίσκεται στο ευρετήριο 0, επομένως το 11 ταξινομείται τώρα. Από τα υπόλοιπα στοιχεία, το μικρότερο είναι 22. Ανταλλάσσεται με το στοιχείο ευρετηρίου 1st.
Τώρα ο πίνακας είναι 11, 22, 44, 77, 88, 33.
Τα στοιχεία 11 και 22 είναι ήδη ταξινομημένα. Από τα υπόλοιπα, η μικρότερη τιμή είναι 33. Ανταλλάσσεται με το στοιχείο ευρετηρίου 2nd.
Τώρα ο πίνακας είναι 11, 22, 33, 77, 88, 44.
Τα στοιχεία 11, 22 και 33 είναι ήδη ταξινομημένα. Από τα υπόλοιπα, η μικρότερη τιμή είναι 44. Ανταλλάσσεται με το στοιχείο ευρετηρίου 3rd.
Τώρα ο πίνακας είναι 11, 22, 33, 44, 88, 66.
Τα στοιχεία 11, 22, 33, 44 είναι ήδη ταξινομημένα. Τα υπόλοιπα στοιχεία είναι 88 και 66. Το στοιχείο 66 ανταλλάσσεται με το στοιχείο ευρετηρίου 4th.
Τώρα ο πίνακας είναι 11, 22, 33, 44, 66, 88.
Είναι ο ταξινομημένος πίνακας που χρησιμοποιεί τον αλγόριθμο ταξινόμησης επιλογής.
Εικόνα 02: Παράδειγμα ταξινόμησης επιλογής
Η υλοποίηση της ταξινόμησης εισαγωγής είναι όπως παραπάνω. Ο αρχικός πίνακας ήταν 77, 33, 44, 11, 88. Μετά την ταξινόμηση, δίνει την έξοδο 11, 33, 44, 77, 88.
Ποια είναι η ομοιότητα μεταξύ της ταξινόμησης εισαγωγής και της ταξινόμησης επιλογής;
Τόσο η ταξινόμηση εισαγωγής όσο και η ταξινόμηση επιλογής είναι αλγόριθμοι ταξινόμησης
Ποια είναι η διαφορά μεταξύ της ταξινόμησης εισαγωγής και της ταξινόμησης επιλογής;
Εισαγωγή Ταξινόμηση έναντι Ταξινόμησης Επιλογής |
|
| Η ταξινόμηση εισαγωγής είναι ο αλγόριθμος ταξινόμησης που ταξινομεί τον πίνακα μετατοπίζοντας στοιχεία ένα προς ένα. | Η ταξινόμηση επιλογής είναι ο αλγόριθμος ταξινόμησης που βρίσκει το μικρότερο στοιχείο στον πίνακα και ανταλλάσσει το στοιχείο με την πρώτη θέση, στη συνέχεια βρίσκει το δεύτερο μικρότερο στοιχείο και το ανταλλάσσει με το στοιχείο στη δεύτερη θέση και συνεχίζει τη διαδικασία μέχρι ολόκληρος ο πίνακας είναι ταξινομημένος. |
| Διαδικασία | |
| Η ταξινόμηση εισαγωγής είναι για την ταξινόμηση της δευτερεύουσας λίστας συγκρίνοντας δύο στοιχεία μέχρι να ταξινομηθεί ολόκληρος ο πίνακας. | Η ταξινόμηση επιλογής επιλέγει το ελάχιστο στοιχείο και το ανταλλάσσει με την πρώτη θέση, επιλέξτε ξανά το ελάχιστο για τα υπόλοιπα και αλλάξτε το στη δεύτερη θέση και συνεχίστε αυτήν τη διαδικασία μέχρι το τέλος. |
| Σταθερότητα | |
| Η ταξινόμηση εισαγωγής είναι ένας σταθερός αλγόριθμος ταξινόμησης. | Η ταξινόμηση επιλογής δεν είναι σταθερός αλγόριθμος ταξινόμησης. |
Σύνοψη – Ταξινόμηση εισαγωγής έναντι ταξινόμησης επιλογής
Μερικές φορές είναι απαραίτητο να ταξινομήσετε δεδομένα. Στην Επιστήμη Υπολογιστών, υπάρχουν αλγόριθμοι για την ταξινόμηση δεδομένων. Αυτό το άρθρο εξέτασε τους δύο αλγόριθμους ταξινόμησης που είναι η ταξινόμηση εισαγωγής και η ταξινόμηση επιλογής. Η ταξινόμηση εισαγωγής είναι ο αλγόριθμος ταξινόμησης που ταξινομεί τον πίνακα μετατοπίζοντας στοιχεία ένα προς ένα. Η ταξινόμηση επιλογής είναι ο αλγόριθμος ταξινόμησης που βρίσκει το μικρότερο στοιχείο στον πίνακα και ανταλλάσσει το στοιχείο με την πρώτη θέση, στη συνέχεια βρίσκει το δεύτερο μικρότερο στοιχείο και το ανταλλάσσει με το στοιχείο στη δεύτερη θέση και συνεχίζει τη διαδικασία μέχρι να ταξινομηθεί ολόκληρος ο πίνακας. Η διαφορά μεταξύ της ταξινόμησης εισαγωγής και της ταξινόμησης επιλογής είναι ότι η ταξινόμηση εισαγωγής συγκρίνει δύο στοιχεία κάθε φορά, ενώ η ταξινόμηση επιλογής επιλέγει το ελάχιστο στοιχείο από ολόκληρο τον πίνακα και το ταξινομεί.
Λήψη του PDF του Insertion Sort vs Selection Sort
Μπορείτε να κατεβάσετε την έκδοση PDF αυτού του άρθρου και να τη χρησιμοποιήσετε για σκοπούς εκτός σύνδεσης σύμφωνα με τη σημείωση παραπομπής. Κατεβάστε την έκδοση PDF εδώ: Διαφορά μεταξύ ταξινόμησης εισαγωγής και ταξινόμησης επιλογής
