# Ταξινόμηση

> Ταξινόμηση με επιλογή και με φυσαλίδα, βήμα βήμα.

Πληροφορική, Γ΄ Γυμνασίου. https://www.akademio.gr/el/gym-c/informatics/sorting

## Τι θα μάθεις

- Να αντιμεταθέτεις δύο τιμές σωστά και να εξηγείς γιατί δεν αρκούν δύο απλές εκχωρήσεις.
- Να εκτελείς με το χέρι την ταξινόμηση με επιλογή και την ταξινόμηση φυσαλίδας, πέρασμα προς πέρασμα.
- Να διαβάζεις τον κώδικα Python των δύο αλγορίθμων.
- Να υπολογίζεις ότι και οι δύο κάνουν n(n − 1)/2 συγκρίσεις και να εξηγείς τι σημαίνει αυτό για μεγάλες λίστες.

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

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

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

```python
[29, 10, 14, 37, 13]
```

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

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

> **Πρόσεχε**
>
> **Δύο εκχωρήσεις στη σειρά δεν ανταλλάσσουν δύο τιμές.**
>
> *Διαδραστικό στη σελίδα: Ανταλλαγή που δεν ανταλλάσσει*
>
> Τυπώνει `8 8`. Η πρώτη εκχώρηση `x = y` **σβήνει** το $3$ πριν προλάβει να σωθεί κάπου. Όταν μετά γράφεις `y = x`, το `x` είναι ήδη $8$.

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

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

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

```text
8 3
```

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

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

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

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

*Διαδραστικό στη σελίδα: Ταξινόμηση με επιλογή*

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

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

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

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

```python
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}
$$

> **Κλειδί**
>
> **Και οι δύο αλγόριθμοι κάνουν $\frac{n(n-1)}{2}$ συγκρίσεις.** Όταν η λίστα **διπλασιάζεται**, οι συγκρίσεις γίνονται περίπου **τετραπλάσιες**.
>
> | Στοιχεία $n$ | Συγκρίσεις |
> | ------------ | ---------- |
> | $10$         | $45$       |
> | $100$        | $4950$     |
> | $1000$       | $499\,500$ |
>
> Αυτό είναι εντάξει για μια τάξη $25$ μαθητών, αλλά όχι για τα εκατομμύρια εγγραφές μιας τράπεζας. Γι' αυτό η έτοιμη `sorted()` της Python χρησιμοποιεί άλλον, πολύ ταχύτερο αλγόριθμο για μεγάλες λίστες.

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

Δοκίμασε και τους δύο αλγόριθμους σε μια νέα λίστα, μία σύγκριση τη φορά. Πριν από κάθε πάτημα, πες τι θα γίνει: στη φυσαλίδα αν θα γίνει αντιμετάθεση, στην επιλογή αν βρέθηκε νέο ελάχιστο.

*Διαδραστικό στη σελίδα: Βήμα βήμα: επιλογή και φυσαλίδα*

## Παραδείγματα

### Παράδειγμα 1: Εκτέλεσε ταξινόμηση με επιλογή στη λίστα \[29, 10, 14, 37, 13] και γράψε τη λίστα μετά από κάθε πέρασμα.

1. **1ο πέρασμα:** το μικρότερο όλης της λίστας είναι το `10`, στη θέση $1$. Ανταλλάσσεται με τη θέση $0$: `[10, 29, 14, 37, 13]`. Συγκρίσεις: $4$.
2. **2ο πέρασμα:** από τη θέση $1$ και μετά, το μικρότερο είναι το `13`, στη θέση $4$. Ανταλλάσσεται με τη θέση $1$: `[10, 13, 14, 37, 29]`. Συγκρίσεις: $3$.
3. **3ο πέρασμα:** από τη θέση $2$ και μετά, το μικρότερο είναι το `14`, που είναι **ήδη** στη θέση $2$. Η «ανταλλαγή» γίνεται με τον εαυτό του και η λίστα δεν αλλάζει. Συγκρίσεις: $2$.
4. **4ο πέρασμα:** ανάμεσα σε `37` και `29`, μικρότερο το `29`. Ανταλλάσσονται: `[10, 13, 14, 29, 37]`. Συγκρίσεις: $1$.
   | Μετά το πέρασμα | Λίστα                  | Συγκρίσεις |
   | --------------- | ---------------------- | ---------- |
   | 1ο              | `[10, 29, 14, 37, 13]` | $4$        |
   | 2ο              | `[10, 13, 14, 37, 29]` | $3$        |
   | 3ο              | `[10, 13, 14, 37, 29]` | $2$        |
   | 4ο              | `[10, 13, 14, 29, 37]` | $1$        |
   Το τελευταίο στοιχείο δεν χρειάζεται δικό του πέρασμα: όταν όλα τα άλλα είναι στη θέση τους, είναι κι αυτό. Γι' αυτό ο εξωτερικός βρόχος είναι `range(n - 1)`.

### Παράδειγμα 2: Πόσες συγκρίσεις κάνει η ταξινόμηση φυσαλίδας, χωρίς τη βελτίωση της σημαίας, σε λίστα 20 στοιχείων; Και σε λίστα 40 στοιχείων;

1. **Ο τύπος:** $\frac{n(n-1)}{2}$. Για $n = 20$: $\frac{20 \cdot 19}{2} = 190$.
2. **Για $n = 40$:** $\frac{40 \cdot 39}{2} = 780$.
3. **Η σύγκριση:** τα στοιχεία διπλασιάστηκαν, οι συγκρίσεις έγιναν $780 / 190 \approx 4{,}1$ φορές περισσότερες. Αυτό είναι το «περίπου τετραπλάσιες» της βασικής ιδέας.

> **Θυμήσου**
>
> - Αντιμετάθεση στην Python: `a, b = b, a`. Με δύο απλές εκχωρήσεις χάνεται η μία τιμή.
> - **Επιλογή:** βρες το ελάχιστο και βάλ' το μπροστά. Μετά από κάθε πέρασμα, η αρχή της λίστας είναι έτοιμη.
> - **Φυσαλίδα:** σύγκρινε γείτονες και αντιμετάθεσε. Μετά από κάθε πέρασμα, το τέλος της λίστας είναι έτοιμο.
> - Και οι δύο: $\frac{n(n-1)}{2}$ συγκρίσεις, με $n - 1$ περάσματα.

## Ερωτήσεις

1. Τι τυπώνει ο κώδικας x = 3; y = 8; x = y; y = x; print(x, y);
   - 8 8
   - 8 3
   - 3 8
   - 3 3
2. Ποια εντολή ανταλλάσσει σωστά τις τιμές των a και b στην Python;
   - a, b = b, a
   - a = b, b = a
   - a = b και από κάτω b = a
   - swap(a, b)
3. Πώς είναι η λίστα [29, 10, 14, 37, 13] μετά το 1ο πέρασμα της ταξινόμησης με επιλογή;
   - [10, 29, 14, 37, 13]
   - [10, 14, 29, 13, 37]
   - [10, 13, 14, 29, 37]
   - [13, 10, 14, 37, 29]
4. Πώς είναι η λίστα [29, 10, 14, 37, 13] μετά το 1ο πέρασμα της ταξινόμησης φυσαλίδας;
   - [10, 14, 29, 13, 37]
   - [10, 29, 14, 37, 13]
   - [10, 29, 14, 13, 37]
   - [10, 13, 14, 29, 37]
5. Πόσες συγκρίσεις κάνει η ταξινόμηση με επιλογή σε λίστα 5 στοιχείων;
   - 10
   - 25
   - 5
   - 20
6. Πόσες συγκρίσεις κάνει η ταξινόμηση φυσαλίδας (χωρίς σημαία) σε λίστα 100 στοιχείων;
   - 4950
   - 100
   - 10000
   - 99
7. Μετά το 1ο πέρασμα της ταξινόμησης φυσαλίδας, τι είναι σίγουρο;
   - το μεγαλύτερο στοιχείο είναι στην τελευταία θέση
   - το μικρότερο στοιχείο είναι στην πρώτη θέση
   - η λίστα είναι ταξινομημένη
   - έγιναν n − 1 αντιμεταθέσεις
8. Πόσες συγκρίσεις κάνει η ταξινόμηση με επιλογή στη λίστα [1, 2, 3, 4], που είναι ήδη ταξινομημένη;
   - 6
   - 0
   - 3
   - 4
9. Μια λίστα διπλασιάζεται σε μέγεθος. Πώς αλλάζουν περίπου οι συγκρίσεις της ταξινόμησης με επιλογή;
   - γίνονται περίπου τετραπλάσιες
   - γίνονται ακριβώς διπλάσιες
   - αυξάνονται μόνο κατά μία
   - μένουν περίπου οι ίδιες
10. Ποια είναι η διαφορά ανάμεσα στο sorted(lista) και στο lista.sort();
   - η sorted επιστρέφει νέα λίστα, η sort αλλάζει την ίδια τη λίστα
   - η sorted ταξινομεί σε φθίνουσα σειρά και η sort σε αύξουσα
   - η sorted χρησιμοποιεί φυσαλίδα και η sort επιλογή
   - καμία διαφορά, είναι δύο ονόματα για το ίδιο

## Ασκήσεις

1. Πόσα περάσματα κάνει η ταξινόμηση με επιλογή σε λίστα 8 στοιχείων;
2. Γράψε μία γραμμή Python που αντιμεταθέτει τα στοιχεία lista[j] και lista[j + 1].
3. Εκτελείς ταξινόμηση φυσαλίδας στη λίστα [5, 1, 4, 2].
   α) Πώς είναι η λίστα μετά το 1ο πέρασμα;
   β) Πόσες αντιμεταθέσεις γίνονται συνολικά;
4. Εκτελείς ταξινόμηση με επιλογή στη λίστα [8, 3, 6, 1].
   α) Πώς είναι η λίστα μετά το 1ο πέρασμα;
   β) Πόσες συγκρίσεις κάνει συνολικά ο αλγόριθμος;
   γ) Πόσες συγκρίσεις θα έκανε σε λίστα 30 στοιχείων;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/gym-c/informatics/sorting
