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

> Τα περάσματα, οι συγκρίσεις και οι αντιμεταθέσεις, η φθίνουσα σειρά, η σημαία και οι παράλληλοι πίνακες.

Πληροφορική, Γ΄ Λυκείου. https://www.akademio.gr/el/lyk-c/informatics/bubble-sort

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

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

## Ο αλγόριθμος του βιβλίου

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

*Διαδραστικό στη σελίδα: Ταξινόμηση φυσαλίδας σε αύξουσα σειρά*

Τρία πράγματα να κρατήσεις από τον κώδικα:

- Ο **εξωτερικός** βρόχος μετράει τα **περάσματα**. Είναι $n - 1$, από `i = 2` ως `i = n`.
- Ο **εσωτερικός** ξεκινά από το `n` και σταματά στο `i`. Κάθε πέρασμα είναι μία θέση πιο κοντό από το προηγούμενο.
- Η **αντιμετάθεση** θέλει τρεις εκχωρήσεις και μια βοηθητική μεταβλητή. Με δύο μόνο, `A[j-1] <- A[j]` και `A[j] <- A[j-1]`, χάνεται η μία τιμή.

> **Κλειδί**
>
> **Κάθε πέρασμα φέρνει το μικρότερο από τα αταξινόμητα στην πρώτη ελεύθερη θέση.**
>
> Επειδή ο εσωτερικός βρόχος πηγαίνει από το τέλος προς την αρχή, το μικρότερο στοιχείο «παρασύρεται» προς τα πάνω σε κάθε σύγκριση που κερδίζει. Μετά το πέρασμα `i`, οι θέσεις $1$ ως `i − 1` έχουν τις τελικές τους τιμές και δεν ξαναγγίζονται.
>
> Αυτό είναι το κλειδί για κάθε ερώτηση «πώς είναι ο πίνακας μετά το δεύτερο πέρασμα»: δεν χρειάζεται να μαντέψεις, μόνο να κάνεις τις συγκρίσεις με τη σειρά.

## Ένα πέρασμα τη φορά

Πάρε τον πίνακα $6, 3, 8, 2, 5$. Πριν πατήσεις, πες αν θα γίνει αντιμετάθεση.

*Διαδραστικό στη σελίδα: Φυσαλίδα στον πίνακα 6, 3, 8, 2, 5*

Και ο ίδιος κώδικας, να τρέχει στον υπολογιστή. Εδώ δεν σε ρωτά σε κάθε βήμα: κοίτα μόνο τη γραμμή που τυπώνει ο πίνακας στο τέλος κάθε περάσματος.

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

## Συγκρίσεις και αντιμεταθέσεις

Οι **συγκρίσεις** δεν εξαρτώνται από τα δεδομένα. Το πέρασμα `i = 2` κάνει $n - 1$, το επόμενο $n - 2$, και το τελευταίο μία:

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

Οι **αντιμεταθέσεις** εξαρτώνται. Σε ήδη ταξινομημένο πίνακα είναι μηδέν. Σε αντίστροφα ταξινομημένο είναι όσες και οι συγκρίσεις, $\dfrac{n(n-1)}{2}$.

Υπάρχει και ένας γρήγορος τρόπος να τις μετρήσεις χωρίς να εκτελέσεις τίποτα: κάθε αντιμετάθεση διορθώνει **ακριβώς ένα** ζεύγος στοιχείων που ήταν σε λάθος σειρά. Άρα οι αντιμεταθέσεις είναι όσα ζεύγη `(x, y)` υπάρχουν με το `x` πριν από το `y` και `x > y`.

> **Πρόσεχε**
>
> Η εκφώνηση ρωτά είτε για **συγκρίσεις** είτε για **αντιμεταθέσεις**, σχεδόν ποτέ για «βήματα». Διάβασε δύο φορές ποιο από τα δύο θέλει. Η απάντηση «$10$» για τον πίνακα $6, 3, 8, 2, 5$ είναι σωστή για τις συγκρίσεις και λάθος για τις αντιμεταθέσεις, που είναι $6$.

## Τρεις αλλαγές που ζητούνται

**Φθίνουσα σειρά.** Αλλάζει μόνο ο τελεστής της γραμμής 3: `ΑΝ A[j-1] < A[j] ΤΟΤΕ`. Τώρα σε κάθε πέρασμα ανεβαίνει στην αρχή το **μεγαλύτερο** από τα αταξινόμητα.

**Σημαία για πρόωρο τερματισμό.** Αν σε ένα πέρασμα δεν γίνει καμία αντιμετάθεση, ο πίνακας είναι ταξινομημένος και τα υπόλοιπα περάσματα περισσεύουν. Μια λογική μεταβλητή το καταγράφει, και ο εξωτερικός βρόχος γίνεται `ΜΕΧΡΙΣ_ΟΤΟΥ`:

*Διαδραστικό στη σελίδα: Φυσαλίδα με σημαία*

Η συνθήκη `i > n` χρειάζεται και εδώ: σε αντίστροφα ταξινομημένο πίνακα γίνεται αντιμετάθεση σε κάθε πέρασμα, και χωρίς αυτήν το `i` θα ξεπερνούσε το `n`.

**Μερική ταξινόμηση.** Αν θέλεις μόνο τα $3$ μικρότερα, αρκούν τρία περάσματα: `ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 4`. Μετά από αυτά, οι θέσεις $1$ ως $3$ είναι τελικές, και το υπόλοιπο του πίνακα σε όποια σειρά έτυχε.

## Παράλληλοι πίνακες

Στο Θέμα Δ ο πίνακας σπάνια είναι μόνος του. Έχεις τα ονόματα στο `ΟΝ` και τους βαθμούς στο `ΒΑΘ`, με το `ΟΝ[i]` και το `ΒΑΘ[i]` να αφορούν τον ίδιο μαθητή. Η σύγκριση γίνεται στο κριτήριο, αλλά **η αντιμετάθεση γίνεται και στους δύο πίνακες**, αλλιώς τα ονόματα χάνουν τους βαθμούς τους.

> **Θυμήσου**
>
> **Ένας παράλληλος πίνακας = μία αντιμετάθεση ακόμα.**
>
> Τρεις εκχωρήσεις για το `ΒΑΘ`, τρεις για το `ΟΝ`, με διαφορετική βοηθητική μεταβλητή για το καθένα, γιατί το ένα είναι αριθμός και το άλλο χαρακτήρες. Οι συμβολοσειρές συγκρίνονται αλφαβητικά, οπότε το ίδιο `ΑΝ ΟΝ[j-1] > ΟΝ[j] ΤΟΤΕ` ταξινομεί ονόματα.

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

`ΒΑΘ[j-1] < ΒΑΘ[j] Η (ΒΑΘ[j-1] = ΒΑΘ[j] ΚΑΙ ΟΝ[j-1] > ΟΝ[j])`

Το πρώτο μέρος πιάνει τον μικρότερο βαθμό που είναι πιο πάνω. Το δεύτερο, την ισοβαθμία με τα ονόματα ανάποδα.

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

### Παράδειγμα 1: Θέμα Β. Δίνεται ο πίνακας A με τιμές 4, 7, 1, 6, 3. Να γράψεις το περιεχόμενό του μετά από κάθε πέρασμα της φυσαλίδας του βιβλίου.

1. **Πέρασμα $i = 2$**, με `j` από $5$ ως $2$. Οι συγκρίσεις $(6, 3)$, $(1, 3)$, $(7, 1)$, $(4, 1)$ δίνουν τρεις αντιμεταθέσεις, και το $1$ ανεβαίνει στην αρχή.
2. *Διαδραστικό στη σελίδα: Ο πίνακας μετά από κάθε πέρασμα*
3. **Το τέταρτο πέρασμα δεν αλλάζει τίποτα.** Γράφεται όμως στην απάντηση: η εκφώνηση ζητά κάθε πέρασμα, και ο αλγόριθμος του βιβλίου το εκτελεί.

### Παράδειγμα 2: Πόσες συγκρίσεις και πόσες αντιμεταθέσεις κάνει η φυσαλίδα στον πίνακα 5, 1, 4, 2, 8, 3;

1. **Συγκρίσεις:** $n = 6$, άρα $\dfrac{6 \cdot 5}{2} = 15$. Ανεξάρτητα από τις τιμές.
2. **Αντιμεταθέσεις:** μετράς τα ζεύγη σε λάθος σειρά. Το $5$ είναι πριν από τα $1, 4, 2, 3$: τέσσερα. Το $4$ πριν από τα $2, 3$: δύο. Το $8$ πριν από το $3$: ένα. Τα $1$ και $2$: κανένα.
3. **Σύνολο $4 + 2 + 1 = 7$ αντιμεταθέσεις.** Αν εκτελέσεις τα πέντε περάσματα, θα βρεις το ίδιο: $3, 2, 1, 1, 0$.

### Παράδειγμα 3: Ποια αλλαγή χρειάζεται για φθίνουσα ταξινόμηση, και πώς γίνεται ο πίνακας 6, 3, 8, 2, 5 μετά το πρώτο πέρασμα;

1. **Αλλάζει μόνο η σύγκριση:** `ΑΝ A[j-1] < A[j] ΤΟΤΕ`. Οι βρόχοι μένουν ίδιοι.
2. **Πέρασμα $i = 2$:** $2 < 5$ ναι, πίνακας $6, 3, 8, 5, 2$. $8 < 5$ όχι. $3 < 8$ ναι, $6, 8, 3, 5, 2$. $6 < 8$ ναι, $8, 6, 3, 5, 2$.
3. **Το $8$, το μεγαλύτερο, είναι στην πρώτη θέση.** Πρόσεξε ότι το $2$ κατέβηκε στο τέλος με την πρώτη κιόλας σύγκριση, αλλά αυτό είναι σύμπτωση. Αυτό που εγγυάται κάθε πέρασμα είναι μόνο η θέση στην αρχή.

### Παράδειγμα 4: Η φυσαλίδα με σημαία εκτελείται στον πίνακα 2, 1, 3, 4, 5, 6. Πόσα περάσματα και πόσες συγκρίσεις κάνει, και πόσες θα έκανε χωρίς τη σημαία;

1. **Πρώτο πέρασμα:** πέντε συγκρίσεις, μία αντιμετάθεση, του $2$ με το $1$. Η σημαία γίνεται `ΑΛΗΘΗΣ`, άρα συνεχίζει.
2. **Δεύτερο πέρασμα:** τέσσερις συγκρίσεις, καμία αντιμετάθεση. Η σημαία μένει `ΨΕΥΔΗΣ` και ο βρόχος σταματά με `i = 4`.
3. **Δύο περάσματα, $5 + 4 = 9$ συγκρίσεις.** Χωρίς σημαία: πέντε περάσματα και $15$. Η σημαία κερδίζει μόνο όταν ο πίνακας είναι σχεδόν ταξινομημένος. Σε αντίστροφα ταξινομημένο πίνακα κάνει τις ίδιες $15$.

### Παράδειγμα 5: Από 10 χρόνους δρομέων στον πίνακα Χ θέλεις μόνο τους 3 καλύτερους, δηλαδή τους 3 μικρότερους. Πώς αλλάζεις τη φυσαλίδα και πόσες συγκρίσεις γλιτώνεις;

1. **Αρκούν τρία περάσματα.** Μετά το πέρασμα `i`, οι θέσεις $1$ ως `i − 1` είναι τελικές. Για τρεις τελικές θέσεις χρειάζεσαι `i` ως $4$: `ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 4`.
2. **Συγκρίσεις:** $9 + 8 + 7 = 24$. Η πλήρης ταξινόμηση θα έκανε $\dfrac{10 \cdot 9}{2} = 45$.
3. **Γλιτώνεις $21$.** Μετά τυπώνεις `Χ[1]`, `Χ[2]`, `Χ[3]`. Οι υπόλοιπες επτά θέσεις δεν είναι ταξινομημένες, και η εκφώνηση δεν τις ζητά.

### Παράδειγμα 6: Θέμα Δ. Οι πίνακες ΟΝ και ΒΑΘ έχουν τα ονόματα και τους βαθμούς 5 μαθητών. Να τους ταξινομήσεις φθίνουσα κατά βαθμό και, σε ισοβαθμία, αλφαβητικά, και να τυπώσεις τη λίστα.

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

   *Διαδραστικό στη σελίδα: Ταξινόμηση με δύο κριτήρια*
3. **Αποτέλεσμα:** Δήμος $20$, Ελένη $19$, Γιώργος $17$, Νίκος $17$, Βασίλης $15$. Ο Γιώργος μπήκε πριν από τον Νίκο μόνο χάρη στο δεύτερο σκέλος.
4. **Τα συνηθισμένα λάθη στη βαθμολόγηση:** αντιμετάθεση μόνο στο `ΒΑΘ`, μία κοινή βοηθητική μεταβλητή για αριθμό και όνομα, και παρενθέσεις που λείπουν από το δεύτερο σκέλος.

## Ερωτήσεις

1. Πόσες συγκρίσεις κάνει η φυσαλίδα του βιβλίου σε πίνακα $10$ στοιχείων;
   - $45$
   - $100$
   - $9$
   - εξαρτάται από τα δεδομένα
2. Σε πίνακα ήδη ταξινομημένο σε αύξουσα σειρά, η φυσαλίδα του βιβλίου κάνει:
   - όλες τις συγκρίσεις και καμία αντιμετάθεση
   - καμία σύγκριση και καμία αντιμετάθεση
   - μόνο το πρώτο πέρασμα και σταματά
   - όσες αντιμεταθέσεις και συγκρίσεις
3. Μετά το πέρασμα με $i = 4$, ποιες θέσεις του πίνακα έχουν σίγουρα την τελική τους τιμή;
   - οι θέσεις $1$ ως $3$
   - οι θέσεις $1$ ως $4$
   - οι τρεις τελευταίες θέσεις
   - μόνο η θέση $4$
4. Τι αλλάζεις στη φυσαλίδα του βιβλίου για φθίνουσα σειρά;
   - τη σύγκριση σε `A[j-1] < A[j]`
   - τον εσωτερικό βρόχο σε `ΜΕ_ΒΗΜΑ 1`
   - τον εξωτερικό σε `ΑΠΟ n ΜΕΧΡΙ 2`
   - τη σειρά των τριών εκχωρήσεων
5. Γιατί η αντιμετάθεση χρειάζεται τη μεταβλητή `temp`;
   - για να μη χαθεί η τιμή που γράφεται πρώτη
   - για να μετρηθούν οι αντιμεταθέσεις
   - για να κρατηθεί η σειρά των περασμάτων
   - γιατί η ΓΛΩΣΣΑ το απαιτεί συντακτικά
6. Ο εσωτερικός βρόχος της φυσαλίδας του βιβλίου είναι:
   - `ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1`
   - `ΓΙΑ j ΑΠΟ i ΜΕΧΡΙ n ΜΕ_ΒΗΜΑ -1`
   - `ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ 1 ΜΕ_ΒΗΜΑ -1`
   - `ΓΙΑ j ΑΠΟ 2 ΜΕΧΡΙ n ΜΕ_ΒΗΜΑ 1`
7. Στη φυσαλίδα με σημαία, ο εξωτερικός βρόχος σταματά όταν:
   - σε ένα πέρασμα δεν γίνει καμία αντιμετάθεση
   - σε ένα πέρασμα γίνει έστω μία αντιμετάθεση
   - βρεθεί το μικρότερο στοιχείο του πίνακα
   - η σημαία γίνει `ΑΛΗΘΗΣ` στην αρχή του περάσματος
8. Ταξινομείς τον `ΒΑΘ` και θέλεις τα ονόματα του `ΟΝ` να μείνουν με τους βαθμούς τους. Τι κάνεις;
   - κάθε αντιμετάθεση γίνεται και στους δύο πίνακες
   - ταξινομείς χωριστά πρώτα τον `ΒΑΘ` και μετά τον `ΟΝ`
   - συγκρίνεις και στους δύο πίνακες σε κάθε βήμα
   - τίποτα: τα ονόματα ακολουθούν μόνα τους
9. Πόσες αντιμεταθέσεις κάνει η φυσαλίδα στον πίνακα $3, 2, 1$;
   - $3$
   - $2$
   - $1$
   - $0$
10. Πόσα περάσματα κάνει η φυσαλίδα του βιβλίου, χωρίς σημαία, σε πίνακα $8$ στοιχείων;
   - $7$
   - $8$
   - $28$
   - εξαρτάται από τα δεδομένα

## Ασκήσεις

1. Πόσα περάσματα κάνει η φυσαλίδα του βιβλίου, χωρίς σημαία, σε πίνακα $9$ στοιχείων;
2. Ο πίνακας $9, 4, 7, 2, 8$ ταξινομείται σε αύξουσα σειρά με τη φυσαλίδα του βιβλίου. Ποια τιμή είναι στην πρώτη θέση μετά το πρώτο πέρασμα;
3. Πόσες συγκρίσεις κάνει η φυσαλίδα του βιβλίου σε πίνακα $12$ στοιχείων;
4. Πόσες αντιμεταθέσεις κάνει η φυσαλίδα για να ταξινομήσει σε αύξουσα σειρά τον πίνακα $4, 3, 1, 2$;
5. Η φυσαλίδα του βιβλίου ταξινομεί σε αύξουσα σειρά τον πίνακα $3, 6, 1, 8, 2$.
   α) Ποιος είναι ο πίνακας μετά το πρώτο πέρασμα;
   β) Πόσες συγκρίσεις γίνονται συνολικά;
   γ) Πόσες αντιμεταθέσεις γίνονται συνολικά;
6. Η γραμμή σύγκρισης της φυσαλίδας γίνεται `ΑΝ A[j-1] < A[j] ΤΟΤΕ` και εκτελείται στον πίνακα $2, 9, 4, 7, 5$.
   α) Ποιος είναι ο πίνακας μετά το πρώτο πέρασμα;
   β) Ποιος είναι ο πίνακας μετά το δεύτερο πέρασμα;
   γ) Πόσες αντιμεταθέσεις γίνονται συνολικά;
7. Η φυσαλίδα με σημαία (`ΜΕΧΡΙΣ_ΟΤΟΥ αλλαγή = ΨΕΥΔΗΣ Η i > n`) εκτελείται σε δύο πίνακες $8$ στοιχείων: τον Π1 $= 2, 3, 4, 5, 6, 7, 8, 1$ και τον Π2 $= 8, 1, 2, 3, 4, 5, 6, 7$.
   α) Πόσες συγκρίσεις γίνονται στον Π1;
   β) Πόσες συγκρίσεις γίνονται στον Π2;
   γ) Ποια είναι η τιμή του `i` στο τέλος, για τον Π2;
8. Ο πίνακας ΧΡ έχει $8$ χρόνους δρομέων, ταξινομημένους από τον μεγαλύτερο προς τον μικρότερο. Ταξινομείται σε αύξουσα σειρά με τη φυσαλίδα του βιβλίου, χωρίς σημαία.
   α) Πόσες συγκρίσεις γίνονται;
   β) Πόσες αντιμεταθέσεις γίνονται;
   γ) Ποια γραμμή ΓΙΑ, για τον εξωτερικό βρόχο, φέρνει στη θέση τους μόνο τους $3$ καλύτερους;
   δ) Πόσες συγκρίσεις κάνει τότε;

---

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