Μενού

Επιλογή Ταξινόμηση σε C ++ με παραδείγματα

selection sort c with examples

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

Μια ματιά σε βάθος επιλογής Ταξινόμηση σε C ++ με παραδείγματα.

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

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

=> Ανατρέξτε στον τέλειο οδηγό εκπαίδευσης C ++ εδώ.

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

Τι θα μάθετε:

Εισαγωγή

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

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

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

Γενικός αλγόριθμος

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

python selenium find element by text

Ταξινόμηση επιλογής (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 : (αρχικοποίηση) σύνολο μικρότεροElem = A (K)
  • Βήμα 2 : (αρχικοποίηση) ορίστε POS = K
  • Βήμα 3 : για J = K + 1 έως N -1, επαναλάβετε
    αν είναι μικρότερο> E (J)
    σετ μικρότεροElem = A (J)
    ορίστε POS = J
    (αν τελειώσει)
    (Τέλος βρόχου)
  • Βήμα 4 : επιστροφή POS

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

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)

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

Απεικόνιση

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

Πέρασμα2

Πέρασμα3

Πέρασμα4

Η αναπαράσταση πίνακα για αυτήν την εικόνα φαίνεται παρακάτω:

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

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

Δίνεται παρακάτω η εφαρμογή αλγορίθμου ταξινόμησης επιλογής στο C ++.

Παράδειγμα C ++

#include using namespace std; int findSmallest (int(),int); int main () { int myarray(10) = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<' Input list of elements to be Sorted '; for(int i=0;i<10;i++) { cout<

Παραγωγή:

Λίστα εισαγωγής στοιχείων προς ταξινόμηση

11 5 2 20 42 53 23 34 101 22

Η ταξινομημένη λίστα στοιχείων είναι

2 5 11 20 22 23 34 42 53 101

Αριθμός περάσεων που απαιτούνται για την ταξινόμηση του πίνακα: 10

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

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

Παράδειγμα Java

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

class Main { public static void main(String() args) { int() a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println(' Input list to be sorted... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a(i); a(i)=a(pos); a(pos) = temp; } System.out.println(' printing sorted elements... '); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } } public static int findSmallest(int a(),int i) { int smallest,position,j; smallest = a(i); position = i; for(j=i+1;j<10;j++) { if(a(j)

Παραγωγή:

Λίστα εισαγωγής προς ταξινόμηση…

11 5 2 20 42 53 23 34 101 22

εκτύπωση ταξινομημένων στοιχείων…

2 5 11 20 22 23 34 42 53 101

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

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

Ανάλυση πολυπλοκότητας ταξινόμησης επιλογής

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

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

Χειρότερη περίπτωση πολυπλοκότηταςO( n 2 ) ; O(n) swaps
Βέλτιστη πολυπλοκότητα χρόνουO( n 2 ) ; O(n) swaps
Μέσος χρόνος πολυπλοκότηταςO( n 2 ) ; O(n) swaps
Διαστημική πολυπλοκότηταΟ (1)

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

συμπέρασμα

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

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

Σε αυτό το σεμινάριο, συζητήσαμε λεπτομερώς το είδος επιλογής, συμπεριλαμβανομένης της εφαρμογής του είδους επιλογής χρησιμοποιώντας γλώσσες C ++ και Java. Η λογική πίσω από το είδος επιλογής είναι να βρείτε το μικρότερο στοιχείο στη λίστα επανειλημμένα και να το τοποθετήσετε στη σωστή θέση.

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

=> Δείτε εδώ για να δείτε τα εκπαιδευτικά μαθήματα A-Z Of C ++ εδώ.

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

^