Μετάβαση στο περιεχόμενο

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

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

40 λεπτά

Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 1 ενότητα

Στις Πανελλήνιες2026 Β ·2026 Δ ·2025 Δ ·2023 επαν. Δ ·2023 Δ ·2022 επαν. Δ ·2022 Δ ·2021 Δ ·2020 Δ

Θα μάθεις να

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

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

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

Ταξινόμηση φυσαλίδας σε αύξουσα σειρά
  1. ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ n
  2. σημειωμένη γραμμή: ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
  3. σημειωμένη γραμμή: ΑΝ A[j-1] > A[j] ΤΟΤΕ
  4. temp ← A[j-1]
  5. A[j-1] ← A[j]
  6. A[j] ← temp
  7. ΤΕΛΟΣ_ΑΝ
  8. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  9. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

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

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

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

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

Φυσαλίδα στον πίνακα 6, 3, 8, 2, 5

Κάθε γραμμή είναι μία σύγκριση της γραμμής 3. Πες πρώτα «ναι» ή «όχι» και μετά πάτα. Πρόσεξε το 2: στο πρώτο πέρασμα ανεβαίνει από την τέταρτη θέση στην πρώτη.

ΒήμαijA[j-1] > A[j]Αντιμετάθεση;Πίνακας
Ζωντανή ενημέρωση

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

Ο πίνακας στο τέλος κάθε περάσματος

Η γραμμή 9 τυπώνει το i και τον πίνακα μετά από κάθε πέρασμα. Σύγκρινε με τον πίνακα τιμών πιο πάνω.

  1. ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ n
  2. ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
  3. ΑΝ A[j-1] > A[j] ΤΟΤΕ
  4. temp ← A[j-1]
  5. A[j-1] ← A[j]
  6. A[j] ← temp
  7. ΤΕΛΟΣ_ΑΝ
  8. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  9. ΓΡΑΨΕ i, ':', A[1], A[2], A[3], A[4], A[5]
  10. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ξεκινάμε με A = [6, 3, 8, 2, 5], n = 5.

Μεταβλητές

A
= [6, 3, 8, 2, 5]
n
= 5

Έξοδος

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

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

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

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

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

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

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

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

Φυσαλίδα με σημαία

Ο πίνακας 3, 1, 2, 5, 4, 6 είναι σχεδόν ταξινομημένος. Μέτρα τα περάσματα: στο τρίτο δεν γίνεται καμία αντιμετάθεση, η αλλαγή μένει ΨΕΥΔΗΣ, και ο βρόχος σταματά.

  1. i ← 2
  2. ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
  3. αλλαγή ← ΨΕΥΔΗΣ
  4. ΓΙΑ j ΑΠΟ n ΜΕΧΡΙ i ΜΕ_ΒΗΜΑ -1
  5. ΑΝ A[j-1] > A[j] ΤΟΤΕ
  6. temp ← A[j-1]
  7. A[j-1] ← A[j]
  8. A[j] ← temp
  9. αλλαγή ← ΑΛΗΘΗΣ
  10. ΤΕΛΟΣ_ΑΝ
  11. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  12. i ← i + 1
  13. ΜΕΧΡΙΣ_ΟΤΟΥ αλλαγή = ΨΕΥΔΗΣ Η i > n

Ξεκινάμε με A = [3, 1, 2, 5, 4, 6], n = 6.

Μεταβλητές

A
= [3, 1, 2, 5, 4, 6]
n
= 6

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

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

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

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

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

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

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

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

Παράδειγμα 1

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

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

Παράδειγμα 2

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

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

Παράδειγμα 3

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

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

Παράδειγμα 4

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

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

Παράδειγμα 5

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

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

Παράδειγμα 6

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

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

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Πόσες συγκρίσεις κάνει η φυσαλίδα του βιβλίου σε πίνακα 1010 στοιχείων;

Ασκήσεις

ΒασικήΆσκηση 1 από 8

Πόσα περάσματα κάνει η φυσαλίδα του βιβλίου, χωρίς σημαία, σε πίνακα 99 στοιχείων;

Τα κατάφερες;

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

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;