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

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

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

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

64 25 12 22 11

11 25 12 22 64

11 12 25 22 64

11 12 22 25 64

11 12 22 25 64

(δεν εμφανίζεται να άλλαξε τίποτα στη τελευταία γραμμή, επειδή οι 2 τελευταίοι αριθμοί ήταν ήδη σε σειρά)

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

64 25 12 22 11

11 64 25 12 22

11 12 64 25 22

11 12 22 64 25

11 12 22 25 64

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

/* a[0] έως a[n-1] είναι ο πίνακας προς ταξινόμηση*/
int i,j;
int iMin;
 
/* διέσχισε όλον τον πίνακα */
/* (θα μπορούσαμε να κάνουμε j < n-1 γιατί το πρώτο στοιχείο το θεωρούμε το ελάχιστο) */
for (j = 0; j < n-1; j++) {
    /* βρες το ελάχιστο στοιχείο στον αταξινόμητο πίνακα a[j .. n-1] */
 
    /* υπόθεσε ότι το ελάχιστο είναι το πρώτο στοιχείο */
    iMin = j;
    /* διέσχισε τα στοιχεία μετά το j για να βρεις το μικρότερο */
    for ( i = j+1; i < n; i++) {
        /* άμα αυτό το στοιχείο είναι μικρότερο, είναι το νέο ελάχιστο */  
        if (a[i] < a[iMin]) {
            /* κράτα τη θέση του νέου ελαχίστου */
            iMin = i;
        }
    }
 
    /* Το iMin είναι η θέση του ελάχιστου στοιχείου. Αντάλλαξέ το με το j στοιχείο */
    if ( iMin != j ) {
        swap(a[j], a[iMin]);
    }
}

Μαθηματικός ορισμός

Έστω $L$ ένα μη-κενό σύνολο και $f:L\to L$ έτσι ώστε $f(L)=L'$ όπου:

1. $L'$ είναι μια μετάθεση του $L$,
2. $e_{i}\leq e_{i+1}$ για κάθε $e\in L'$ and $i\in \mathbb {N}$,
3. $f(L)={\begin{cases}L,&{\mbox{if }}|L|=1\\\{s\}\cup f(L_{s}),&{\mbox{otherwise}}\end{cases}}$,
4. $s$ είναι το μεγαλύτερο και μικρότερο στοιχείο του $L$ και,
5. $L_{s}$ είναι το σύνολο στοιχείων του $L$ χωρίς το ελάχιστο στοιχείο του $L$.

Ανάλυση

Η ταξινόμηση με επιλογή δεν είναι δύσκολο να αναλυθεί σε σχέση με άλλους αλγορίθμους ταξινόμησης αφού κανένας από τους βρόχους δεν εξαρτάται από τα δεδομένα του πίνακα. Επιλέγοντας το χαμηλότερο στοιχείο απαιτεί τη σάρωση όλων των στοιχείων n του πίνακα (αυτό παίρνει n − 1 συγκρίσεις) και στη συνέχεια το εναλλαγή με αυτό της πρώτης θέσης. Βρίσκοντας το επόμενο χαμηλότερο στοιχείο απαιτείται η σάρωση των υπόλοιπων n − 1 στοιχείων και ούτω καθεξής, για (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n²) συγκρίσεις (βλέπε Αριθμητική πρόοδος). Κάθε μία από αυτές τις σαρώσεις απαιτεί μία ανταλλαγής για n − 1 στοιχεία (το τελευταίο στοιχείο είναι ήδη στη κατάλληλη θέση).

Σύγκριση με άλλους αλγορίθμους ταξινόμησης

Μεταξύ απλή μέσης κατάστασης αλγορίθμους Θ(n²), ο αλγόριθμος με επιλογή σχεδόν πάντα ξεπερνά την ταξινόμηση φυσαλίδας και τον gnome sort.Ο αλγόριθμος με εισαγωγή είναι αρκετά όμοιος με τον αλγόριθμο με επιλογή μετά την k − οστή επανάληψη του , τα πρώτα k στοιχεία στο πίνακα είναι σε ταξινομημένη σειρά. Πλεονέκτημα του insert sort είναι ότι σαρώνει μόνο όσα στοιχεία που χρειάζεται ώστε να τοποθετήσει το k + 1 στοιχείο, ενώ η ταξινόμηση με επιλογή πρέπει να σαρώσει όλα τα υπόλοιπα στοιχεία για να βρει το k + 1 στοιχείο.

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

Ενώ ο αλγόριθμος ταξινόμησης με επιλογή είναι προτιμότερος από την ταξινόμηση με εισαγωγή όσον αφορά στον αριθμό των εγγραφών (Θ(n) εναλλαγές έναντιΟ(n²) εναλλαγές), σχεδόν πάντα υπερβαίνει κατά πολύ (και ποτέ δεν χάνει), ο αριθμός των εγγραφών όπου ο cycle sort κάνει, μιας και ο cycle sort είναι θεωρητικά βέλτιστος στον αριθμό των εγγραφών. Αυτό μπορεί να είναι σημαντικό, αν οι εγγραφές κοστίζουν περισσότερο από τις αναγνώσεις, όπως με την EEPROM ή την Flash μνήμη, όπου κάθε εγγραφή μειώνει την διάρκεια ζωής της μνήμης.

Τέλος, η ταξινόμηση με επιλογή είναι εξαιρετικά καλύτερος σε επιδόσεις στους μεγαλύτερους πίνακες από Θ(n log n) οι αλγόριθμοι διαίρει και βασίλευε, όπως η ταξινόμηση με συγχώνευση. Ωστόσο, η ταξινόμηση με εισαγωγή ή ο ταξινόμηση με επιλογή είναι και οι δύο συνήθως πιο γρήγοροι για μικρούς πίνακες (δηλαδή λιγότερα από 10-20 στοιχεία). Ένα χρήσιμος τρόπος εξέτασης στην πράξη για αναδρομικούς αλγόριθμους είναι η επιλογή μεταξύ του αλγόριθμου ταξινόμησης με επιλογή και της ταξινόμησης με εισαγωγή και η μελέτη του σε αρκετά μικρές υπολίστες .

Παραλλαγές

Ο Heapsort βελτιώνει σημαντικά το βασικό αλγόριθμο χρησιμοποιώντας μια απεριόριστη δομή δεδομένων σωρού για να επιταχύνει την εύρεση και την αφαίρεση της χαμηλότερης αναφοράς. Αν εφαρμοστεί σωστά, ο σωρός θα επιτρέψει την εξεύρεση του επόμενου χαμηλότερου στοιχείου σε Θ(log n) χρόνο, αντί Θ(n) για τον εσωτερικό βρόχο στην κανονική ταξινόμηση με επιλογή, μειώνοντας το συνολικό χρόνο λειτουργίας σε Θ(n log n).

Μια αμφίδρομη παραλλαγή του αλγορίθμου ταξινόμησης με επιλογή, που ονομάζεται cocktail sort, είναι ένας αλγόριθμος που βρίσκει τόσο τις ελάχιστες και μέγιστες τιμές στη λίστα σε κάθε πέρασμα. Αυτό μειώνει τον αριθμό των σαρώσεων του καταλόγου με συντελεστή 2, εξαλείφοντας κάποια επιβάρυνση βρόχου, αλλά δεν μειώνεται στην πραγματικότητα ο αριθμός των συγκρίσεων ή των εναλλαγών. Σημειώστε, ωστόσο, ότι ο cocktail sort πιο συχνά αναφέρεται σε μια αμφίδρομη παραλλαγή του bubble sort.

Ο ταξινόμηση με επιλογή μπορεί να εφαρμοστεί ως stable sort. Εάν, αντί για εναλλαγή στο βήμα 2, η ελάχιστη τιμή εισάγεται στην πρώτη θέση (δηλαδή, όλα τα υπάρχοντα στοιχεία μετακινούνται μια θέση προς τα κάτω), ο αλγόριθμος είναι σταθερός. Ωστόσο, η τροποποίηση αυτή απαιτεί είτε μια δομή δεδομένων που υποστηρίζει αποτελεσματικές εισαγωγές ή διαγραφές, όπως μια συνδεδεμένη λίστα, ή οδηγεί σε εκτέλεση Θ(n²) εγγραφών.

Στην παραλλαγή bingo sort, τα στοιχεία είναι οργανωμένα μέσα από επανειλημμένες αναζητήσεις εντός των στοιχεία που απομένουν, για να βρεθεί το ή τα μεγαλύτερα σε τιμή στοιχεία και έπειτα μετακινούνται όλα μαζί με την ίδια τιμή στις τελικές τους θέσεις. Όπως και ο counting sort, αυτή είναι μια αποτελεσματική παραλλαγή αν υπάρχουν πολλές ίδιες τιμές στη λίστα. Πράγματι, o ταξινόμηση με επιλογή κάνει ένα πέρασμα στα υπόλοιπα εναπομείναντα στοιχεία για κάθε στοιχείο που μετακινείται. Ο bingo sort κάνει ένα πέρασμα για κάθε τιμή (όχι αντικείμενο): μετά από ένα αρχικό πέρασμα για να βρει τη μεγαλύτερη τιμή, στα επόμενα περάσματα μπορεί να μετακινεί κάθε στοιχείο με αυτή την τιμή στην τελική του θέση, ενώ η αναζητά την επόμενη σε σειρά τιμή όπως φαίνεται στον ακόλουθο ψευδοκώδικα (πίνακες είναι με μηδενική βάση και το for-loop περιλαμβάνει τόσο τα άνω και κάτω όρια, όπως σε Pascal):

bingo(array A)

{ Η παρακάτω διαδικασία ταξινομεί σε αυξητική σειρά }
begin
    max := length(A)-1;

    { Η πρώτη επανάληψη είναι γραμμένο για να μοιάζει πολύ με τις επόμενες, αλλά χωρίς μετατοπίσεις.}
    nextValue := A[max];
    for i := max - 1 downto 0 do
        if A[i] > nextValue then
            nextValue := A[i];
    while (max > 0) and (A[max] = nextValue) do
        max := max - 1;

    while max > 0 do begin
        value := nextValue;
        nextValue := A[max];
        for i := max - 1 downto 0 do
             if A[i] = value then begin
                 swap(A[i], A[max]);
                 max := max - 1;
             end else if A[i] > nextValue then
                 nextValue := A[i];
        while (max > 0) and (A[max] = nextValue) do
            max := max - 1;
    end;
end;

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

Αναφορές

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison–Wesley, 1997. ISBN 0-201-89685-0. Pages 138–141 of Section 5.2.3: Sorting by Selection.
• Anany Levitin. Introduction to the Design & Analysis of Algorithms, 2nd Edition. ISBN 0-321-35828-7. Section 3.1: Selection Sort, pp 98–100.
• Robert Sedgewick. Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching: Fundamentals, Data Structures, Sorting, Searching Pts. 1–4, Second Edition. Addison–Wesley Longman, 1998. ISBN 0-201-35088-2. Pages 273–274

Εξωτερικοί σύνδεσμοι

• Animated Sorting Algorithms: Selection Sort – γραφική αναπαράσταση της ταξινόμησης με επιλογή