Τι είναι η ταξινόμηση εισαγωγής στο C;
Η μέθοδος ταξινόμησης που ονομάζεται ταξινόμηση εισαγωγής ταιριάζει κάθε μεμονωμένο στοιχείο με γειτονικά καθώς επαναλαμβάνεται σε έναν πίνακα. Ένα μικρότερο στοιχείο από αυτό πριν εισαχθεί στην ταξινομημένη υποσυστοιχία στην κατάλληλη θέση.
Για να διευκρινίσω περαιτέρω, έχω δείξει ένα παράδειγμα στο οποίο έχω εξετάσει έναν πίνακα τεσσάρων στοιχείων σε έναν πίνακα όπως π.χ. arr[]= {5, 4, 60, 9} και θέλουμε να ταξινομήσουμε αυτό το στοιχείο σε αύξουσα σειρά χρησιμοποιώντας ταξινόμηση εισαγωγής. Οι ακόλουθες αλληλεπιδράσεις εξηγούν την πλήρη ξηρή εκτέλεση της ταξινόμησης εισαγωγής:
Επανάληψη 1
| 5 | 4 | 60 | 9 |
Έχουμε έναν πίνακα ως arr[5, 4, 60, 9] τώρα, στην πρώτη επανάληψη της ταξινόμησης εισαγωγής συγκρίνουμε πρώτα τα δύο πρώτα στοιχεία όπως 5 και 4, καθώς το arr[5] είναι > arr[4] τα εναλλάσσουμε για να ταξινομήσουμε τον πίνακα σε αύξουσα σειρά. Τώρα, ο πίνακας θα είναι:
| 4 | 5 | 60 | 9 |
Επανάληψη 2
| 4 | 5 | 60 | 9 |
Στη δεύτερη επανάληψη, συγκρίνουμε τα επόμενα δύο στοιχεία, όπως το arr[5] με το arr[60].
Καθώς το arr[5] < arr[60] έτσι η εναλλαγή δεν συμβαίνει καθώς έχει ήδη ταξινομηθεί σε αύξουσα σειρά. Τώρα, ο πίνακας γίνεται:
| 4 | 5 | 60 | 9 |
Επανάληψη 3
| 4 | 5 | 60 | 9 |
Όπως και στην τρίτη επανάληψη, αντιστοιχίζουμε το τρίτο και το τέταρτο στοιχείο όπως το arr[60] με το arr[9].
Τώρα, βλέπουμε ότι το arr[60] > arr[9] so swapping συμβαίνει, τότε ο πίνακας θα ταξινομηθεί με αύξουσα σειρά.
| 4 | 5 | 9 | 60 |
Έτσι λειτουργεί η ταξινόμηση εισαγωγής στο C που ταξινομεί ένα στοιχείο πίνακα εύκολα σε αύξουσα ή φθίνουσα σειρά.
Διάγραμμα ροής Ταξινόμηση εισαγωγής
Ακολουθεί το διάγραμμα ροής του αλγορίθμου ταξινόμησης εισαγωγής:
Παράδειγμα εφαρμογής της ταξινόμησης εισαγωγής στο C
Απαιτούμε πρώτα μια συλλογή στοιχείων που πρέπει να ταξινομηθούν σε φθίνουσα και αύξουσα σειρά για να δημιουργήσουμε τη μέθοδο ταξινόμησης εισαγωγής στο C. Ας υποθέσουμε για τους σκοπούς αυτού του παραδείγματος ότι έχουμε να κάνουμε με έναν πίνακα αριθμών {5, 4, 60, 9} :
#includeκενός insertionsort_ascending ( ενθ arr1 [ ] , ενθ n ) {
ενθ Εγώ , ι , το κλειδί μου ;
Ο βρόχος //for χρησιμοποιείται για την επανάληψη των τιμών i από το 1 στο i
Για ( Εγώ = 1 ; Εγώ < n ; Εγώ ++ ) {
το κλειδί μου = arr1 [ Εγώ ] ;
ι = Εγώ - 1 ;
ενώ ( ι >= 0 && arr1 [ ι ] > το κλειδί μου ) {
arr1 [ ι + 1 ] = arr1 [ ι ] ;
ι = ι - 1 ;
}
arr1 [ ι + 1 ] = το κλειδί μου ;
}
}
κενός insertionsort_decending ( ενθ arr2 [ ] , ενθ Μ ) {
ενθ Εγώ , ι , το κλειδί μου ;
Δημιουργείται //ένας άλλος βρόχος for για την επανάληψη των τιμών i από το 1 στο i
Για ( Εγώ = 1 ; Εγώ < Μ ; Εγώ ++ ) {
το κλειδί μου = arr2 [ Εγώ ] ;
ι = Εγώ - 1 ;
ενώ ( ι >= 0 && arr2 [ ι ] < το κλειδί μου ) {
arr2 [ ι + 1 ] = arr2 [ ι ] ;
ι = ι - 1 ;
}
arr2 [ ι + 1 ] = το κλειδί μου ;
}
}
ενθ κύριος ( ) {
//Εισαγωγή-Ταξινόμηση με φθίνουσα σειρά
ενθ my_arr [ ] = { 5 , 4 , 60 , 9 } ; //αρχικοποιήστε ένα my_arr[] που έχει τέσσερις τιμές
ενθ Μ = μέγεθος του ( my_arr ) / μέγεθος του ( my_arr [ 0 ] ) ;
insertionsort_decending ( my_arr , Μ ) ;
printf ( 'Ταξινομημένος πίνακας με φθίνουσα σειρά: ' ) ;
Για ( ενθ Εγώ = 0 ; Εγώ < Μ ; Εγώ ++ )
printf ( '%d' , my_arr [ Εγώ ] ) ;
printf ( ' \n ' ) ;
//Εισαγωγή-Ταξινόμηση με αύξουσα σειρά
ενθ n = μέγεθος του ( my_arr ) / μέγεθος του ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Ταξινομημένος πίνακας σε αύξουσα σειρά: ' ) ;
Για ( ενθ Εγώ = 0 ; Εγώ < n ; Εγώ ++ )
printf ( '%d' , my_arr [ Εγώ ] ) ;
printf ( ' \n ' ) ;
ΕΠΙΣΤΡΟΦΗ 0 ;
}
Σε αυτόν τον κώδικα, δύο μέθοδοι insertionsort_decending() , και insertionsort_ascending() πάρτε τις τιμές του πίνακα my_arr[] . Ο κώδικας χρησιμοποιεί στη συνέχεια a για βρόχο για επανάληψη μέσω των στοιχείων του πίνακα.
Καλούμε και τις δύο συναρτήσεις στην κύρια συνάρτηση αφού έχουν ταξινομήσει τους πίνακες σε φθίνουσα και αύξουσα σειρά. Μετά από αυτό, οι βρόχοι for χρησιμοποιούνται για την εκτύπωση του ταξινομημένου πίνακα.
Όταν εκτελούμε αυτό το πρόγραμμα, η αναμενόμενη έξοδος τοποθετείται παρακάτω:
συμπέρασμα
Η ταξινόμηση εισαγωγής είναι ένας γρήγορος και εύκολος τρόπος για να ταξινομήσετε έναν πίνακα είτε με φθίνουσα είτε με αύξουσα σειρά. Για μικρά σύνολα δεδομένων, αυτή η τεχνική ταξινόμησης αποδίδει καλά. Όπως μπορείτε να δείτε στον παραπάνω οδηγό, είναι απλό να εφαρμόσετε ένα παράδειγμα προγράμματος C για να κατανοήσετε εύκολα την ταξινόμηση εισαγωγής σε φθίνουσα αλλά και σε αύξουσα σειρά.