Μενού

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

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

selection sort java selection sort algorithm examples

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

Αυτό το σεμινάριο θα εξηγήσει τα πάντα για την επιλογή Ταξινόμηση σε Java μαζί με τον αλγόριθμο επιλογής ταξινόμησης, τον κώδικα Java, την εφαρμογή σε Java και Java Παραδείγματα:

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

=> Δείτε εδώ για να δείτε το A-Z Of Java Training Tutorials εδώ.

Ταξινόμηση επιλογής σε Java

Τι θα μάθετε:

Ταξινόμηση επιλογής σε Java

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

Δύο δευτερεύουσες συστοιχίες διατηρούνται για το είδος επιλογής:

  1. Ταξινομημένη δευτερεύουσα σειρά: Σε κάθε επανάληψη, το ελάχιστο στοιχείο βρίσκεται και τοποθετείται στη σωστή του θέση. Αυτή η δευτερεύουσα σειρά ταξινομείται.
  2. Μη ταξινομημένη δευτερεύουσα σειρά: Τα υπόλοιπα στοιχεία που δεν έχουν ταξινομηθεί.

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

Έτσι μπορούμε να πούμε ότι το είδος επιλογής δεν συνιστάται για μεγαλύτερες λίστες δεδομένων.

Αλγόριθμος επιλογής ταξινόμησης

Ο γενικός αλγόριθμος για ταξινόμηση επιλογής δίνεται παρακάτω:

Ταξινόμηση επιλογής (A, N)

Βήμα 1 : Επαναλάβετε τα βήματα 2 και 3 για K = 1 έως N-1

Βήμα 2 : Μικρότερη ρουτίνα κλήσεων (A, K, N, POS)

Βήμα 3 :

Ανταλλαγή A (K) με A (POS)
(Τέλος βρόχου)

Βήμα 4 : ΕΞΟΔΟΣ

Μικρότερη ρουτίνα (A, K, N, POS)

Βήμα 1 : (αρχικοποίηση) σύνολο μικρότερο στοιχείο = A (K)

Βήμα 2 : (αρχικοποίηση) ορίστε POS = K

Βήμα 3 :

για J = K + 1 έως N -1, επαναλάβετε
αν το μικρότερο στοιχείο> A (J)
ορίστε το μικρότερο στοιχείο = A (J)
ορίστε POS = J
(αν τελειώσει)
(Τέλος βρόχου)

Βήμα 4 : επιστροφή POS

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

το καλύτερο μέρος για να παρακολουθήσετε μεταγλωττισμένο anime δωρεάν

Ψευδοκώδικας για επιλογή ταξινόμησης

Ο ψευδοκωδικός για τον αλγόριθμο επιλογής δίνεται παρακάτω.

Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j)

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

Παράδειγμα ταξινόμησης επιλογής

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

Παράδειγμα ταξινόμησης επιλογής

Περάστε 1

Πέρασμα 2

Περάστε 3

Περάστε 4

Δίνεται παρακάτω μια αναπαράσταση πίνακα για την εικόνα:

Μη ταξινομημένη λίσταΛιγότερο στοιχείοΤαξινομημένη λίστα
{17,10,7,29,2}δύο{}
{17,10,7,29}7{δύο}
{17,10,29}10{2.7}
{17.29}17{2,7,10)
{29}29{2,7,10,17}
{}{2,7,10,17,29}

Από την εικόνα, βλέπουμε ότι με κάθε πέρασμα το επόμενο μικρότερο στοιχείο τοποθετείται στη σωστή του θέση στον ταξινομημένο πίνακα. Γενικά, για να ταξινομήσουμε μια σειρά στοιχείων N, χρειαζόμαστε συνολικά περάσματα N-1.

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

Ας δείξουμε τώρα το πρόγραμμα Java για την εφαρμογή του είδους επιλογής.

import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i

Παραγωγή:

Original Array: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Ταξινομημένη σειρά: (2, 5, 7, 10, 15, 20, 23, 34, 42)

Έξοδος - Πρόγραμμα Java για εφαρμογή του είδους επιλογής

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

Επιλογή Ταξινόμηση συνδεδεμένης λίστας σε Java

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

Έτσι, εάν η συνδεδεμένη λίστα δίνεται ως εξής:

συνδεδεμένη λίστα

συνδεδεμένη λίστα - 2

Δίνεται παρακάτω το πρόγραμμα Java που εφαρμόζει την παραπάνω ταξινόμηση.

// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data

Παραγωγή:

c ++ απροσδιόριστο σφάλμα αναφοράς

Αρχική συνδεδεμένη λίστα:
7 9 3 5 1 11
Συνδεδεμένη λίστα μετά την ταξινόμηση:
1 3 5 7 9 11

Εφαρμογή Java Sort - Output

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

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

Ε # 1) Πώς λειτουργεί η επιλογή επιλογής;

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

Q # 2) Ποια είναι η πολυπλοκότητα του είδους Επιλογή;

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

Q # 3) Ποια είναι τα πλεονεκτήματα και τα μειονεκτήματα της επιλογής;

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

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

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

Q # 4) Πόσες ανταλλαγές υπάρχουν στο είδος επιλογής;

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

Ερ # 5) Είναι η ταξινόμηση επιλογής πιο γρήγορη από την ταξινόμηση εισαγωγής;

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

συμπέρασμα

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

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

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

=> Επισκεφθείτε εδώ για να δείτε τη σειρά εκπαίδευσης Java για όλους.

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

^