Μενού

Ταξινόμηση εισαγωγής σε Java - Αλγόριθμος ταξινόμησης εισαγωγής και παραδείγματα

  • Κύριος
  • Αλλα
  • Ταξινόμηση εισαγωγής σε Java - Αλγόριθμος ταξινόμησης εισαγωγής και παραδείγματα

insertion sort java insertion sort algorithm examples

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Αυτό το σεμινάριο εξηγεί την ταξινόμηση εισαγωγής στην Java, συμπεριλαμβανομένων του αλγορίθμου, του ψευδοκώδικα και παραδειγμάτων συστοιχιών ταξινόμησης, λίστας μεμονωμένων συνδέσεων και διπλής σύνδεσης:

Η τεχνική Insertion Sort Algorithm είναι παρόμοια με το Bubble sort αλλά είναι ελαφρώς πιο αποτελεσματική. Το είδος εισαγωγής είναι πιο εφικτό και αποτελεσματικό όταν εμπλέκεται ένας μικρός αριθμός στοιχείων. Όταν το σύνολο δεδομένων είναι μεγαλύτερο, θα χρειαστεί περισσότερος χρόνος για την ταξινόμηση των δεδομένων.

=> Ρίξτε μια ματιά στον οδηγό για αρχάριους Java εδώ.

ομαδική διαχείριση διακομιστή ευέλικτων έργων

Ταξινόμηση εισαγωγής σε Java

Τι θα μάθετε:

Εισαγωγή στην ταξινόμηση εισαγωγής στην Java

Στην τεχνική εισαγωγής εισαγωγής, υποθέτουμε ότι το πρώτο στοιχείο στη λίστα έχει ήδη ταξινομηθεί και ξεκινάμε με το δεύτερο στοιχείο. Το δεύτερο στοιχείο συγκρίνεται με το πρώτο και ανταλλάσσεται αν όχι στη σειρά. Αυτή η διαδικασία επαναλαμβάνεται για όλα τα επόμενα στοιχεία.

Σε γενικές γραμμές, η τεχνική εισαγωγής συγκρίνει κάθε στοιχείο με όλα τα προηγούμενα στοιχεία του και ταξινομεί το στοιχείο για να το τοποθετήσει στη σωστή του θέση.

Όπως προαναφέρθηκε, η τεχνική εισαγωγής εισαγωγής είναι πιο εφικτή για ένα μικρότερο σύνολο δεδομένων, και έτσι οι πίνακες με μικρό αριθμό στοιχείων μπορούν να ταξινομηθούν χρησιμοποιώντας αποτελεσματικά το είδος εισαγωγής.

Η ταξινόμηση εισαγωγής είναι ιδιαίτερα χρήσιμη για την ταξινόμηση δομών δεδομένων συνδεδεμένων λιστών. Όπως γνωρίζετε, οι Συνδεδεμένες λίστες έχουν δείκτες που δείχνουν το επόμενο στοιχείο του (λίστα συνδεδεμένων μεμονωμένων) και το προηγούμενο στοιχείο (λίστα με διπλούς συνδέσμους). Αυτό διευκολύνει την παρακολούθηση των προηγούμενων και των επόμενων στοιχείων.

Έτσι, είναι ευκολότερο να χρησιμοποιήσετε το είδος Εισαγωγής για ταξινόμηση συνδεδεμένων λιστών. Ωστόσο, η ταξινόμηση θα διαρκέσει πολύ χρόνο εάν τα στοιχεία δεδομένων είναι περισσότερα.

Σε αυτό το σεμινάριο, θα συζητήσουμε την τεχνική ταξινόμησης εισαγωγής, συμπεριλαμβανομένου του αλγορίθμου, ψευδοκώδικα και παραδειγμάτων. Θα εφαρμόσουμε επίσης προγράμματα 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 while freePosition > 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

Στη συνέχεια, ας δούμε μια εικόνα που δείχνει την ταξινόμηση ενός πίνακα χρησιμοποιώντας το είδος Εισαγωγής.

Ταξινόμηση μιας σειράς με χρήση Ταξινόμησης εισαγωγής

Ας πάρουμε ένα παράδειγμα ταξινόμησης εισαγωγής χρησιμοποιώντας έναν πίνακα.

Ο πίνακας που θα ταξινομηθεί έχει ως εξής:

πίνακας προς ταξινόμηση

Τώρα για κάθε πάσο, συγκρίνουμε το τρέχον στοιχείο με όλα τα προηγούμενα στοιχεία του. Έτσι στο πρώτο πέρασμα, ξεκινάμε με το δεύτερο στοιχείο.

Συγκρίνετε το 2ο στοιχείο με το 1ο στοιχείο

πέρασμα 2

πέρασμα 3

πέρασμα 4

πέρασμα 5

πέρασμα 6

Επομένως, απαιτούμε τον αριθμό Ν περάσεων για να ταξινομήσουμε εντελώς έναν πίνακα που περιέχει Ν αριθμό στοιχείων.

ποιο βοηθητικό πρόγραμμα μπορεί να χρησιμοποιηθεί για την παρακολούθηση αναλυτικών πληροφοριών από τον ιστότοπο μιας εταιρείας;

Η παραπάνω εικόνα μπορεί να συνοψιστεί σε μορφή πίνακα όπως φαίνεται παρακάτω:

ΠέρασμαΜη ταξινομημένη λίστασύγκρισηΤαξινομημένη λίστα
1{10,2,6,15,4,1}{10.2}{2,10, 6,15,4,1}
δύο{2,10, 6,15,4,1}{2,10, 6}{2,6,10,15,4,1}
3{2,6,10,15,4,1}{2.6, 10.15}{2,6,10,15,4,1}
4{2,6,10,15,4,1}{2.6, 10.15.4}{2,4,6,10,15,1}
5{2,4,6,10,15,1}{2,4,6,10,15,1}{1,2,4,6, 10,15}
6{}{}{1,2,4,6, 10,15}

Όπως φαίνεται στην παραπάνω εικόνα, στο τέλος κάθε περάσματος, ένα στοιχείο πηγαίνει στη σωστή του θέση. Ως εκ τούτου, γενικά, για να τοποθετήσουμε τα στοιχεία N στη σωστή τους θέση, χρειαζόμαστε περάσματα N-1.

Εφαρμογή ταξινόμησης εισαγωγής σε Java

Το ακόλουθο πρόγραμμα δείχνει την εφαρμογή του είδους Εισαγωγή στην Java. Εδώ, έχουμε έναν πίνακα που θα ταξινομηθεί χρησιμοποιώντας το είδος Εισαγωγής.

import java.util.*; public class Main { public static void main(String() args) { //declare an array and print the original contents int() numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray(j)) { numArray(j+1) = numArray(j); j = j-1; } numArray(j+1) = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } }

Παραγωγή:

Πρωτότυπη σειρά: (10, 6, 15, 4, 1, 45)
Ταξινομημένη σειρά: (1, 4, 6, 10, 15, 45)

Υλοποίηση Ταξινόμησης Εισαγωγής - Εξόδου

Στην παραπάνω εφαρμογή, φαίνεται ότι η ταξινόμηση ξεκινά από το 2αρστοιχείο του πίνακα (μεταβλητή βρόχου j = 1) και στη συνέχεια το τρέχον στοιχείο συγκρίνεται με όλα τα προηγούμενα στοιχεία του. Το στοιχείο τοποθετείται στη συνέχεια στη σωστή του θέση.

Η ταξινόμηση εισαγωγής λειτουργεί αποτελεσματικά για μικρότερους πίνακες και για πίνακες που ταξινομούνται μερικώς όπου η ταξινόμηση ολοκληρώνεται σε λιγότερα περάσματα.

Το είδος εισαγωγής είναι ένα σταθερό είδος, δηλαδή διατηρεί τη σειρά των ίσων στοιχείων στη λίστα.

Ταξινόμηση μιας συνδεδεμένης λίστας με χρήση Ταξινόμησης εισαγωγής

Το ακόλουθο πρόγραμμα Java δείχνει την ταξινόμηση μιας λίστας μεμονωμένης σύνδεσης χρησιμοποιώντας το είδος Εισαγωγής.

import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val

Παραγωγή:

Αρχική συνδεδεμένη λίστα:
1 8 32 2 10
Ταξινομημένη συνδεδεμένη λίστα:
1 2 8 10 32

έξοδος - Συνδεδεμένη λίστα

Στο παραπάνω πρόγραμμα, έχουμε ορίσει μια κλάση που δημιουργεί μια συνδεδεμένη λίστα και προσθέτει κόμβους σε αυτήν καθώς και την ταξινομεί. Επειδή η λίστα με έναν μόνο σύνδεσμο έχει έναν επόμενο δείκτη, είναι ευκολότερο να παρακολουθείτε τους κόμβους κατά την ταξινόμηση της λίστας.

Ταξινόμηση λίστας διπλής σύνδεσης με χρήση Ταξινόμησης εισαγωγής

Το ακόλουθο πρόγραμμα ταξινομεί μια λίστα διπλά συνδεδεμένη χρησιμοποιώντας το είδος Εισαγωγής. Λάβετε υπόψη ότι καθώς η λίστα διπλά συνδεδεμένων έχει προηγούμενους και επόμενους δείκτες, είναι εύκολο να ενημερώσετε και να επανασυνδέσετε τους δείκτες κατά την ταξινόμηση των δεδομένων.

πώς μπορώ να ανοίξω ένα αρχείο βάζου
class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args()) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println(' Sorted Doubly Linked List:'); print_DLL(head); } }

Παραγωγή:

Αρχική λίστα διπλά συνδεδεμένων:
1 11 2 7 3 5
Ταξινόμηση διπλής συνδεδεμένης λίστας:
1 2 3 5 7 11

Έξοδος - Διπλά συνδεδεμένη λίστα

Συχνές Ερωτήσεις

Q # 1) Τι είναι η Ταξινόμηση εισαγωγής στην Java;

Απάντηση: Η ταξινόμηση εισαγωγής είναι μια απλή τεχνική ταξινόμησης στην Java που είναι αποτελεσματική για ένα μικρότερο σύνολο δεδομένων και στη θέση του. Υποτίθεται ότι το πρώτο στοιχείο ταξινομείται πάντα και στη συνέχεια κάθε επόμενο στοιχείο συγκρίνεται με όλα τα προηγούμενα στοιχεία του και τοποθετείται στη σωστή του θέση.

Q # 2) Γιατί είναι καλύτερη η Ταξινόμηση εισαγωγής;

Απάντηση: Η ταξινόμηση εισαγωγής είναι ταχύτερη για μικρότερα σύνολα δεδομένων όταν οι άλλες τεχνικές όπως η γρήγορη ταξινόμηση προσθέτουν γενικά μέσω επαναλαμβανόμενων κλήσεων. Η ταξινόμηση εισαγωγής είναι συγκριτικά πιο σταθερή από τους άλλους αλγόριθμους ταξινόμησης και απαιτεί λιγότερη μνήμη. Η ταξινόμηση εισαγωγής λειτουργεί επίσης πιο αποτελεσματικά όταν ο πίνακας έχει σχεδόν ταξινομηθεί.

Q # 3) Σε τι χρησιμοποιείται το Ταξινόμηση εισαγωγής;

Απάντηση: Το είδος εισαγωγής χρησιμοποιείται κυρίως σε εφαρμογές υπολογιστών που δημιουργούν σύνθετα προγράμματα όπως αναζήτηση αρχείων, εύρεση διαδρομής και συμπίεση δεδομένων.

Q # 4)Ποια είναι η αποτελεσματικότητα του Insertion Sort;

Απάντηση: Το είδος εισαγωγής έχει μέση απόδοση περιπτώσεων O (n ^ 2). Η καλύτερη περίπτωση για ταξινόμηση εισαγωγής είναι όταν ο πίνακας έχει ήδη ταξινομηθεί και είναι O (n). Η χειρότερη απόδοση για το είδος εισαγωγής είναι και πάλι O (n ^ 2).

συμπέρασμα

Η ταξινόμηση εισαγωγής είναι μια απλή τεχνική ταξινόμησης που λειτουργεί σε πίνακες ή συνδεδεμένες λίστες. Είναι χρήσιμο όταν το σύνολο δεδομένων είναι μικρότερο. Καθώς το σύνολο δεδομένων γίνεται μεγαλύτερο, αυτή η τεχνική γίνεται πιο αργή και αναποτελεσματική.

Το είδος εισαγωγής είναι επίσης πιο σταθερό και επιτόπου από τις άλλες τεχνικές ταξινόμησης. Δεν υπάρχει γενική μνήμη καθώς δεν χρησιμοποιείται ξεχωριστή δομή για την αποθήκευση ταξινομημένων στοιχείων.

Η ταξινόμηση εισαγωγής λειτουργεί καλά για την ταξινόμηση συνδεδεμένων λιστών που είναι και οι λίστες μεμονωμένα και διπλά συνδεδεμένα. Αυτό συμβαίνει επειδή η συνδεδεμένη λίστα αποτελείται από κόμβους που συνδέονται μέσω δεικτών. Ως εκ τούτου, η διαλογή κόμβων γίνεται ευκολότερη.

Στο επερχόμενο σεμινάριό μας, θα συζητήσουμε μια ακόμη τεχνική ταξινόμησης στην Java.

=> Διαβάστε ολόκληρη τη σειρά Easy Java Training.

Συνιστώμενη ανάγνωση

^