Ταξινόμηση φυσαλίδας βήμα βήμα
Τα περάσματα, οι συγκρίσεις και οι αντιμεταθέσεις, η φθίνουσα σειρά, η σημαία και οι παράλληλοι πίνακες.
40 λεπτά
Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 1 ενότητα
Στις Πανελλήνιες2026 Β ·2026 Δ ·2025 Δ ·2023 επαν. Δ ·2023 Δ ·2022 επαν. Δ ·2022 Δ ·2021 Δ ·2020 Δ
Θα μάθεις να
- Να εκτελείς την ταξινόμηση φυσαλίδας του βιβλίου και να γράφεις τον πίνακα μετά από κάθε πέρασμα.
- Να μετράς συγκρίσεις και αντιμεταθέσεις, και να ξεχωρίζεις ποιο από τα δύο εξαρτάται από τα δεδομένα.
- Να προσαρμόζεις τον αλγόριθμο: φθίνουσα σειρά, σημαία για πρόωρο τερματισμό, μερική ταξινόμηση.
- Να ταξινομείς παράλληλους πίνακες με ένα ή δύο κριτήρια.
Ο αλγόριθμος του βιβλίου
Η φυσαλίδα συγκρίνει γειτονικά στοιχεία και τα αντιμεταθέτει όταν είναι σε λάθος σειρά. Στη ΓΛΩΣΣΑ, όπως τη γράφει το βιβλίο, ο εσωτερικός βρόχος πηγαίνει ανάποδα: από το τέλος του πίνακα προς την αρχή.
ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ n- σημειωμένη γραμμή:
ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1 - σημειωμένη γραμμή:
ΑΝ A[j-1] > A[j] ΤΟΤΕ temp ← A[j-1]A[j-1] ← A[j]A[j] ← tempΤΕΛΟΣ_ΑΝΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Τρία πράγματα να κρατήσεις από τον κώδικα:
- Ο εξωτερικός βρόχος μετράει τα περάσματα. Είναι , από
i = 2ωςi = n. - Ο εσωτερικός ξεκινά από το
nκαι σταματά στοi. Κάθε πέρασμα είναι μία θέση πιο κοντό από το προηγούμενο. - Η αντιμετάθεση θέλει τρεις εκχωρήσεις και μια βοηθητική μεταβλητή. Με δύο μόνο,
A[j-1] <- A[j]καιA[j] <- A[j-1], χάνεται η μία τιμή.
Ένα πέρασμα τη φορά
Πάρε τον πίνακα . Πριν πατήσεις, πες αν θα γίνει αντιμετάθεση.
Και ο ίδιος κώδικας, να τρέχει στον υπολογιστή. Εδώ δεν σε ρωτά σε κάθε βήμα: κοίτα μόνο τη γραμμή που τυπώνει ο πίνακας στο τέλος κάθε περάσματος.
Συγκρίσεις και αντιμεταθέσεις
Οι συγκρίσεις δεν εξαρτώνται από τα δεδομένα. Το πέρασμα i = 2 κάνει , το επόμενο , και το τελευταίο μία:
Οι αντιμεταθέσεις εξαρτώνται. Σε ήδη ταξινομημένο πίνακα είναι μηδέν. Σε αντίστροφα ταξινομημένο είναι όσες και οι συγκρίσεις, .
Υπάρχει και ένας γρήγορος τρόπος να τις μετρήσεις χωρίς να εκτελέσεις τίποτα: κάθε αντιμετάθεση διορθώνει ακριβώς ένα ζεύγος στοιχείων που ήταν σε λάθος σειρά. Άρα οι αντιμεταθέσεις είναι όσα ζεύγη (x, y) υπάρχουν με το x πριν από το y και x > y.
Τρεις αλλαγές που ζητούνται
Φθίνουσα σειρά. Αλλάζει μόνο ο τελεστής της γραμμής 3: ΑΝ A[j-1] < A[j] ΤΟΤΕ. Τώρα σε κάθε πέρασμα ανεβαίνει στην αρχή το μεγαλύτερο από τα αταξινόμητα.
Σημαία για πρόωρο τερματισμό. Αν σε ένα πέρασμα δεν γίνει καμία αντιμετάθεση, ο πίνακας είναι ταξινομημένος και τα υπόλοιπα περάσματα περισσεύουν. Μια λογική μεταβλητή το καταγράφει, και ο εξωτερικός βρόχος γίνεται ΜΕΧΡΙΣ_ΟΤΟΥ:
Η συνθήκη i > n χρειάζεται και εδώ: σε αντίστροφα ταξινομημένο πίνακα γίνεται αντιμετάθεση σε κάθε πέρασμα, και χωρίς αυτήν το i θα ξεπερνούσε το n.
Μερική ταξινόμηση. Αν θέλεις μόνο τα μικρότερα, αρκούν τρία περάσματα: ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 4. Μετά από αυτά, οι θέσεις ως είναι τελικές, και το υπόλοιπο του πίνακα σε όποια σειρά έτυχε.
Παράλληλοι πίνακες
Στο Θέμα Δ ο πίνακας σπάνια είναι μόνος του. Έχεις τα ονόματα στο ΟΝ και τους βαθμούς στο ΒΑΘ, με το ΟΝ[i] και το ΒΑΘ[i] να αφορούν τον ίδιο μαθητή. Η σύγκριση γίνεται στο κριτήριο, αλλά η αντιμετάθεση γίνεται και στους δύο πίνακες, αλλιώς τα ονόματα χάνουν τους βαθμούς τους.
Με δύο κριτήρια, π.χ. «φθίνουσα κατά βαθμό και, σε ισοβαθμία, αλφαβητικά», η συνθήκη λέει πότε ένα ζεύγος είναι σε λάθος σειρά:
ΒΑΘ[j-1] < ΒΑΘ[j] Η (ΒΑΘ[j-1] = ΒΑΘ[j] ΚΑΙ ΟΝ[j-1] > ΟΝ[j])
Το πρώτο μέρος πιάνει τον μικρότερο βαθμό που είναι πιο πάνω. Το δεύτερο, την ισοβαθμία με τα ονόματα ανάποδα.
Παραδείγματα
Παράδειγμα 1
Θέμα Β. Δίνεται ο πίνακας A με τιμές 4, 7, 1, 6, 3. Να γράψεις το περιεχόμενό του μετά από κάθε πέρασμα της φυσαλίδας του βιβλίου.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Πέρασμα , με
jαπό ως . Οι συγκρίσεις , , , δίνουν τρεις αντιμεταθέσεις, και το ανεβαίνει στην αρχή.Το τέταρτο πέρασμα δεν αλλάζει τίποτα. Γράφεται όμως στην απάντηση: η εκφώνηση ζητά κάθε πέρασμα, και ο αλγόριθμος του βιβλίου το εκτελεί.
Παράδειγμα 2
Πόσες συγκρίσεις και πόσες αντιμεταθέσεις κάνει η φυσαλίδα στον πίνακα 5, 1, 4, 2, 8, 3;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Συγκρίσεις: , άρα . Ανεξάρτητα από τις τιμές.
Αντιμεταθέσεις: μετράς τα ζεύγη σε λάθος σειρά. Το είναι πριν από τα : τέσσερα. Το πριν από τα : δύο. Το πριν από το : ένα. Τα και : κανένα.
Σύνολο αντιμεταθέσεις. Αν εκτελέσεις τα πέντε περάσματα, θα βρεις το ίδιο: .
Παράδειγμα 3
Ποια αλλαγή χρειάζεται για φθίνουσα ταξινόμηση, και πώς γίνεται ο πίνακας 6, 3, 8, 2, 5 μετά το πρώτο πέρασμα;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Αλλάζει μόνο η σύγκριση:
ΑΝ A[j-1] < A[j] ΤΟΤΕ. Οι βρόχοι μένουν ίδιοι.Πέρασμα : ναι, πίνακας . όχι. ναι, . ναι, .
Το , το μεγαλύτερο, είναι στην πρώτη θέση. Πρόσεξε ότι το κατέβηκε στο τέλος με την πρώτη κιόλας σύγκριση, αλλά αυτό είναι σύμπτωση. Αυτό που εγγυάται κάθε πέρασμα είναι μόνο η θέση στην αρχή.
Παράδειγμα 4
Η φυσαλίδα με σημαία εκτελείται στον πίνακα 2, 1, 3, 4, 5, 6. Πόσα περάσματα και πόσες συγκρίσεις κάνει, και πόσες θα έκανε χωρίς τη σημαία;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Πρώτο πέρασμα: πέντε συγκρίσεις, μία αντιμετάθεση, του με το . Η σημαία γίνεται
ΑΛΗΘΗΣ, άρα συνεχίζει.Δεύτερο πέρασμα: τέσσερις συγκρίσεις, καμία αντιμετάθεση. Η σημαία μένει
ΨΕΥΔΗΣκαι ο βρόχος σταματά μεi = 4.Δύο περάσματα, συγκρίσεις. Χωρίς σημαία: πέντε περάσματα και . Η σημαία κερδίζει μόνο όταν ο πίνακας είναι σχεδόν ταξινομημένος. Σε αντίστροφα ταξινομημένο πίνακα κάνει τις ίδιες .
Παράδειγμα 5
Από 10 χρόνους δρομέων στον πίνακα Χ θέλεις μόνο τους 3 καλύτερους, δηλαδή τους 3 μικρότερους. Πώς αλλάζεις τη φυσαλίδα και πόσες συγκρίσεις γλιτώνεις;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Αρκούν τρία περάσματα. Μετά το πέρασμα
i, οι θέσεις ωςi − 1είναι τελικές. Για τρεις τελικές θέσεις χρειάζεσαιiως :ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 4.Συγκρίσεις: . Η πλήρης ταξινόμηση θα έκανε .
Γλιτώνεις . Μετά τυπώνεις
Χ[1],Χ[2],Χ[3]. Οι υπόλοιπες επτά θέσεις δεν είναι ταξινομημένες, και η εκφώνηση δεν τις ζητά.
Παράδειγμα 6
Θέμα Δ. Οι πίνακες ΟΝ και ΒΑΘ έχουν τα ονόματα και τους βαθμούς 5 μαθητών. Να τους ταξινομήσεις φθίνουσα κατά βαθμό και, σε ισοβαθμία, αλφαβητικά, και να τυπώσεις τη λίστα.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η συνθήκη λάθους σειράς έχει δύο σκέλη: μικρότερος βαθμός πιο πάνω, ή ίσος βαθμός με όνομα που έρχεται αλφαβητικά μετά.
Η αντιμετάθεση γίνεται και στους δύο πίνακες, με δύο βοηθητικές μεταβλητές.
Αποτέλεσμα: Δήμος , Ελένη , Γιώργος , Νίκος , Βασίλης . Ο Γιώργος μπήκε πριν από τον Νίκο μόνο χάρη στο δεύτερο σκέλος.
Τα συνηθισμένα λάθη στη βαθμολόγηση: αντιμετάθεση μόνο στο
ΒΑΘ, μία κοινή βοηθητική μεταβλητή για αριθμό και όνομα, και παρενθέσεις που λείπουν από το δεύτερο σκέλος.
Πολλαπλή επιλογή
Ασκήσεις
Πόσα περάσματα κάνει η φυσαλίδα του βιβλίου, χωρίς σημαία, σε πίνακα στοιχείων;
Τα κατάφερες;
- Να εκτελείς την ταξινόμηση φυσαλίδας του βιβλίου και να γράφεις τον πίνακα μετά από κάθε πέρασμα.
- Να μετράς συγκρίσεις και αντιμεταθέσεις, και να ξεχωρίζεις ποιο από τα δύο εξαρτάται από τα δεδομένα.
- Να προσαρμόζεις τον αλγόριθμο: φθίνουσα σειρά, σημαία για πρόωρο τερματισμό, μερική ταξινόμηση.
- Να ταξινομείς παράλληλους πίνακες με ένα ή δύο κριτήρια.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.