Selection sort

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

rdf:langString Στην επιστήμη των υπολογιστών, η ταξινόμηση με επιλογή είναι ένας αλγόριθμος ταξινόμησης, και συγκεκριμένα μια επιτόπια σύγκριση στοιχείων. Έχει O(n2) χρονική πολυπλοκότητα, γεγονός που τον καθιστά αναποτελεσματικό σε μεγάλες λίστες, και γενικά παρουσιάζεται χειρότερος από τον παρόμοιο αλγόριθμο ταξινόμησης με εισαγωγή. Η ταξινόμηση με επιλογή είναι αξιοσημείωτος για την απλότητά του, και έχει πλεονεκτήματα απόδοσης πάνω από πιο περίπλοκους αλγορίθμους σε ορισμένες περιπτώσεις, ιδιαίτερα όπου η βοηθητική μνήμη είναι περιορισμένη. Ο αλγόριθμος χωρίζει τη λίστα εισόδου σε δύο μέρη: την υπο-λίστα των αντικειμένων που έχουν ήδη ταξινομηθεί, η οποία έχει δημιουργηθεί από αριστερά προς τα δεξιά της λίστας, και την υπο-λίστα των αντικειμένων που απομένουν να ταξινομηθούν, που καταλαμβάνουν τον υπόλοιπο χώρο της λίστα. Αρχικά, η ταξινομημένη υπο-λίστα είναι κενή και η αταξινόμητη υπο-λίστα είναι ολόκληρη η λίστα εισόδου. Ο αλγόριθμος αρχικά ξεκινά με την εύρεση του μικρότερου (ή μεγαλύτερου, ανάλογα με τη σειρά ταξινόμησης) στοιχείου στην αταξινόμητη υπο-λίστα, ανταλλάζοντας το με το αριστερό στοιχείο (βάζοντας το σε ταξινομημένη σειρά), και μετακινεί στα όρια της λίστας κάθε ένα στοιχείο προς τα δεξιά. Εδώ είναι ένα παράδειγμα αυτού του αλγορίθμου ταξινόμησης με επιλογή με πέντε στοιχεία: 64 25 12 22 1111 25 12 22 6411 12 25 22 6411 12 22 25 6411 12 22 25 64 (δεν εμφανίζεται να άλλαξε τίποτα στη τελευταία γραμμή, επειδή οι 2 τελευταίοι αριθμοί ήταν ήδη σε σειρά) Η ταξινόμηση με επιλογή μπορεί επίσης να χρησιμοποιηθεί σε δομές λιστών κάνοντας τη πρόσθεση και αφαίρεση στοιχείων αποτελεσματική, όπως σε μια συνδεδεμένη λίστα. Σε αυτή την περίπτωση είναι πιο σύνηθες να αφαιρείται το ελάχιστο στοιχείο από το υπόλοιπο της λίστας και στη συνέχεια να τοποθετείται στο τέλος των ταξινομημένων μέχρι τώρα. Για παράδειγμα: 64 25 12 22 1111 64 25 12 2211 12 64 25 2211 12 22 64 2511 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]); }}