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

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

ΕΠΙΛΟΓΗ ΤΑΞΙΝΟΜΗΣΗ είναι ένας αλγόριθμος σύγκρισης ταξινόμησης που χρησιμοποιείται για την ταξινόμηση μιας τυχαίας λίστας στοιχείων σε αύξουσα σειρά. Η σύγκριση δεν απαιτεί πολύ επιπλέον χώρο. Απαιτεί μόνο έναν επιπλέον χώρο μνήμης για τη χρονική μεταβλητή.

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

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

Πώς λειτουργεί η ταξινόμηση επιλογής;

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

Παράδειγμα

Για παράδειγμα, εάν ο δείκτης της ελάχιστης τιμής είναι 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 = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [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 που έχει τυχαίους αριθμούς
Εκτυπώστε την ταξινομημένη λίστα αφού καλέσετε την επιλογή Ταξινόμηση συνάρτησης περνώντας στο el ως παράμετρο.

Χρονική Πολυπλοκότητα Επιλογής Ταξινόμηση

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

Ο εξωτερικός βρόχος που επιλέγει τις τιμές μία προς μία από τη λίστα εκτελείται n φορές όπου n είναι ο συνολικός αριθμός των τιμών στη λίστα.

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

Επομένως, ο αριθμός των εκτελέσεων είναι (n * n), ο οποίος μπορεί επίσης να εκφραστεί ως O(n²).

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

Χειρότερη περίπτωση – εδώ η παρεχόμενη λίστα είναι με φθίνουσα σειρά. Ο αλγόριθμος εκτελεί τον μέγιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-O] O(n²)
καλυτερα case – αυτό συμβαίνει όταν η παρεχόμενη λίστα είναι ήδη ταξινομημένη. Ο αλγόριθμος εκτελεί τον ελάχιστο αριθμό εκτελέσεων που εκφράζεται ως [Big-Omega] ?(n²)
Μέση περίπτωση – αυτό συμβαίνει όταν η λίστα είναι σε τυχαία σειρά. Η μέση πολυπλοκότητα εκφράζεται ως [Big-theta] ?(n²)

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

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

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

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

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

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

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

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

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

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

Περίληψη

Η ταξινόμηση επιλογής είναι ένας επιτόπιος αλγόριθμος σύγκρισης που χρησιμοποιείται για την ταξινόμηση μιας τυχαίας λίστας σε μια ταξινομημένη λίστα. Έχει χρονική πολυπλοκότητα O(n²)
Η λίστα χωρίζεται σε δύο ενότητες, ταξινομημένη και μη ταξινομημένη. Η ελάχιστη τιμή επιλέγεται από το μη ταξινομημένο τμήμα και τοποθετείται στο ταξινομημένο τμήμα.
Αυτό το πράγμα επαναλαμβάνεται μέχρι να ταξινομηθούν όλα τα στοιχεία.
Εφαρμογή του ψευδοκώδικα στο Python 3 περιλαμβάνει τη χρήση δύο βρόχων for και if εντολών για να ελέγξετε αν είναι απαραίτητη η εναλλαγή
Η χρονική πολυπλοκότητα μετρά τον αριθμό των βημάτων που απαιτούνται για την ταξινόμηση της λίστας.
Η χρονική πολυπλοκότητα στη χειρότερη περίπτωση συμβαίνει όταν η λίστα είναι σε φθίνουσα σειρά. Έχει χρονική πολυπλοκότητα [Big-O] O(n²)
Η χρονική πολυπλοκότητα στην καλύτερη περίπτωση συμβαίνει όταν η λίστα είναι ήδη σε αύξουσα σειρά. Έχει χρονική πολυπλοκότητα [Big-Omega] ?(n²)
Η πολυπλοκότητα του χρόνου μέσης περίπτωσης συμβαίνει όταν η λίστα είναι σε τυχαία σειρά. Έχει χρονική πολυπλοκότητα [Big-theta] ?(n²)
Η ταξινόμηση επιλογής χρησιμοποιείται καλύτερα όταν έχετε μια μικρή λίστα στοιχείων για ταξινόμηση, το κόστος αλλαγής τιμών δεν έχει σημασία και ο έλεγχος όλων των τιμών είναι υποχρεωτικός.
Η ταξινόμηση επιλογής δεν έχει καλή απόδοση σε τεράστιες λίστες
Άλλοι αλγόριθμοι ταξινόμησης, όπως η γρήγορη ταξινόμηση, έχουν καλύτερη απόδοση σε σύγκριση με την ταξινόμηση επιλογής.