Ταξινόμηση

Γιατί ταξινομούμε

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

Ταξινόμηση (sorting) είναι η αναδιάταξη των στοιχείων μιας λίστας σε αύξουσα (από το μικρότερο στο μεγαλύτερο) ή φθίνουσα σειρά. Εδώ θα δούμε δύο κλασικούς αλγορίθμους, την ταξινόμηση με επιλογή και την ταξινόμηση φυσαλίδας, πάνω στην ίδια λίστα:

[29, 10, 14, 37, 13]

Πρώτα, η αντιμετάθεση

Και οι δύο αλγόριθμοι χρειάζονται να ανταλλάξουν δύο στοιχεία μεταξύ τους. Αυτό είναι πιο ύπουλο απ' όσο φαίνεται.

Η κλασική λύση, αυτή του ψευδοκώδικα, χρησιμοποιεί μια βοηθητική μεταβλητή, όπως όταν ανταλλάσσεις το περιεχόμενο δύο ποτηριών με τη βοήθεια ενός τρίτου άδειου: temp = x, x = y, y = temp.

Η Python έχει και μια δική της, πιο σύντομη γραφή, που κάνει την ανταλλαγή σε μία εντολή:

x = 3
y = 8
x, y = y, x
print(x, y)

8 3

Το ίδιο δουλεύει και για στοιχεία λίστας: lista[i], lista[j] = lista[j], lista[i].

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

Η ιδέα: βρες το μικρότερο στοιχείο όλης της λίστας και βάλ' το πρώτο. Μετά βρες το μικρότερο από όσα απέμειναν και βάλ' το δεύτερο. Και ούτω καθεξής.

Κάθε τέτοιος γύρος λέγεται πέρασμα. Μετά από κάθε πέρασμα, ένα ακόμη στοιχείο έχει πάρει την οριστική του θέση στην αρχή της λίστας.

def epilogi(lista):
    n = len(lista)
    for i in range(n - 1):
        thesi_min = i
        for j in range(i + 1, n):
            if lista[j] < lista[thesi_min]:
                thesi_min = j
        lista[i], lista[thesi_min] = lista[thesi_min], lista[i]

a = [29, 10, 14, 37, 13]
epilogi(a)
print(a)

[10, 13, 14, 29, 37]

Εδώ υπάρχει βρόχος μέσα σε βρόχο. Ο εξωτερικός (i) μετρά τα περάσματα και δείχνει τη θέση που γεμίζουμε. Ο εσωτερικός (j) διατρέχει ό,τι απέμεινε για να βρει τη θέση του ελάχιστου, με τον ίδιο αλγόριθμο που έγραψες για το μέγιστο στο μάθημα των λιστών.

Η συνάρτηση δεν έχει return: αλλάζει την ίδια τη λίστα που της δόθηκε.

Ταξινόμηση φυσαλίδας

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

def fysalida(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]

Σε κάθε πέρασμα ο εσωτερικός βρόχος κάνει μία σύγκριση λιγότερη (n - 1 - i), γιατί το τέλος της λίστας έχει ήδη ταξινομηθεί.

Πίνακας βημάτων: φυσαλίδα στη λίστα [29, 10, 14, 37, 13]

Κάθε γραμμή είναι μία σύγκριση γειτόνων. Πριν πατήσεις, πες αν θα γίνει αντιμετάθεση.

Βήμα	Πέρασμα	Σύγκριση	Αντιμετάθεση;	Λίστα μετά
Ζωντανή ενημέρωση

Επόμενο βήμαΌλαΕπαναφορά

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

Πόσες συγκρίσεις;

Για λίστα με $n = 5$ στοιχεία, και οι δύο αλγόριθμοι κάνουν στο 1ο πέρασμα $4$ συγκρίσεις, στο 2ο $3$, στο 3ο $2$, στο 4ο $1$. Σύνολο $4 + 3 + 2 + 1 = 10$.

Γενικά, για $n$ στοιχεία:

$$(n-1) + (n-2) + \dots + 2 + 1 = \frac{n(n-1)}{2}$$

Στην πράξη, σε ένα πρόγραμμα Python γράφεις απλώς sorted(lista), που επιστρέφει νέα ταξινομημένη λίστα, ή lista.sort(), που ταξινομεί την ίδια τη λίστα. Αξίζει όμως να ξέρεις τι γίνεται από κάτω: είναι ο τρόπος να καταλάβεις γιατί κάποια προγράμματα αργούν όταν τα δεδομένα μεγαλώνουν.

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση