Ο αλγόριθμος ταξινόμησης με επιλογή (Selection Sort) είναι ένας απλός αλγόριθμος ταξινόμησης που βασίζεται στην ιδέα της επιλογής του μικρότερου (ή μεγαλύτερου) στοιχείου και της τοποθέτησής του στη σωστή θέση. Θεωρούμε ότι ο πίνακας χωρίζεται σε δύο μέρη: το ταξινομημένο (αρχικά κενό) και το αταξινόμητο (όλα τα στοιχεία). Από το αταξινόμητο τμήμα: βρίσκουμε το μικρότερο στοιχείο και το ανταλλάσσουμε με το πρώτο στοιχείο του αταξινόμητου τμήματος. Τοποθετούμε έτσι το μικρότερο στοιχείο στην πρώτη σωστή θέση και επαναλαμβάνουμε τη διαδικασία για το υπόλοιπο τμήμα του πίνακα, μέχρι να ταξινομηθούν όλα τα στοιχεία.
Να γράψετε πρόγραμμα το οποίο:
- Διαβάζει 10 αριθμούς και να τους αποθηκεύει σε μία λίστα.
-
Καλεί συνάρτηση με όνομα selection_sort, η οποία δέχεται ως παράμετρο μία λίστα στοιχείων και επιστρέφει τη λίστα ταξινομημένη σε αύξουσα σειρά, χρησιμοποιώντας τον αλγόριθμο ταξινόμησης με επιλογή (Selection Sort) όπως περιγράφεται παραπάνω.
- Να εμφανίζει στην οθόνη τη ταξινομημένη λίστα.
Λύση
# Συνάρτηση
def selection_sort(lista):
n = len(lista)
for i in range(n): # Διασχίζουμε τη λίστα μέχρι το στοιχείο n-1
min_index = i # Υποθέτουμε ότι το τρέχον στοιχείο είναι το μικρότερο και κρατάμε τη θέση του
for j in range(i + 1, n): # Ψάχνουμε στο υπόλοιπο μέρος της λίστας για το μικρότερο στοιχείο και κρατάμε τη θέση του
if lista[j] < lista[min_index]:
min_index = j
lista[i], lista[min_index] = lista[min_index], lista[i] # Ανταλλάσσουμε το μικρότερο στοιχείο που βρήκαμε με το πρώτο στοιχείο
return lista
# Πρόγραμμα
L=[]
for i in range(10):
L.append(input('Δώστε στοιχείο...:'))
selection_sort(L)
print L