# Ταξινόμηση ευθείας ανταλλαγής

> Οι διαδοχικές ανταλλαγές γειτονικών στοιχείων, βήμα βήμα, σε αύξουσα και φθίνουσα σειρά.

Προγραμματισμός Υπολογιστών, Γ΄ ΕΠΑΛ. https://www.akademio.gr/el/epal-c/programming/bubble-sort

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

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

## Ο Αλέξανδρος βρίσκει τη θέση του

Τέσσερις μαθητές περιμένουν σε αλφαβητική σειρά την πρόβα της παρέλασης. Ο Αλέξανδρος φτάνει τελευταίος και μπαίνει στο τέλος της σειράς. Συγκρίνει το όνομά του με αυτό του συμμαθητή που είναι **μπροστά** του: αν προηγείται αλφαβητικά, αλλάζουν θέσεις. Μετά συγκρίνεται με τον επόμενο, ώσπου να φτάσει στη θέση του.

| Θέση | Αρχικά         |                |                |                | Τέλος          |
| ---- | -------------- | -------------- | -------------- | -------------- | -------------- |
| 0    | Δημήτρης       | Δημήτρης       | Δημήτρης       | Δημήτρης       | **Αλέξανδρος** |
| 1    | Ευγενία        | Ευγενία        | Ευγενία        | **Αλέξανδρος** | Δημήτρης       |
| 2    | Ναταλία        | Ναταλία        | **Αλέξανδρος** | Ναταλία        | Ευγενία        |
| 3    | Ρένια          | **Αλέξανδρος** | Ναταλία        | Ευγενία        | Ναταλία        |
| 4    | **Αλέξανδρος** | Ρένια          | Ρένια          | Ρένια          | Ρένια          |

Οι συμβολοσειρές συγκρίνονται με τη **λεξικογραφική** διάταξη, δηλαδή αλφαβητικά: `"Αλέξανδρος" < "Ρένια"` είναι `True`. Η αμοιβαία αλλαγή τιμών γίνεται με μία εντολή της Python, `a, b = b, a`, χωρίς βοηθητική μεταβλητή. Με βοηθητική θα έγραφες `temp = a`, `a = b`, `b = temp`.

Οι τέσσερις συγκρίσεις, από τη θέση $4$ ως τη θέση $1$, γράφονται με έναν βρόχο. Στους runners της ενότητας το `print(...)` έχει ένα όρισμα, και έτσι δουλεύει ίδια και στην Python 2.7 του βιβλίου και στην Python 3.

*Διαδραστικό στη σελίδα: Ο Αλέξανδρος ανεβαίνει στη θέση 0*

Η `range(4, 0, -1)` δίνει `4, 3, 2, 1`. Στην τελευταία επανάληψη `j = 1` και `j - 1 = 0`: το τελευταίο στοιχείο που συγκρίνεται είναι το `students[0]`.

## Ένα πέρασμα

> **Στον υπολογιστή σου, με Python 3**
>
> Ο αλγόριθμος γράφεται ίδιος και στις δύο εκδόσεις. Αλλάζουν μόνο η είσοδος και η έξοδος: `print(A)` αντί για `print A`, `input()` αντί για `raw_input()`, και `int(input())` για να διαβάσεις αριθμό, γιατί το `input()` της Python 3 δίνει πάντα κείμενο.

Σε μια λίστα `A` με `N` στοιχεία, ο ίδιος βρόχος γράφεται:

```python
N = len(A)
for j in range(N - 1, 0, -1):
    if A[j] < A[j - 1]:
        A[j], A[j - 1] = A[j - 1], A[j]
```

Αυτό λέγεται **πέρασμα**. Το αποτέλεσμά του είναι ότι το **μικρότερο** στοιχείο ανεβαίνει στη θέση $0$, όπως μια φυσαλίδα στην επιφάνεια του νερού.

*Διαδραστικό στη σελίδα: Ένα πέρασμα στη λίστα \[21, 13, 8, 5, 3, 2]*

## Όλα τα περάσματα

Αν εκτελέσεις το ίδιο πέρασμα ξανά, ανεβαίνει στη θέση $1$ το αμέσως μικρότερο, το $3$. Κάθε πέρασμα φέρνει ένα ακόμα στοιχείο στην τελική του θέση. Δύο παρατηρήσεις κάνουν τον αλγόριθμο οικονομικότερο:

1. **Αρκούν `N - 1` περάσματα.** Όταν τα `N - 1` μικρότερα είναι στις θέσεις τους, το τελευταίο είναι αναγκαστικά στη θέση που περισσεύει. Γι' αυτό η εξωτερική επανάληψη είναι `range(N - 1)`, με `i` από `0` ως και `N - 2`.
2. **Κάθε πέρασμα σταματά νωρίτερα.** Μετά το πέρασμα `i`, οι θέσεις `0` ως `i` είναι ήδη τελικές. Στο επόμενο πέρασμα η φυσαλίδα δεν χρειάζεται να ανέβει πάνω από αυτές.

Η τελευταία σύγκριση του περάσματος `i` είναι η `A[i + 1] < A[i]`, δηλαδή με `j = i + 1`. Γι' αυτό η εσωτερική `range` γίνεται `range(N - 1, i, -1)`, που σταματά στο `i + 1`. Ο αλγόριθμος παίρνει την τελική του μορφή:

```python
N = len(A)
for i in range(N - 1):
    for j in range(N - 1, i, -1):
        if A[j] < A[j - 1]:
            A[j], A[j - 1] = A[j - 1], A[j]
```

Λέγεται **ταξινόμηση ευθείας ανταλλαγής** (straight exchange sort) και είναι πιο γνωστή ως **ταξινόμηση φυσαλίδας** (bubble sort). Βασίζεται στη σύγκριση γειτονικών στοιχείων και στην αντιμετάθεση όσων δεν ακολουθούν τη σειρά της ταξινόμησης.

*Διαδραστικό στη σελίδα: Επτά αριθμοί, πέρασμα πέρασμα*

Μετά το πέρασμα `i = 3` η λίστα είναι ήδη ταξινομημένη, αλλά ο αλγόριθμος κάνει και τα δύο τελευταία. Το πλήθος των συγκρίσεων δεν εξαρτάται από τα δεδομένα: το πέρασμα `i` κάνει `N - 1 - i` συγκρίσεις, άρα συνολικά

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

Για $7$ στοιχεία, $21$ συγκρίσεις. Οι **αντιμεταθέσεις** εξαρτώνται από τα δεδομένα: εδώ ήταν $14$, σε ήδη ταξινομημένη λίστα $0$.

> **Κλειδί**
>
> **Δύο βρόχοι, δύο ρόλοι.** Ο εξωτερικός, `for i in range(N - 1)`, μετρά τα περάσματα. Ο εσωτερικός, `for j in range(N - 1, i, -1)`, πηγαίνει **από το τέλος προς την αρχή** και συγκρίνει κάθε στοιχείο με το **προηγούμενό** του, `A[j]` με `A[j - 1]`.
>
> Μετά το πέρασμα `i`, το τμήμα από τη θέση `0` ως τη θέση `i` είναι ταξινομημένο και δεν ξαναγγίζεται.

> **Πρόσεχε**
>
> **Τα όρια γράφονται ακριβώς.** Η `range(N - 1, i, -1)` ξεκινά από την τελευταία θέση, `N - 1`, και δεν φτάνει ποτέ το `i`. Με `range(N, i, -1)` το πρώτο `A[j]` θα ήταν το `A[N]`, που δεν υπάρχει: `IndexError`.
>
> Μην ανακατεύεις τα δύο ζευγάρια. Ο αλγόριθμος του βιβλίου συγκρίνει `A[j]` με `A[j - 1]`. Αν γράψεις `A[j + 1]`, πρέπει να αλλάξεις και τα όρια.

Θα δεις και τη μορφή `for i in range(N)`. Ταξινομεί σωστά: στο τελευταίο πέρασμα η `range(N - 1, N - 1, -1)` είναι κενή, άρα δεν γίνεται καμία σύγκριση.

## Φθίνουσα σειρά

Για ταξινόμηση από το μεγαλύτερο στο μικρότερο αλλάζει **μόνο ο τελεστής** της σύγκρισης:

```python
if A[j] > A[j - 1]:
    A[j], A[j - 1] = A[j - 1], A[j]
```

Τώρα σε κάθε πέρασμα ανεβαίνει στην κορυφή το **μεγαλύτερο** από όσα απομένουν. Ο αλγόριθμος δουλεύει με αριθμούς και με συμβολοσειρές, γιατί και οι δύο συγκρίνονται με `<` και `>`.

## Η βελτιωμένη φυσαλίδα

Το πλεονέκτημα της ευθείας ανταλλαγής, αν και είναι από τους πιο αργούς αλγορίθμους ταξινόμησης, είναι ότι μπορεί να σταματήσει μόλις διαπιστώσει ότι η λίστα ταξινομήθηκε. Αν σε ένα πέρασμα δεν γίνει **καμία** αντιμετάθεση, όλα τα γειτονικά ζεύγη είναι στη σωστή σειρά. Αυτό το κρατά μια λογική μεταβλητή, η `isSorted`:

*Διαδραστικό στη σελίδα: Σχεδόν ταξινομημένη λίστα*

Το πρώτο πέρασμα φέρνει το $2$ στην αρχή. Το δεύτερο δεν κάνει καμία αντιμετάθεση, η `isSorted` μένει `True` και ο βρόχος σταματά: δύο περάσματα αντί για επτά. Εδώ το `i` ξεκινά από `1`, γι' αυτό η εσωτερική `range` σταματά στο `i - 1`.

Η ταξινόμηση με εισαγωγή (5.3) δεν εξετάζεται.

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

### Παράδειγμα 1: Δίνεται η λίστα A = \[55, 34, 5, 3, 2, 1, 1]. Να γράψετε το περιεχόμενο της λίστας αμέσως μετά από κάθε πέρασμα του αλγορίθμου ταξινόμησης ευθείας ανταλλαγής σε αύξουσα σειρά.

1. **Πρώτο πέρασμα (`i = 0`):** ένα $1$ ανεβαίνει ως τη θέση $0$. Στη σύγκριση `A[6] < A[5]` είναι $1 < 1$, ψευδές, οπότε ανεβαίνει το $1$ της θέσης $5$, και το άλλο $1$ μένει στο τέλος: `[1, 55, 34, 5, 3, 2, 1]`.
2. **Δεύτερο (`i = 1`):** `[1, 1, 55, 34, 5, 3, 2]`. **Τρίτο:** `[1, 1, 2, 55, 34, 5, 3]`. **Τέταρτο:** `[1, 1, 2, 3, 55, 34, 5]`.
3. **Πέμπτο:** `[1, 1, 2, 3, 5, 55, 34]`. **Έκτο (`i = 5`):** `[1, 1, 2, 3, 5, 34, 55]`. Για $7$ στοιχεία, $6$ περάσματα.

### Παράδειγμα 2: Τι θα εμφανίσει το παρακάτω τμήμα προγράμματος;

1. ```python
   A = [4, 1, 3, 2]
   N = len(A)
   s = 0
   for i in range(N - 1):
       for j in range(N - 1, i, -1):
           if A[j] < A[j - 1]:
               A[j], A[j - 1] = A[j - 1], A[j]
               s = s + 1
   print A, s
   ```
2. **Πέρασμα `i = 0`:** `j = 3`, $2 < 3$, αντιμετάθεση: `[4, 1, 2, 3]`. `j = 2`, $2 < 1$ ψευδές. `j = 1`, $1 < 4$, αντιμετάθεση: `[1, 4, 2, 3]`.
3. **Πέρασμα `i = 1`:** `j = 3`, $3 < 2$ ψευδές. `j = 2`, $2 < 4$, αντιμετάθεση: `[1, 2, 4, 3]`. **Πέρασμα `i = 2`:** `j = 3`, $3 < 4$, αντιμετάθεση: `[1, 2, 3, 4]`.
4. **Εμφανίζει `[1, 2, 3, 4] 4`.** Έγιναν $6$ συγκρίσεις, όσο το $\frac{4 \cdot 3}{2}$, και $4$ από αυτές έδωσαν αντιμετάθεση.

### Παράδειγμα 3: Να γράψετε πρόγραμμα σε Python που διαβάζει το πλήθος N των μαθητών ενός τμήματος και για τον καθένα το όνομα και τον βαθμό του, και εμφανίζει τα ονόματα και τους βαθμούς σε φθίνουσα σειρά βαθμού.

1. **Δύο παράλληλες λίστες**, `nameList` και `gradeList`: ο μαθητής της θέσης `i` έχει τον βαθμό της ίδιας θέσης. Η ταξινόμηση γίνεται με βάση τη `gradeList`, με `>` για φθίνουσα σειρά.
2. **Κάθε αντιμετάθεση γίνεται και στις δύο λίστες.** Αν άλλαζαν θέσεις μόνο οι βαθμοί, κάθε όνομα θα έμενε με λάθος βαθμό.
   ```python
   N = input("Πόσοι μαθητές έχει η τάξη; N = ")
   gradeList = []
   nameList = []
   for i in range(N):
       name = raw_input("όνομα = ")
       grade = input("βαθμός = ")
       nameList.append(name)
       gradeList.append(grade)
   for i in range(N - 1):
       for j in range(N - 1, i, -1):
           if gradeList[j] > gradeList[j - 1]:
               gradeList[j], gradeList[j - 1] = gradeList[j - 1], gradeList[j]
               nameList[j], nameList[j - 1] = nameList[j - 1], nameList[j]
   for i in range(N):
       print nameList[i], gradeList[i]
   ```
3. **Για 4 μαθητές**, Ελένη 15, Νίκος 18, Μαρία 12, Γιάννης 19, εμφανίζει `Γιάννης 19`, `Νίκος 18`, `Ελένη 15`, `Μαρία 12`. Το όνομα διαβάζεται με `raw_input`, γιατί είναι κείμενο, και ο βαθμός με `input`, που δίνει αριθμό.

> **Θυμήσου**
>
> - Ευθεία ανταλλαγή: σύγκριση γειτονικών στοιχείων από το τέλος προς την αρχή και αντιμετάθεση όσων είναι σε λάθος σειρά.
> - `for i in range(N - 1):` και μέσα `for j in range(N - 1, i, -1):` με `if A[j] < A[j - 1]:`.
> - Σε κάθε πέρασμα το μικρότερο από όσα απομένουν ανεβαίνει στη θέση `i`.
> - `N - 1` περάσματα, $\frac{N(N-1)}{2}$ συγκρίσεις, όποια κι αν είναι τα δεδομένα.
> - Φθίνουσα σειρά: `>` αντί για `<`. Βελτιωμένη: σταματά όταν ένα πέρασμα δεν κάνει καμία αντιμετάθεση.

## Ερωτήσεις

1. Σωστό ή Λάθος: «Στην ταξινόμηση ευθείας ανταλλαγής συγκρίνονται πάντα γειτονικά στοιχεία της λίστας.»
   - Σωστό, το A[j] με το A[j - 1]
   - Λάθος, το A[j] με το A[0]
   - Λάθος, το A[j] με το ελάχιστο
   - Σωστό, μόνο στο πρώτο πέρασμα
2. Η λίστα [21, 13, 8, 5, 3, 2] περνά ένα πέρασμα της ευθείας ανταλλαγής σε αύξουσα σειρά. Ποιο στοιχείο βρίσκεται μετά στη θέση 0;
   - Το 2
   - Το 21
   - Το 13
   - Το 3
3. Στο πέρασμα i η εσωτερική επανάληψη είναι for j in range(N - 1, i, -1). Ποια είναι η τελευταία τιμή του j;
   - i + 1
   - i
   - i - 1
   - 0
4. Πόσα περάσματα κάνει ο αλγόριθμος του βιβλίου για μια λίστα 7 στοιχείων;
   - 6
   - 7
   - 21
   - Όσα χρειάζονται, ανάλογα με τα δεδομένα
5. Πόσες συγκρίσεις κάνει ο αλγόριθμος του βιβλίου για λίστα 6 στοιχείων;
   - 15
   - 30
   - 25
   - Εξαρτάται από τη σειρά των στοιχείων
6. Τι αλλάζεις στον αλγόριθμο του βιβλίου για να ταξινομεί σε φθίνουσα σειρά;
   - Τη σύγκριση σε if A[j] > A[j - 1]
   - Την εσωτερική σε range(0, N - 1 - i)
   - Την εξωτερική σε range(N - 1, 0, -1)
   - Την αντιμετάθεση σε A[j - 1], A[j] = A[j], A[j - 1]
7. Τι εμφανίζει το τμήμα A = [3, 1, 2], μετά for j in range(2, 0, -1): με την αντιμετάθεση του βιβλίου όταν A[j] < A[j - 1], και στο τέλος print A;
   - [1, 3, 2]
   - [1, 2, 3]
   - [3, 1, 2]
   - [2, 3, 1]
8. Σωστό ή Λάθος: «Σε μια ήδη ταξινομημένη λίστα, ο αλγόριθμος του βιβλίου κάνει λιγότερες συγκρίσεις.»
   - Λάθος, κάνει πάλι N(N − 1)/2 συγκρίσεις
   - Σωστό, κάνει μόνο N − 1 συγκρίσεις
   - Σωστό, δεν κάνει καμία σύγκριση
   - Λάθος, κάνει περισσότερες συγκρίσεις
9. Σωστό ή Λάθος: «Για την αντιμετάθεση των A[j] και A[j - 1] στην Python χρειάζεται βοηθητική μεταβλητή temp.»
   - Λάθος, αρκεί A[j], A[j - 1] = A[j - 1], A[j]
   - Σωστό, αλλιώς χάνεται η μία από τις δύο τιμές
   - Σωστό, η Python δεν έχει εντολή αντιμετάθεσης
   - Λάθος, αρκεί A[j] = A[j - 1] και μετά A[j - 1] = A[j]
10. Ταξινομείς τη gradeList κατά βαθμό, ενώ η nameList έχει στις ίδιες θέσεις τα ονόματα των μαθητών. Τι κάνεις σε κάθε αντιμετάθεση;
   - Αντιμεταθέτεις και τα ονόματα στις ίδιες θέσεις
   - Ταξινομείς στο τέλος και τη nameList αλφαβητικά
   - Τίποτα, η nameList ακολουθεί αυτόματα
   - Αντιμεταθέτεις τα ονόματα μόνο στο τελευταίο πέρασμα

## Ασκήσεις

1. Η λίστα A = [7, 3, 9, 1] ταξινομείται σε αύξουσα σειρά με τον αλγόριθμο του βιβλίου. Πώς είναι η λίστα μετά το πρώτο πέρασμα;
2. Στην ίδια λίστα A = [7, 3, 9, 1], πώς είναι η λίστα μετά το δεύτερο πέρασμα, και πόσες αντιμεταθέσεις έχουν γίνει ως τότε;
3. Ο αλγόριθμος του βιβλίου έκανε συνολικά 28 συγκρίσεις για να ταξινομήσει μια λίστα. Πόσα στοιχεία είχε η λίστα, και πόσα περάσματα έγιναν;
4. Η λίστα A = [2, 8, 5, 9] ταξινομείται σε φθίνουσα σειρά, με τη σύγκριση if A[j] > A[j - 1] και τα όρια του βιβλίου.
   α) Πώς είναι η λίστα μετά το πρώτο πέρασμα;
   β) Πόσες αντιμεταθέσεις γίνονται συνολικά;
5. Η λίστα A = [4, 6, 8, 18, 30, 50, 56, 68, 70, 3, 1] ταξινομείται με τη βελτιωμένη φυσαλίδα, την optimizedBubbleSort του μαθήματος.
   α) Πόσα περάσματα εκτελούνται;
   β) Πόσες συγκρίσεις γίνονται συνολικά;
   γ) Πόσες συγκρίσεις θα έκανε ο βασικός αλγόριθμος;
6. Ο αλγόριθμος του βιβλίου ταξινομεί σε αύξουσα σειρά 5 διαφορετικούς αριθμούς. Πόσες το πολύ αντιμεταθέσεις μπορεί να κάνει, και με ποια αρχική σειρά των αριθμών;

---

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