Στην επιστήμη των υπολογιστών, η ταξινόμηση με επιλογή είναι ένας αλγόριθμος ταξινόμησης, και συγκεκριμένα μια επιτόπια σύγκριση στοιχείων. Έχει O(n2) χρονική πολυπλοκότητα, γεγονός που τον καθιστά αναποτελεσματικό σε μεγάλες λίστες, και γενικά παρουσιάζεται χειρότερος από τον παρόμοιο αλγόριθμο ταξινόμησης με εισαγωγή. Η ταξινόμηση με επιλογή είναι αξιοσημείωτος για την απλότητά του, και έχει πλεονεκτήματα απόδοσης πάνω από πιο περίπλοκους αλγορίθμους σε ορισμένες περιπτώσεις, ιδιαίτερα όπου η βοηθητική μνήμη είναι περιορισμένη.
Ο αλγόριθμος χωρίζει τη λίστα εισόδου σε δύο μέρη: την υπο-λίστα των αντικειμένων που έχουν ήδη ταξινομηθεί, η οποία έχει δημιουργηθεί από αριστερά προς τα δεξιά της λίστας, και την υπο-λίστα των αντικειμένων που απομένουν να ταξινομηθούν, που καταλαμβάνουν τον υπόλοιπο χώρο της λίστα. Αρχικά, η ταξινομημένη υπο-λίστα είναι κενή και η αταξινόμητη υπο-λίστα είναι ολόκληρη η λίστα εισόδου. Ο αλγόριθμος αρχικά ξεκινά με την εύρεση του μικρότερου (ή μεγαλύτερου, ανάλογα με τη σειρά ταξινόμησης) στοιχείου στην αταξινόμητη υπο-λίστα, ανταλλάζοντας το με το αριστερό στοιχείο (βάζοντας το σε ταξινομημένη σειρά), και μετακινεί στα όρια της λίστας κάθε ένα στοιχείο προς τα δεξιά.
Εδώ είναι ένα παράδειγμα αυτού του αλγορίθμου ταξινόμησης με επιλογή με πέντε στοιχεία:
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
Μαθηματικός ορισμός
Έστω
L
{\displaystyle L}
ένα μη-κενό σύνολο και
f
:
L
→
L
{\displaystyle f:L\to L}
έτσι ώστε
f
(
L
)
=
L
′
{\displaystyle f(L)=L'}
όπου:
L
′
{\displaystyle L'}
είναι μια μετάθεση του
L
{\displaystyle L}
,
e
i
≤
e
i
+
1
{\displaystyle e_{i}\leq e_{i+1}}
για κάθε
e
∈
L
′
{\displaystyle e\in L'}
and
i
∈
N
{\displaystyle i\in \mathbb {N} }
,
f
(
L
)
=
{
L
,
if
|
L
|
=
1
{
s
}
∪
f
(
L
s
)
,
otherwise
{\displaystyle f(L)={\begin{cases}L,&{\mbox{if }}|L|=1\\\{s\}\cup f(L_{s}),&{\mbox{otherwise}}\end{cases}}}
,
s
{\displaystyle s}
είναι το μεγαλύτερο και μικρότερο στοιχείο του
L
{\displaystyle L}
και,
L
s
{\displaystyle L_{s}}
είναι το σύνολο στοιχείων του
L
{\displaystyle L}
χωρίς το ελάχιστο στοιχείο του
L
{\displaystyle L}
.
Ανάλυση
Η ταξινόμηση με επιλογή δεν είναι δύσκολο να αναλυθεί σε σχέση με άλλους αλγορίθμους ταξινόμησης αφού κανένας από τους βρόχους δεν εξαρτάται από τα δεδομένα του πίνακα.
