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

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

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

Ταξινόμηση επιλογής: Μια πιο προσεκτική εμφάνιση

Ας υποθέσουμε ότι έχετε τη λίστα: [39, 82, 2, 51, 30, 42, 7]. Για να ταξινομήσετε τη λίστα χρησιμοποιώντας το είδος επιλογής, θα πρέπει πρώτα να βρείτε τον υψηλότερο αριθμό σε αυτήν.

Με τη δεδομένη λίστα, αυτός ο αριθμός είναι 82. Ανταλλάξτε 82 με τον αριθμό στον υψηλότερο δείκτη (δηλαδή, 7).

Μετά το πρώτο πέρασμα, η νέα σειρά λίστας θα είναι: [39, 7, 2, 51, 30, 42, 82]. Κάθε φορά που ο αλγόριθμος περνά ολόκληρη τη λίστα, αυτό ονομάζεται "πέρασμα".

Παρατηρήστε ότι η λίστα διατηρεί μια ταξινομημένη δευτερεύουσα λίστα και μια μη ταξινομημένη δευτερεύουσα λίστα κατά τη διαδικασία ταξινόμησης.

Σχετίζεται με: Τι είναι η σημείωση Big-O;

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

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

[39, 7, 2, 42, 30, 51, 82].

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

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

Ανάλυση αλγορίθμου

Για να αποκτήσετε την πολυπλοκότητα (χρησιμοποιώντας τη σημείωση Big-O) αυτού του αλγορίθμου, ακολουθήστε παρακάτω:

Στο πρώτο πέρασμα, γίνονται συγκρίσεις (n-1). Στο δεύτερο πέρασμα, (n-2). Στο τρίτο πέρασμα, (n-3) και ούτω καθεξής μέχρι το (n-1) th πέρασμα που κάνει μόνο μία σύγκριση.

Συνοψίζοντας τις συγκρίσεις όπως παρακάτω δίνεται:

(n-1) + (n-1) + (n-1) +... + 1 = ((n-1) n) / 2.

Επομένως, το είδος επιλογής είναι O (n²).

Εφαρμογή κώδικα

Ο κώδικας δείχνει συναρτήσεις που μπορείτε να χρησιμοποιήσετε για την εκτέλεση ταξινόμησης επιλογής χρησιμοποιώντας Python και Java

Πύθων:

def selectionSort (mylist):
για x σε εύρος (len (mylist) - 1, 0, -1):
max_idx = 0
για posn στο εύρος (1, x + 1):
αν mylist [posn]> mylist [max_idx]:
max_idx = θέση
temp = mylist [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = temp

Ιάβα:

Ακύρωση επιλογής Ταξινόμηση (int my_array []) { 
για (int x = 0; x { 
int index = x; 
για (int y = x + 1; y αν (my_array [y] δείκτης = y; // βρείτε τον χαμηλότερο δείκτη 
} 
} 
int temp = my_array [ευρετήριο]; // temp είναι προσωρινή αποθήκευση
my_array [index] = my_array [x]; 
my_array [x] = temp; 
}}

Μετακίνηση από επιλογή ταξινόμησης σε συγχώνευση ταξινόμησης

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

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

Σχετικά με τον Συγγραφέα