Η ταξινόμηση εισαγωγής είναι ένας απλός αλγόριθμος ταξινόμησης που λειτουργεί εισάγοντας κάθε στοιχείο ενός πίνακα στη σωστή του θέση στον πίνακα. Ξεκινά με έναν κενό ταξινομημένο πίνακα και στη συνέχεια επαναλαμβάνεται μέσω του πίνακα εισόδου, εισάγοντας κάθε στοιχείο στη σωστή του θέση στον ταξινομημένο πίνακα. Αυτή η διαδικασία επαναλαμβάνεται μέχρι να ταξινομηθεί ολόκληρος ο πίνακας εισόδου.
Ακολουθεί ο αλγόριθμος βήμα προς βήμα για την ταξινόμηση εισαγωγής:
1. Ξεκινήστε με έναν κενό ταξινομημένο πίνακα.
2. Επανάληψη μέσω του πίνακα εισόδου.
3. Για κάθε στοιχείο στον πίνακα εισόδου, τοποθετήστε το στη σωστή θέση του στον ταξινομημένο πίνακα.
4. Για να εισαγάγετε ένα στοιχείο, συγκρίνετε το με κάθε στοιχείο στον ταξινομημένο πίνακα, ξεκινώντας από το πρώτο στοιχείο.
5. Εάν το στοιχείο είναι μικρότερο από το τρέχον στοιχείο στον ταξινομημένο πίνακα, τοποθετήστε το πριν από το τρέχον στοιχείο.
6. Εάν το στοιχείο είναι μεγαλύτερο από το τρέχον στοιχείο στον ταξινομημένο πίνακα, συνεχίστε τη σύγκριση με το επόμενο στοιχείο στον ταξινομημένο πίνακα.
7. Επαναλάβετε τα βήματα 4-6 μέχρι το στοιχείο να εισαχθεί στη σωστή θέση του στον ταξινομημένο πίνακα.
8. Επαναλάβετε τα βήματα 2-7 για κάθε στοιχείο του πίνακα εισόδου.
Ας εξετάσουμε τον ακόλουθο πίνακα εισόδου:
```
[5, 2, 8, 3, 1]
```
Τα ακόλουθα βήματα δείχνουν πώς ο αλγόριθμος ταξινόμησης εισαγωγής θα ταξινομήσει αυτόν τον πίνακα:
1. Ξεκινήστε με έναν κενό ταξινομημένο πίνακα.
```
[]
```
2. Επανάληψη μέσω του πίνακα εισόδου.
```
[5]
```
3. Για κάθε στοιχείο στον πίνακα εισόδου, τοποθετήστε το στη σωστή θέση του στον ταξινομημένο πίνακα.
```
[5]
```
4. Για να εισαγάγετε το στοιχείο 2, συγκρίνετε το με κάθε στοιχείο στον ταξινομημένο πίνακα, ξεκινώντας από το πρώτο στοιχείο.
```
[5, 2]
```
5. Επειδή το 2 είναι μικρότερο από το 5, τοποθετήστε το πριν από το τρέχον στοιχείο.
```
[2, 5]
```
6. Επανάληψη μέσω του πίνακα εισόδου.
```
[2, 5, 8]
```
7. Για κάθε στοιχείο στον πίνακα εισόδου, τοποθετήστε το στη σωστή θέση του στον ταξινομημένο πίνακα.
```
[2, 5, 8]
```
8. Για να εισαγάγετε το στοιχείο 3, συγκρίνετε το με κάθε στοιχείο στον ταξινομημένο πίνακα, ξεκινώντας από το πρώτο στοιχείο.
```
[2, 3, 5, 8]
```
9. Επειδή το 3 είναι μικρότερο από το 5, τοποθετήστε το πριν από το τρέχον στοιχείο.
```
[2, 3, 5, 8]
```
10. Επανάληψη μέσω του πίνακα εισόδου.
```
[2, 3, 5, 8, 1]
```
11. Για κάθε στοιχείο στον πίνακα εισόδου, τοποθετήστε το στη σωστή θέση του στον ταξινομημένο πίνακα.
```
[1, 2, 3, 5, 8]
```
12. Για να εισαγάγετε το στοιχείο 1, συγκρίνετε το με κάθε στοιχείο στον ταξινομημένο πίνακα, ξεκινώντας από το πρώτο στοιχείο.
```
[1, 2, 3, 5, 8]
```
13. Επειδή το 1 είναι μικρότερο από το 2, τοποθετήστε το πριν από το τρέχον στοιχείο.
```
[1, 2, 3, 5, 8]
```
14. Ο ταξινομημένος πίνακας έχει πλέον ολοκληρωθεί.
```
[1, 2, 3, 5, 8]
```
Η χρονική πολυπλοκότητα της ταξινόμησης εισαγωγής είναι O(n^2), όπου n είναι το μήκος του πίνακα εισόδου. Αυτό σημαίνει ότι ο χρόνος εκτέλεσης της ταξινόμησης εισαγωγής αυξάνεται τετραγωνικά καθώς αυξάνεται το μέγεθος του πίνακα εισόδου. Η ταξινόμηση εισαγωγής αποδίδει καλύτερα όταν ο πίνακας εισόδου είναι ήδη σχεδόν ταξινομημένος, οπότε η χρονική του πολυπλοκότητα είναι O(n).
Η ταξινόμηση εισαγωγής απαιτεί βοηθητικό χώρο O(1), καθώς χρειάζεται να αποθηκεύσει μόνο μία μεταβλητή (το τρέχον στοιχείο που εισάγεται) εκτός από τον πίνακα εισόδου.
Η ταξινόμηση εισαγωγής έχει μερικά πλεονεκτήματα και μειονεκτήματα:
Πλεονεκτήματα:
* Απλό στην εφαρμογή
* Αποτελεσματικό για μικρούς πίνακες ή σχεδόν ταξινομημένους πίνακες
* Σταθερός αλγόριθμος ταξινόμησης (διατηρεί τη σχετική σειρά ίσων στοιχείων)
Μειονεκτήματα:
* Δεν είναι αποτελεσματικό για μεγάλες συστοιχίες
* Τετραγωνική χρονική πολυπλοκότητα (O(n^2))
* Δεν είναι αλγόριθμος επιτόπιας ταξινόμησης (απαιτεί επιπλέον χώρο)
Η ταξινόμηση εισαγωγής είναι ένας απλός και αποτελεσματικός αλγόριθμος ταξινόμησης που έχει καλή απόδοση για μικρούς πίνακες ή σχεδόν ταξινομημένους πίνακες. Η απλότητα και η σταθερότητά του το καθιστούν χρήσιμο αλγόριθμο για εκπαιδευτικούς σκοπούς και για εξειδικευμένες εφαρμογές. Ωστόσο, δεν είναι ο πιο αποτελεσματικός αλγόριθμος ταξινόμησης για μεγάλους πίνακες, όπου θα πρέπει να χρησιμοποιούνται πιο αποτελεσματικοί αλγόριθμοι όπως η γρήγορη ταξινόμηση ή η συγχώνευση.
Πνευματικά δικαιώματα © Γνώση Υπολογιστών Όλα τα δικαιώματα κατοχυρωμένα