Τι είναι η επιλογή ταξινόμησης;
SELECTION SORT είναι ένας αλγόριθμος ταξινόμησης σύγκρισης που χρησιμοποιείται για την ταξινόμηση μιας τυχαίας λίστας στοιχείων με αύξουσα σειρά. Η σύγκριση δεν απαιτεί πολύ επιπλέον χώρο. Απαιτείται μόνο ένας επιπλέον χώρος μνήμης για τη χρονική μεταβλητή.
Αυτό είναι γνωστό ως τόπου διαλογή. Το είδος επιλογής έχει μια χρονική πολυπλοκότητα του O (n 2 ) όπου n είναι ο συνολικός αριθμός στοιχείων στη λίστα. Η πολυπλοκότητα του χρόνου μετρά τον αριθμό των επαναλήψεων που απαιτούνται για την ταξινόμηση της λίστας. Η λίστα χωρίζεται σε δύο κατατμήσεις: Η πρώτη λίστα περιέχει ταξινομημένα αντικείμενα, ενώ η δεύτερη λίστα περιέχει μη ταξινομημένα στοιχεία.
Από προεπιλογή, η ταξινομημένη λίστα είναι κενή και η μη ταξινομημένη λίστα περιέχει όλα τα στοιχεία. Στη συνέχεια, η λίστα χωρίς ταξινόμηση σαρώνεται για την ελάχιστη τιμή, η οποία στη συνέχεια τοποθετείται στη λίστα ταξινόμησης. Αυτή η διαδικασία επαναλαμβάνεται έως ότου συγκριθούν και ταξινομηθούν όλες οι τιμές.
Σε αυτό το σεμινάριο Αλγόριθμου, θα μάθετε:
- Τι είναι η επιλογή ταξινόμησης;
- Πώς λειτουργεί η επιλογή επιλογής;
- Ορισμός του προβλήματος
- Λύση (Αλγόριθμος)
- Οπτική αναπαράσταση
- Πρόγραμμα επιλογής ταξινόμησης χρησιμοποιώντας Python 3
- Επεξήγηση κώδικα
- Χρόνος πολυπλοκότητας της ταξινόμησης επιλογής
- Πότε να χρησιμοποιήσετε το είδος επιλογής;
- Πλεονεκτήματα της επιλογής Ταξινόμηση
- Μειονεκτήματα της επιλογής Ταξινόμηση
Πώς λειτουργεί η επιλογή επιλογής;
Το πρώτο στοιχείο στο μη ταξινομημένο διαμέρισμα συγκρίνεται με όλες τις τιμές στη δεξιά πλευρά για να ελέγξετε αν είναι η ελάχιστη τιμή. Εάν δεν είναι η ελάχιστη τιμή, τότε η θέση του ανταλλάσσεται με την ελάχιστη τιμή.
Παράδειγμα:
- Για παράδειγμα, εάν ο δείκτης της ελάχιστης τιμής είναι 3, τότε η τιμή του στοιχείου με το δείκτη 3 τοποθετείται στο ευρετήριο 0 ενώ η τιμή που ήταν στο ευρετήριο 0 τοποθετείται στον δείκτη 3. Εάν το πρώτο στοιχείο στο μη ταξινομημένο διαμέρισμα είναι την ελάχιστη τιμή, τότε επιστρέφει τις θέσεις της.
- Το στοιχείο που έχει καθοριστεί ως η ελάχιστη τιμή μετακινείται στη συνέχεια στο διαμέρισμα στην αριστερή πλευρά, που είναι η ταξινομημένη λίστα.
- Η διαχωρισμένη πλευρά έχει τώρα ένα στοιχείο, ενώ η μη διαχωρισμένη πλευρά έχει (n - 1) στοιχεία όπου n είναι ο συνολικός αριθμός στοιχείων στη λίστα. Αυτή η διαδικασία επαναλαμβάνεται ξανά και ξανά μέχρι να συγκριθούν και να ταξινομηθούν όλα τα στοιχεία με βάση τις τιμές τους.
Ορισμός του προβλήματος
Μια λίστα στοιχείων με τυχαία σειρά πρέπει να ταξινομηθεί σε αύξουσα σειρά. Εξετάστε την ακόλουθη λίστα ως παράδειγμα.
[21,6,9,33,3]
Η παραπάνω λίστα πρέπει να ταξινομηθεί για να παράγει τα ακόλουθα αποτελέσματα
[3,6,9,21,33]
Λύση (Αλγόριθμος)
Βήμα 1) Λάβετε την τιμή του n που είναι το συνολικό μέγεθος του πίνακα
Βήμα 2) Χωρίστε τη λίστα σε ταξινομημένες και μη ταξινομημένες ενότητες. Η ταξινομημένη ενότητα είναι αρχικά κενή, ενώ η μη ταξινομημένη ενότητα περιέχει ολόκληρη τη λίστα
Βήμα 3) Διαλέξτε την ελάχιστη τιμή από την μη διαχωρισμένη ενότητα και τοποθετήστε την στην ταξινομημένη ενότητα.
Βήμα 4) Επαναλάβετε τη διαδικασία (n - 1) φορές μέχρι να ταξινομηθούν όλα τα στοιχεία της λίστας.
Οπτική αναπαράσταση
Λαμβάνοντας υπόψη μια λίστα με πέντε στοιχεία, οι παρακάτω εικόνες απεικονίζουν τον τρόπο με τον οποίο ο αλγόριθμος ταξινόμησης επιλογής επαναλαμβάνεται μέσω των τιμών κατά την ταξινόμησή τους.
Η ακόλουθη εικόνα εμφανίζει τη μη ταξινομημένη λίστα
Βήμα 1)
Η πρώτη τιμή 21 συγκρίνεται με τις υπόλοιπες τιμές για να ελέγξει αν είναι η ελάχιστη τιμή.
3 είναι η ελάχιστη τιμή, επομένως οι θέσεις των 21 και 3 ανταλλάσσονται. Οι τιμές με πράσινο φόντο αντιπροσωπεύουν το ταξινομημένο διαμέρισμα της λίστας.
Βήμα 2)
Η τιμή 6 που είναι το πρώτο στοιχείο στο διαχωρισμένο διαμέρισμα συγκρίνεται με τις υπόλοιπες τιμές για να διαπιστωθεί εάν υπάρχει χαμηλότερη τιμή
Η τιμή 6 είναι η ελάχιστη τιμή, επομένως διατηρεί τη θέση της.
Βήμα 3)
Το πρώτο στοιχείο της μη ταξινομημένης λίστας με την τιμή 9 συγκρίνεται με τις υπόλοιπες τιμές για να ελέγξετε αν είναι η ελάχιστη τιμή.
Η τιμή 9 είναι η ελάχιστη τιμή, επομένως διατηρεί τη θέση της στο διαχωρισμένο διαμέρισμα.
Βήμα 4)
Η τιμή 33 συγκρίνεται με τις υπόλοιπες τιμές.
Η τιμή 21 είναι χαμηλότερη από 33, οπότε οι θέσεις εναλλάσσονται για να δημιουργήσουν την παραπάνω νέα λίστα.
Βήμα 5)
Απομένει μόνο μία τιμή στη λίστα χωρίς διαχωρισμό. Επομένως, είναι ήδη ταξινομημένο.
Η τελική λίστα είναι όπως αυτή που φαίνεται στην παραπάνω εικόνα.
Πρόγραμμα επιλογής ταξινόμησης χρησιμοποιώντας Python 3
Ο παρακάτω κώδικας δείχνει την εφαρμογή ταξινόμησης επιλογής χρησιμοποιώντας το Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))
Εκτελέστε τον παραπάνω κώδικα παράγει τα ακόλουθα αποτελέσματα
[3, 6, 9, 21, 33]
Επεξήγηση κώδικα
Η εξήγηση για τον κωδικό έχει ως εξής
Εδώ είναι η εξήγηση κώδικα:
- Ορίζει μια συνάρτηση που ονομάζεται selectionSort
- Παίρνει τον συνολικό αριθμό στοιχείων στη λίστα. Χρειαζόμαστε αυτό για να προσδιορίσουμε τον αριθμό των πάσων που πρέπει να γίνουν κατά τη σύγκριση των τιμών.
- Εξωτερικός βρόχος. Χρησιμοποιεί τον βρόχο για να επαναλάβει τις τιμές της λίστας. Ο αριθμός των επαναλήψεων είναι (n - 1). Η τιμή του n είναι 5, έτσι (5 - 1) μας δίνει 4. Αυτό σημαίνει ότι οι εξωτερικές επαναλήψεις θα εκτελεστούν 4 φορές. Σε κάθε επανάληψη, η τιμή της μεταβλητής i αντιστοιχεί στη μεταβλητή minValueIndex
- Εσωτερικός βρόχος. Χρησιμοποιεί το βρόχο για να συγκρίνει την αριστερότερη τιμή με τις άλλες τιμές στη δεξιά πλευρά. Ωστόσο, η τιμή για το j δεν ξεκινά στο ευρετήριο 0. Ξεκινά από (i + 1). Αυτό αποκλείει τις τιμές που έχουν ήδη ταξινομηθεί, ώστε να επικεντρωθούμε σε στοιχεία που δεν έχουν ταξινομηθεί ακόμη.
- Βρίσκει την ελάχιστη τιμή στη λίστα χωρίς ταξινόμηση και την τοποθετεί στη σωστή θέση
- Ενημερώνει την τιμή του minValueIndex όταν ισχύει η συνθήκη ανταλλαγής
- Συγκρίνει τις τιμές των αριθμών ευρετηρίου minValueIndex και i για να δούμε αν δεν είναι ίσες
- Η αριστερή τιμή αποθηκεύεται σε μια χρονική μεταβλητή
- Η χαμηλότερη τιμή από τη δεξιά πλευρά παίρνει την πρώτη θέση
- Η τιμή που αποθηκεύτηκε στη χρονική τιμή αποθηκεύεται στη θέση που διατηρούσε προηγουμένως από την ελάχιστη τιμή
- Επιστρέφει την ταξινομημένη λίστα ως αποτέλεσμα της συνάρτησης
- Δημιουργεί μια λίστα που έχει τυχαίους αριθμούς
- Εκτυπώστε τη ταξινομημένη λίστα αφού καλέσετε την επιλογή Ταξινόμηση που περνά στο el ως παράμετρος.
Χρόνος πολυπλοκότητας της ταξινόμησης επιλογής
Η πολυπλοκότητα ταξινόμησης χρησιμοποιείται για να εκφράσει τον αριθμό των χρόνων εκτέλεσης που απαιτείται για την ταξινόμηση της λίστας. Η εφαρμογή έχει δύο βρόχους.
Ο εξωτερικός βρόχος που επιλέγει τις τιμές μία προς μία από τη λίστα εκτελείται n φορές όπου n είναι ο συνολικός αριθμός τιμών στη λίστα.
Ο εσωτερικός βρόχος, ο οποίος συγκρίνει την τιμή από τον εξωτερικό βρόχο με τις υπόλοιπες τιμές, εκτελείται επίσης n φορές όπου το n είναι ο συνολικός αριθμός στοιχείων στη λίστα.
Επομένως, ο αριθμός των εκτελέσεων είναι (n * n), ο οποίος μπορεί επίσης να εκφραστεί ως O (n 2 ).
Το είδος επιλογής έχει τρεις κατηγορίες πολυπλοκότητας:
- Χειρότερη περίπτωση - εδώ είναι η λίστα που παρέχεται με φθίνουσα σειρά. Ο αλγόριθμος εκτελεί τον μέγιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-O] O (n 2 )
- Βέλτιστη περίπτωση - αυτό συμβαίνει όταν η παρεχόμενη λίστα έχει ήδη ταξινομηθεί. Ο αλγόριθμος εκτελεί τον ελάχιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-Omega] Ω (n 2 )
- Μέση περίπτωση - αυτό συμβαίνει όταν η λίστα είναι τυχαία. Η μέση πολυπλοκότητα εκφράζεται ως [Big-theta] ⊝ (n 2 )
Το είδος επιλογής έχει μια πολυπλοκότητα διαστήματος του O (1) καθώς απαιτεί μια χρονική μεταβλητή που χρησιμοποιείται για την ανταλλαγή τιμών.
Πότε να χρησιμοποιήσετε το είδος επιλογής;
Το είδος επιλογής χρησιμοποιείται καλύτερα όταν θέλετε:
- Πρέπει να ταξινομήσετε μια μικρή λίστα στοιχείων με αύξουσα σειρά
- Όταν το κόστος ανταλλαγής τιμών είναι ασήμαντο
- Χρησιμοποιείται επίσης όταν πρέπει να βεβαιωθείτε ότι έχουν ελεγχθεί όλες οι τιμές στη λίστα.
Πλεονεκτήματα της επιλογής Ταξινόμηση
Τα παρακάτω είναι τα πλεονεκτήματα του είδους επιλογής
- Λειτουργεί πολύ καλά σε μικρές λίστες
- Είναι ένας αλγόριθμος επιτόπου. Δεν απαιτεί πολύ χώρο για ταξινόμηση. Απαιτείται μόνο ένας επιπλέον χώρος για τη συγκράτηση της χρονικής μεταβλητής.
- Αποδίδει καλά σε αντικείμενα που έχουν ήδη ταξινομηθεί.
Μειονεκτήματα της επιλογής Ταξινόμηση
Τα παρακάτω είναι τα μειονεκτήματα του είδους επιλογής.
- Λειτουργεί άσχημα όταν εργάζεται σε τεράστιες λίστες.
- Ο αριθμός των επαναλήψεων που πραγματοποιήθηκαν κατά την ταξινόμηση είναι n-τετράγωνο, όπου n είναι ο συνολικός αριθμός στοιχείων στη λίστα.
- Άλλοι αλγόριθμοι, όπως η γρήγορη ταξινόμηση, έχουν καλύτερη απόδοση σε σύγκριση με το είδος επιλογής.
Περίληψη:
- Επιλογή ταξινόμησης είναι ένας επιτόπιος αλγόριθμος σύγκρισης που χρησιμοποιείται για την ταξινόμηση μιας τυχαίας λίστας σε μια παραγγελία. Έχει χρονική πολυπλοκότητα του O (n 2 )
- Η λίστα χωρίζεται σε δύο ενότητες, ταξινομημένες και ταξινομημένες. Η ελάχιστη τιμή επιλέγεται από την μη ταξινομημένη ενότητα και τοποθετείται στην ταξινομημένη ενότητα.
- Αυτό το πράγμα επαναλαμβάνεται έως ότου ταξινομηθούν όλα τα στοιχεία.
- Η εφαρμογή του ψευδοκώδικα στο Python 3 συνεπάγεται τη χρήση δύο για βρόχους και εάν δηλώσεις για έλεγχο εάν η ανταλλαγή είναι απαραίτητη
- Η πολυπλοκότητα του χρόνου μετρά τον αριθμό των βημάτων που απαιτούνται για την ταξινόμηση της λίστας.
- Η χειρότερη περίπτωση πολυπλοκότητας συμβαίνει όταν η λίστα είναι σε φθίνουσα σειρά. Έχει χρονική πολυπλοκότητα [Big-O] O (n 2 )
- Η πολυπλοκότητα του χρόνου στην περίπτωση συμβαίνει όταν η λίστα είναι ήδη σε αύξουσα σειρά. Έχει χρονική πολυπλοκότητα [Big-Omega] Ω (n 2 )
- Η πολυπλοκότητα του μέσου χρόνου εμφανίζεται όταν η λίστα είναι τυχαία. Έχει χρονική πολυπλοκότητα [Big-theta] ⊝ (n 2 )
- Το είδος επιλογής χρησιμοποιείται καλύτερα όταν έχετε μια μικρή λίστα στοιχείων προς ταξινόμηση, το κόστος ανταλλαγής τιμών δεν έχει σημασία και ο έλεγχος όλων των τιμών είναι υποχρεωτικός.
- Το είδος επιλογής δεν αποδίδει καλά σε τεράστιες λίστες
- Άλλοι αλγόριθμοι ταξινόμησης, όπως η γρήγορη ταξινόμηση, έχουν καλύτερη απόδοση σε σύγκριση με το είδος επιλογής.