Υπάρχουν αρκετοί βασικοί αλγόριθμοι για την επίλυση του προβλήματος της ταξινόμησης ενός πίνακα. Ένα από τα πιο διάσημα μεταξύ τους είναι το insertion sort. Λόγω της σαφήνειας και της απλότητάς της, αλλά χαμηλής απόδοσης, αυτή η μέθοδος χρησιμοποιείται κυρίως στη διδασκαλία του προγραμματισμού. Σας επιτρέπει να κατανοήσετε τους βασικούς μηχανισμούς ταξινόμησης.
Περιγραφή του αλγορίθμου
Η ουσία του αλγορίθμου ταξινόμησης εισαγωγής είναι ότι σχηματίζεται ένα σωστά ταξινομημένο τμήμα μέσα στον αρχικό πίνακα. Κάθε στοιχείο συγκρίνεται ένα προς ένα με το επιλεγμένο τμήμα και εισάγεται στη σωστή θέση. Έτσι, μετά την επανάληψη όλων των στοιχείων, παρατάσσονται με τη σωστή σειρά.
Η σειρά επιλογής στοιχείων μπορεί να είναι οποιαδήποτε, μπορούν να επιλεγούν αυθαίρετα ή σύμφωνα με κάποιον αλγόριθμο. Τις περισσότερες φορές, η διαδοχική απαρίθμηση χρησιμοποιείται από την αρχή του πίνακα, όπου σχηματίζεται ένα διατεταγμένο τμήμα.
Η αρχή της ταξινόμησης μπορεί να μοιάζει με αυτό:
- Λήψη του πρώτου στοιχείου του πίνακα.
- Δεδομένου ότι δεν υπάρχει τίποτα με το οποίο να το συγκρίνετε, πάρτε το ίδιο το στοιχείο σύμφωνα με την παραγγελίαακολουθία.
- Μετάβαση στο δεύτερο στοιχείο.
- Σύγκρινε το με το πρώτο με βάση τον κανόνα ταξινόμησης.
- Αν χρειάζεται, αλλάξτε στοιχεία σε μέρη.
- Λήψη των δύο πρώτων στοιχείων ως διατεταγμένη ακολουθία.
- Μετάβαση στο τρίτο στοιχείο.
- Συγκρίνετέ το με το δεύτερο, αλλάξτε το εάν χρειάζεται.
- Εάν η αντικατάσταση έχει γίνει, συγκρίνετε την με την πρώτη.
- Λήψη τριών στοιχείων ως διατεταγμένη ακολουθία.
Και ούτω καθεξής μέχρι το τέλος του αρχικού πίνακα.
Ταξινόμηση εισαγωγής πραγματικής ζωής
Για λόγους σαφήνειας, αξίζει να δώσουμε ένα παράδειγμα για το πώς χρησιμοποιείται αυτός ο μηχανισμός ταξινόμησης στην καθημερινή ζωή.
Πάρτε, για παράδειγμα, ένα πορτοφόλι. Τα χαρτονομίσματα των εκατοντάδων, των πεντακοσίων και των χιλιάδων δολαρίων βρίσκονται σε αταξία στο διαμέρισμα των τραπεζογραμματίων. Αυτό είναι ένα χάος, σε ένα τέτοιο χαζό είναι δύσκολο να βρεις αμέσως το σωστό κομμάτι χαρτί. Η σειρά των τραπεζογραμματίων πρέπει να ταξινομηθεί.
Το πρώτο είναι ένα τραπεζογραμμάτιο 1000 ρούβλια και αμέσως μετά - 100. Παίρνουμε εκατό και το τοποθετούμε μπροστά. Το τρίτο στη σειρά είναι 500 ρούβλια, η σωστή θέση για αυτό είναι μεταξύ εκατό και χιλίων.
Με τον ίδιο τρόπο ταξινομούμε τις ληφθείσες κάρτες όταν παίζουμε το "Fool" για να διευκολύνουμε την πλοήγησή τους.
Χειριστές και βοηθητικές λειτουργίες
Η μέθοδος ταξινόμησης εισαγωγής λαμβάνει ως είσοδο έναν αρχικό πίνακα προς ταξινόμηση, μια συνάρτηση σύγκρισης και, εάν είναι απαραίτητο, μια συνάρτηση που καθορίζει τον κανόνα για την απαρίθμηση στοιχείων. Τις περισσότερες φορές χρησιμοποιείται αντίδήλωση κανονικού βρόχου.
Το πρώτο στοιχείο είναι από μόνο του ένα ταξινομημένο σύνολο, επομένως η σύγκριση ξεκινά από το δεύτερο.
Ο αλγόριθμος χρησιμοποιεί συχνά μια βοηθητική συνάρτηση για την ανταλλαγή δύο τιμών (swap). Χρησιμοποιεί μια πρόσθετη προσωρινή μεταβλητή, η οποία καταναλώνει τη μνήμη και επιβραδύνει λίγο τον κώδικα.
Μια εναλλακτική είναι να μετατοπίσετε μαζικά μια ομάδα στοιχείων και μετά να εισαγάγετε την τρέχουσα στον ελεύθερο χώρο. Σε αυτήν την περίπτωση, η μετάβαση στο επόμενο στοιχείο λαμβάνει χώρα όταν η σύγκριση έδωσε ένα θετικό αποτέλεσμα, το οποίο υποδεικνύει τη σωστή σειρά.
Παραδείγματα εφαρμογής
Η συγκεκριμένη υλοποίηση εξαρτάται σε μεγάλο βαθμό από τη γλώσσα προγραμματισμού που χρησιμοποιείται, τη σύνταξη και τις δομές της.
Κλασική εφαρμογή C με χρήση προσωρινής μεταβλητής για ανταλλαγή τιμών:
int i, j, θερμοκρασία; for (i=1; i =0; j--) { if (array[j] < temp) break; πίνακας[j + 1]=πίνακας[j]; πίνακας[j]=θερμοκρασία; } }
Υλοποίηση PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Εδώ, πρώτα, όλα τα στοιχεία που δεν ταιριάζουν με τη συνθήκη ταξινόμησης μετατοπίζονται προς τα δεξιά και, στη συνέχεια, το τρέχον στοιχείο εισάγεται στον ελεύθερο χώρο.
Κώδικας Java με χρήση βρόχου while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
Η γενική σημασία του κώδικα παραμένει αμετάβλητη: κάθε στοιχείο του πίνακα συγκρίνεται διαδοχικά με τα προηγούμενα και ανταλλάσσεται με αυτά εάν είναι απαραίτητο.
Εκτιμώμενος χρόνος λειτουργίας
Προφανώς, στην καλύτερη περίπτωση, η είσοδος του αλγορίθμου θα είναι ένας πίνακας που έχει ήδη ταξινομηθεί με τον σωστό τρόπο. Σε αυτήν την περίπτωση, ο αλγόριθμος θα πρέπει απλώς να ελέγξει κάθε στοιχείο για να βεβαιωθεί ότι βρίσκεται στη σωστή θέση χωρίς να κάνει ανταλλαγές. Έτσι, ο χρόνος εκτέλεσης θα εξαρτηθεί άμεσα από το μήκος του αρχικού πίνακα O(n).
Η είσοδος στη χειρότερη περίπτωση είναι ένας πίνακας ταξινομημένος με αντίστροφη σειρά. Αυτό θα απαιτήσει μεγάλο αριθμό μεταθέσεων, η συνάρτηση χρόνου εκτέλεσης θα εξαρτάται από τον αριθμό των στοιχείων στο τετράγωνο.
Ο ακριβής αριθμός των μεταθέσεων για έναν εντελώς μη ταξινομημένο πίνακα μπορεί να υπολογιστεί χρησιμοποιώντας τον τύπο:
n(n-1)/2
όπου n είναι το μήκος του αρχικού πίνακα. Έτσι, θα χρειαστούν 4950 μεταθέσεις για να τακτοποιηθούν 100 στοιχεία με τη σωστή σειρά.
Η μέθοδος εισαγωγής είναι πολύ αποτελεσματική για την ταξινόμηση μικρών ή μερικώς ταξινομημένων πινάκων. Ωστόσο, δεν συνιστάται η εφαρμογή του παντού λόγω της υψηλής πολυπλοκότητας των υπολογισμών.
Ο αλγόριθμος χρησιμοποιείται ως βοηθητικός σε πολλές άλλες πιο σύνθετες μεθόδους ταξινόμησης.
Ταξινόμηση ίσων τιμών
Ο αλγόριθμος εισαγωγής ανήκει στα λεγόμενα σταθερά είδη. Σημαίνει,ότι δεν ανταλλάσσει πανομοιότυπα στοιχεία, αλλά διατηρεί την αρχική τους σειρά. Ο δείκτης σταθερότητας είναι σε πολλές περιπτώσεις σημαντικός για τη σωστή σειρά.
Το παραπάνω είναι ένα εξαιρετικό οπτικό παράδειγμα εισαγωγής σε έναν χορό.
