Αλγόριθμος ταξινόμησης εισαγωγής σε Java με Παράδειγμα Προγράμματος
Τζέιμς Χάρτμαν
⚡ Έξυπνη Σύνοψη
Εισαγωγή ταξινόμησης σε Java Δημιουργεί ένα ταξινομημένο τμήμα ενός πίνακα, ένα στοιχείο τη φορά, μετατοπίζοντας τις μεγαλύτερες τιμές προς τα δεξιά μέχρι κάθε κλειδί να καταλήξει στη σωστή του θέση, καθιστώντας το ιδανικό για μικρά σύνολα δεδομένων.
Τι είναι ο αλγόριθμος ταξινόμησης εισαγωγής;
Η ταξινόμηση εισαγωγής είναι ένας απλός αλγόριθμος ταξινόμησης κατάλληλος για μικρά σύνολα δεδομένων. Κατά τη διάρκεια κάθε επανάληψης, ο αλγόριθμος:
- Αφαιρεί ένα στοιχείο από έναν πίνακα.
- Το συγκρίνει με τη μεγαλύτερη τιμή στο παράταξη.
- Μετακινεί το στοιχείο στη σωστή του θέση.
Η συμπεριφορά αυτή αντικατοπτρίζει τον τρόπο με τον οποίο ένας παίκτης χαρτιών οργανώνει ένα χέρι: κάθε νέο φύλλο λαμβάνεται και σπρώχνεται αριστερά, περνώντας από κάθε μεγαλύτερο φύλλο, μέχρι να σταματήσει στο σωστό σημείο. Επειδή όλες οι μετακινήσεις συμβαίνουν μέσα στον αρχικό πίνακα, η ταξινόμηση με εισαγωγή είναι και στη θέση της και σταθερή.
Ανήκει στην ίδια οικογένεια φιλικών προς αρχάριους Java ρουτίνες ταξινόμησης ως τύπος φυσαλίδων, ωστόσο συνήθως εκτελεί πολύ λιγότερες εγγραφές σε δεδομένα που έχουν ήδη παραγγελθεί εν μέρει.
Διαδικασία αλγορίθμου ταξινόμησης εισαγωγής
Ακολουθεί ο τρόπος με τον οποίο λειτουργεί γραφικά η διαδικασία αλγόριθμου ταξινόμησης Εισαγωγή:
Η κινούμενη εικόνα επαναλαμβάνει τα ίδια τρία βήματα Java εκτελείται το παρακάτω πρόγραμμα. Ο πίνακας ξηρής λειτουργίας tracΕκτελεί αυτά τα βήματα στον πίνακα δειγμάτων {860, 8, 200, 9}, ακριβώς όπως τα εκτυπώνει το πρόγραμμα κατά τον χρόνο εκτέλεσης.
| Πέρασμα | Βασικό στοιχείο | Συγκρίσεις που έγιναν | Πίνακας μετά το πέρασμα |
|---|---|---|---|
| 1 | 8 | 8 εναντίον 860 | 8 860 200 9 |
| 2 | 200 | 200 εναντίον 860 | 8 200 860 9 |
| 3 | 9 | 9 εναντίον 860, έπειτα 9 εναντίον 200 | 8 9 200 860 |
Παρατηρήστε ότι το πέρασμα 3 χρειάζεται δύο συγκρίσεις επειδή το κλειδί 9 πρέπει να περάσει από δύο μεγαλύτερες τιμές. Ο αριθμός των συγκρίσεων επομένως αυξάνεται ανάλογα με το πόσο μακριά ξεκινά η εκτός σειράς θέση κάθε στοιχείου.
Java Παράδειγμα προγράμματος για την ταξινόμηση ενός πίνακα χρησιμοποιώντας τον αλγόριθμο ταξινόμησης εισαγωγής:
Το παρακάτω πρόγραμμα ταξινομεί τον πίνακα {860, 8, 200, 9} και εκτυπώνει ένα τρέχον σχόλιο, έτσι ώστε κάθε σύγκριση και κάθε μετατόπιση να είναι ορατή. Αποθηκεύστε το ως InsertionSortExample.java και να το μεταγλωττίσετε με οποιαδήποτε έκδοση JDK 8 ή νεότερη.
package com.guru99; public class InsertionSortExample { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("Before Insertion Sort"); printArray(myArray); insertionSort(myArray);//sorting array using insertion sort System.out.println("After Insertion Sort"); printArray(myArray); } public static void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; i++) { System.out.println("Sort Pass Number "+(i)); int key = arr[i]; int j = i-1; while ( (j > -1) && ( arr [j] > key ) ) { System.out.println("Comparing "+ key + " and " + arr [j]); arr [j+1] = arr [j]; j--; } arr[j+1] = key; System.out.println("Swapping Elements: New Array After Swap"); printArray(arr); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Η εκτέλεση της τάξης παράγει το tracεμφανίζεται εδώ. Κάθε Αριθμός Ταξινόμησης Κάρτας Η γραμμή σηματοδοτεί μια επανάληψη του εξωτερικού βρόχου και η γραμμή που εκτυπώνεται μετά από κάθε εναλλαγή δείχνει τον πίνακα όπως βρίσκεται εκείνη τη στιγμή.
Code Παραγωγή:
Before Insertion Sort 860 8 200 9 Sort Pass Number 1 Comparing 8 and 860 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 200 860 9 Sort Pass Number 3 Comparing 9 and 860 Comparing 9 and 200 Swapping Elements: New Array After Swap 8 9 200 860 After Insertion Sort 8 9 200 860
Χρονική και χωρική πολυπλοκότητα της ταξινόμησης με εισαγωγή
Η απόδοση της ταξινόμησης με εισαγωγή εξαρτάται σε μεγάλο βαθμό από την ήδη ταξινομημένη σειρά των δεδομένων εισόδου, γι' αυτό και η καλύτερη και η χειρότερη περίπτωση διαφέρουν κατά μια ολόκληρη τάξη ανάπτυξης.
| Περίπτωση | Συνθήκη εισόδου | Χρονική πολυπλοκότητα |
|---|---|---|
| καλυτερα | Ο πίνακας είναι ήδη ταξινομημένος, επομένως ο εσωτερικός βρόχος while δεν εκτελείται ποτέ | O (n) |
| Μέτρια | Τα στοιχεία φτάνουν με τυχαία σειρά | O(n²) |
| χειρότερη | Ο πίνακας ταξινομείται αντίστροφα, έτσι ώστε κάθε πλήκτρο να μετακινείται προς τα εμπρός | O(n²) |
Η χρήση του χώρου είναι πολύ πιο απλή. Μόνο οι πάγκοι i, j, n και key δημιουργούνται και ο πίνακας αναδιατάσσεται στη θέση του, επομένως ο βοηθητικός χώρος είναι O(1) ανεξάρτητα από το πόσο μεγάλη μεγαλώνει η είσοδος.
Επειδή ο εσωτερικός βρόχος σταματά μόλις συναντήσει μια μικρότερη τιμή, η ταξινόμηση με εισαγωγή περιγράφεται ως προσαρμοστική: όσο πιο κοντά στην ταξινομημένη σειρά είναι η είσοδος, τόσο πιο κοντά κινείται ο χρόνος εκτέλεσης προς τη γραμμική.
Πλεονεκτήματα και μειονεκτήματα της ταξινόμησης με εισαγωγή
Η ταξινόμηση με εισαγωγή επιβιώνει στις βιβλιοθήκες παραγωγής παρά την περίπτωση του τετραγωνικού μέσου όρου, επειδή οι σταθεροί παράγοντες της είναι μικροσκοπικοί και η συμπεριφορά της είναι προβλέψιμη.
Πλεονεκτήματα
- Απλό στη γραφή και εύκολο στη χρήση tracμε το χέρι, κάτι που το καθιστά κατάλληλο για διδασκαλία και συνεντεύξεις.
- Σταθερό, επομένως οι εγγραφές που μοιράζονται ένα κλειδί διατηρούν την αρχική τους σχετική σειρά.
- Επί τόπου, χρειάζεται μόνο O(1) επιπλέον μνήμη πέρα από τον πίνακα εισόδου.
- Προσαρμοστικό, φτάνοντας στο O(n) σε δεδομένα που είναι ήδη σχεδόν ταξινομημένα.
- Διαδικτυακά, που σημαίνει ότι μπορεί να ταξινομήσει μια λίστα ενώ εξακολουθούν να φτάνουν νέα στοιχεία.
Μειονεκτήματα
- Ο τετραγωνικός χρόνος σε τυχαία ή αντίστροφα ταξινομημένη είσοδο το καθιστά ακατάλληλο για μεγάλους πίνακες.
- Κάθε μετατόπιση γράφει στον πίνακα, επομένως μετακινεί περισσότερα δεδομένα από ό,τι η ταξινόμηση με επιλογή.
- Η συγχώνευση ταξινόμησης και η γρήγορη ταξινόμηση την ξεπερνούν άνετα μόλις η είσοδος περάσει μερικές δεκάδες στοιχεία.
Ένας πρακτικός κανόνας είναι να επιλέγουμε την ταξινόμηση με εισαγωγή όταν ο πίνακας είναι μικρός, όταν τα δεδομένα είναι σχεδόν σε τάξη ή όταν μια ταξινόμηση διαίρει και βασίλευε έχει μειώσει μια διαμέριση σε μια χούφτα στοιχείων.
Ταξινόμηση με Εισαγωγή vs. BubblΤαξινόμηση μέσω ηλεκτρονικής ταξινόμησης έναντι ταξινόμησης επιλογής
Και οι τρεις αλγόριθμοι είναι τετραγωνικές συγκριτικές ταξινομήσεις, ωστόσο διαφέρουν ως προς τη σταθερότητα, τον τρόπο που αντιδρούν σε διατεταγμένα δεδομένα εισόδου και τον αριθμό των εγγραφών που εκτελούν.
| Κριτήρια | Ταξινόμηση εισαγωγής | Bubble Ταξινόμηση | Ταξινόμηση επιλογής |
|---|---|---|---|
| καλυτερα case | O (n) | O(n) με σημαία πρόωρης εξόδου | O(n²) |
| Μέση και χειρότερη περίπτωση | O(n²) | O(n²) | O(n²) |
| Επιπλέον χώρος | Ο (1) | Ο (1) | Ο (1) |
| Σταθερός | Ναι | Ναι | Όχι, στην τυπική έκδοση πίνακα |
| Adaptive | Ναι | Ναι, όταν χρησιμοποιείται η βελτιστοποίηση σημαίας | Οχι |
| Γράφει στον πίνακα | Πολλές βάρδιες, λίγες σε ταξινομημένα δεδομένα | Πολλές ανταλλαγές | Ακριβώς n-1 ανταλλαγές |
Η ταξινόμηση με επιλογή κερδίζει όταν μια εγγραφή είναι ακριβή, επειδή εκτελεί τις λιγότερες ανταλλαγές. Η ταξινόμηση με εισαγωγή κερδίζει σχεδόν παντού αλλού σε αυτήν την κλίμακα, ειδικά σε μερικώς ταξινομημένα δεδομένα, γι' αυτό και οι ταξινομήσεις βιβλιοθήκης όπως αυτή που ακολουθεί κοινός Java ασκήσεις και τα εσωτερικά του JDK μεταβαίνουν σε αυτό για πολύ μικρά διαμερίσματα.
