insertion sort c with examples
Μια ματιά στο βάθος κατά την εισαγωγή με κλασικά παραδείγματα.
Το είδος εισαγωγής είναι μια τεχνική ταξινόμησης που μπορεί να προβληθεί με τρόπο που παίζουμε χαρτιά στο χέρι. Ο τρόπος με τον οποίο εισάγουμε οποιαδήποτε κάρτα σε μια τράπουλα ή την αφαιρούμε, τα είδη εισαγωγής λειτουργούν με παρόμοιο τρόπο.
Η τεχνική εισαγωγής αλγορίθμου ταξινόμησης είναι πιο αποτελεσματική από τις τεχνικές ταξινόμησης Bubble και Selection, αλλά είναι λιγότερο αποτελεσματική από τις άλλες τεχνικές όπως η ταξινόμηση Quicksort και Merge.
=> Δείτε τα καλύτερα εκπαιδευτικά σεμινάρια C ++ εδώ.
Τι θα μάθετε:
- ΣΦΑΙΡΙΚΗ ΕΙΚΟΝΑ
- Γενικός αλγόριθμος
- Ψευδοκώδικας
- Απεικόνιση
- Παράδειγμα C ++
- Παράδειγμα Java
- Ανάλυση πολυπλοκότητας του αλγόριθμου ταξινόμησης εισαγωγής
- συμπέρασμα
- Συνιστώμενη ανάγνωση
ΣΦΑΙΡΙΚΗ ΕΙΚΟΝΑ
Στην τεχνική ταξινόμησης εισαγωγής, ξεκινάμε από το δεύτερο στοιχείο και το συγκρίνουμε με το πρώτο στοιχείο και το βάζουμε σε σωστό μέρος. Στη συνέχεια, εκτελούμε αυτήν τη διαδικασία για τα επόμενα στοιχεία.
Συγκρίνουμε κάθε στοιχείο με όλα τα προηγούμενα στοιχεία του και βάζουμε ή εισάγουμε το στοιχείο στη σωστή του θέση. Η τεχνική ταξινόμησης εισαγωγής είναι πιο εφικτή για συστοιχίες με μικρότερο αριθμό στοιχείων. Είναι επίσης χρήσιμο για την ταξινόμηση συνδεδεμένων λιστών.
τι είναι η αναντιστοιχία κλειδιού ασφαλείας δικτύου
Οι συνδεδεμένες λίστες έχουν δείκτη στο επόμενο στοιχείο (στην περίπτωση μίας μόνο συνδεδεμένης λίστας) και δείκτη και στο προηγούμενο στοιχείο (στην περίπτωση λίστας με διπλή σύνδεση). Ως εκ τούτου, γίνεται ευκολότερο να εφαρμοστεί είδος εισαγωγής για μια συνδεδεμένη λίστα.
Ας εξερευνήσουμε τα πάντα σχετικά με το είδος εισαγωγής σε αυτό το σεμινάριο.
Γενικός αλγόριθμος
Βήμα 1 : Επαναλάβετε τα βήματα 2 έως 5 για K = 1 έως N-1
Βήμα 2 : ορίστε temp = A (K)
Βήμα 3 : σετ J = K - 1
Βήμα 4 : Επαναλάβετε ενώ η θερμοκρασία<=A(J)
σύνολο A (J + 1) = A (J)
σύνολο J = J - 1
(τέλος εσωτερικού βρόχου)
Βήμα 5 : ορίστε A (J + 1) = temp
(τέλος βρόχου)
Βήμα 6 : έξοδος
Έτσι, στην τεχνική ταξινόμησης εισαγωγής, ξεκινάμε από το δεύτερο στοιχείο καθώς υποθέτουμε ότι το πρώτο στοιχείο είναι πάντα ταξινομημένο. Στη συνέχεια, από το δεύτερο στοιχείο στο τελευταίο στοιχείο, συγκρίνουμε κάθε στοιχείο με όλα τα προηγούμενα στοιχεία του και τοποθετούμε αυτό το στοιχείο στη σωστή θέση.
Ψευδοκώδικας
Ο ψευδοκώδικας για είδος εισαγωγής δίνεται παρακάτω.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedureΔίνεται παραπάνω είναι ο ψευδοκώδικας για το είδος Εισαγωγής, στη συνέχεια, θα παρουσιάσουμε αυτήν την τεχνική στο ακόλουθο παράδειγμα.
Απεικόνιση
Ο πίνακας που θα ταξινομηθεί έχει ως εξής:
Τώρα για κάθε πάσο, συγκρίνουμε το τρέχον στοιχείο με όλα τα προηγούμενα στοιχεία του. Έτσι στο πρώτο πέρασμα, ξεκινάμε με το δεύτερο στοιχείο.
Συνεπώς, απαιτούμε τον αριθμό Ν περάσεων για να ταξινομήσουμε πλήρως έναν πίνακα που περιέχει αριθμό N στοιχείων.
Η παραπάνω εικόνα μπορεί να συνοψιστεί σε μορφή πίνακα:
| Πέρασμα | Μη ταξινομημένη λίστα | σύγκριση | Ταξινομημένη λίστα |
|---|---|---|---|
| ένας | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| δύο | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 3 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
Όπως φαίνεται στην παραπάνω εικόνα, ξεκινάμε με το 2αρδεδομένου ότι υποθέτουμε ότι το πρώτο στοιχείο είναι πάντα ταξινομημένο. Αρχίζουμε λοιπόν να συγκρίνουμε το δεύτερο στοιχείο με το πρώτο και να αλλάζουμε τη θέση εάν το δεύτερο στοιχείο είναι μικρότερο από το πρώτο.
πώς να εκτελέσετε αρχεία .jar
Αυτή η διαδικασία σύγκρισης και ανταλλαγής τοποθετεί δύο στοιχεία στις κατάλληλες θέσεις τους. Στη συνέχεια, συγκρίνουμε το τρίτο στοιχείο με τα προηγούμενα (πρώτο και δεύτερο) στοιχεία και εκτελούμε την ίδια διαδικασία για να τοποθετήσουμε το τρίτο στοιχείο στη σωστή θέση.
Με αυτόν τον τρόπο, για κάθε πάσο, τοποθετούμε ένα στοιχείο στη θέση του. Για το πρώτο πέρασμα, τοποθετούμε το δεύτερο στοιχείο στη θέση του. Έτσι, γενικά, για να τοποθετήσουμε τα στοιχεία N στη σωστή τους θέση, χρειαζόμαστε περάσματα N-1.
Στη συνέχεια, θα παρουσιάσουμε την εφαρμογή τεχνικής ταξινόμησης εισαγωγής σε γλώσσα C ++.
Παράδειγμα C ++
#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < Παραγωγή:
Η λίστα εισαγωγής είναι
12 4 3 1 15 45 33 21 10 2
Η ταξινομημένη λίστα είναι
1 2 3 4 10 12 15 21 33 45
Στη συνέχεια, θα δούμε την εφαρμογή Java της τεχνικής ταξινόμησης εισαγωγής.
Παράδειγμα Java
public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } } Παραγωγή:
προσθήκη στοιχείου στο παράδειγμα java
Λίστα εισόδου στοιχείων…
12 4 3 1 15 45 33 21 10 2
ταξινομημένη λίστα στοιχείων…
1 2 3 4 10 12 15 21 33 45
Και στις δύο εφαρμογές, μπορούμε να δούμε ότι ξεκινάμε την ταξινόμηση από το 2αρστοιχείο του πίνακα (μεταβλητή βρόχου j = 1) και συγκρίνει επανειλημμένα το τρέχον στοιχείο με όλα τα προηγούμενα στοιχεία του και, στη συνέχεια, ταξινομήστε το στοιχείο για να το τοποθετήσετε στη σωστή του θέση, εάν το τρέχον στοιχείο δεν είναι σε τάξη με όλα τα προηγούμενα στοιχεία του.
Η ταξινόμηση εισαγωγής λειτουργεί καλύτερα και μπορεί να ολοκληρωθεί σε λιγότερα περάσματα εάν ο πίνακας έχει μερικώς ταξινομηθεί. Αλλά καθώς η λίστα μεγαλώνει, η απόδοσή της μειώνεται. Ένα άλλο πλεονέκτημα του είδους Insertion είναι ότι είναι ένα Stable είδος που σημαίνει ότι διατηρεί τη σειρά των ίσων στοιχείων στη λίστα.
Ανάλυση πολυπλοκότητας του αλγόριθμου ταξινόμησης εισαγωγής
Από τον ψευδο κώδικα και την παραπάνω εικόνα, το είδος εισαγωγής είναι ο αποτελεσματικός αλγόριθμος σε σύγκριση με το είδος φυσαλίδας ή το είδος επιλογής. Αντί να χρησιμοποιείται για βρόχους και τρέχουσες συνθήκες, χρησιμοποιεί βρόχο λίγου που δεν εκτελεί επιπλέον βήματα κατά την ταξινόμηση του πίνακα.
Ωστόσο, ακόμη και αν περάσουμε την ταξινομημένη συστοιχία στην τεχνική ταξινόμησης Εισαγωγής, θα συνεχίσει να εκτελεί το εξωτερικό για βρόχο απαιτώντας έτσι έναν αριθμό βημάτων για την ταξινόμηση ενός ήδη ταξινομημένου πίνακα. Αυτό κάνει την καλύτερη χρονική πολυπλοκότητα της εισαγωγής ταξινομήστε μια γραμμική συνάρτηση του Ν όπου Ν είναι ο αριθμός των στοιχείων στον πίνακα.
Έτσι δίδονται παρακάτω οι διάφορες πολυπλοκότητες για την τεχνική εισαγωγής:
Χειρότερη περίπτωση πολυπλοκότητας Ο (ν 2) Βέλτιστη πολυπλοκότητα χρόνου Επί) Μέσος χρόνος πολυπλοκότητας Ο (ν 2) Διαστημική πολυπλοκότητα Ο (1)
Παρά αυτές τις πολυπλοκότητες, μπορούμε ακόμα να συμπεράνουμε ότι το είδος εισαγωγής είναι ο πιο αποτελεσματικός αλγόριθμος σε σύγκριση με τις άλλες τεχνικές ταξινόμησης όπως Bubble sort και Selection sort.
συμπέρασμα
Το είδος εισαγωγής είναι το πιο αποτελεσματικό από τις τρεις τεχνικές που συζητήθηκαν μέχρι τώρα. Εδώ, υποθέτουμε ότι το πρώτο στοιχείο ταξινομείται και, στη συνέχεια, συγκρίνει επανειλημμένα κάθε στοιχείο με όλα τα προηγούμενα στοιχεία του και, στη συνέχεια, τοποθετεί το τρέχον στοιχείο στη σωστή του θέση στον πίνακα.
Σε αυτό το σεμινάριο, ενώ συζητάμε για το είδος της Εισαγωγής, παρατηρήσαμε ότι συγκρίνουμε τα στοιχεία χρησιμοποιώντας μια αύξηση 1 και επίσης είναι συνεχόμενα. Αυτό το χαρακτηριστικό έχει ως αποτέλεσμα να απαιτούνται περισσότερες κάρτες για τη λήψη της ταξινομημένης λίστας.
Στο επερχόμενο σεμινάριό μας, θα συζητήσουμε το “Shell sort”, το οποίο είναι μια βελτίωση σε σχέση με το είδος επιλογής.
Σε είδος κελύφους, εισάγουμε μια μεταβλητή γνωστή ως «αύξηση» ή «κενό» χρησιμοποιώντας την οποία διαιρούμε τη λίστα σε λίστες που περιέχουν μη συνεχόμενα στοιχεία που διαχωρίζουν. Η ταξινόμηση κελύφους απαιτεί λιγότερα περάσματα σε σύγκριση με την ταξινόμηση εισαγωγής και είναι επίσης ταχύτερη.
Στα μελλοντικά μας σεμινάρια, θα μάθουμε για δύο τεχνικές ταξινόμησης, 'Quicksort' και 'Mergesort' που χρησιμοποιούν τη στρατηγική 'Διαίρεση και κατάκτηση' για τη διαλογή λιστών δεδομένων.
=> Παρακολουθήστε τον εκπαιδευτικό οδηγό για αρχάριους C ++ εδώ.
Συνιστώμενη ανάγνωση
- Ταξινόμηση κελύφους σε C ++ με παραδείγματα
- Επιλογή Ταξινόμηση σε C ++ με παραδείγματα
- MongoDB Sort () Μέθοδος με παραδείγματα
- Unix Sort Command με Σύνταξη, Επιλογές και Παραδείγματα
- Ταξινόμηση Bubble σε C ++ με παραδείγματα
- Ταξινόμηση σωρού σε C ++ με παραδείγματα
- Συγχώνευση ταξινόμησης σε C ++ με παραδείγματα
- Γρήγορη ταξινόμηση σε C ++ με παραδείγματα