Το θέμα Γ των πανελλαδικών της ΑΕΠΠ και η ταξινόμηση φυσαλίδας (bubble sort)

Το πιο “δύσκολο” σημείο του θέματος Γ των φετινών πανελλαδικών (2017) ήταν κατά κοινή ομολογία η ιδιαίτερη μορφή ταξινόμησης η οποία ζητήθηκε στο υποερώτημα Γ3. Τέτοιου είδους προβλήματα (ταξινόμησης) γίνονται πολύ εύκολα αν θεωρήσουμε τον ακόλουθο γενικό ορισμό της ταξινόμησης:

α) Θεωρείστε έναν μονοδιάστατο πίνακα Α[μ] τύπου Τ.

β) Θεωρείστε μια συνάρτηση Διάταξη(χ1, χ2, …) λογικού τύπου με τουλάχιστον δύο τυπικές παραμέτρους (οι δύο πρώτες τύπου Τ), η οποία ορίζεται στην γλώσσα της ΑΕΠΠ για κάθε τιμή των παραμέτρων χ1, χ2, οι οποίες παίρνουν τιμές αποκλειστικά από τα στοιχεία του πίνακα Α. Θεωρείστε ότι για την συνάρτηση αυτή ισχύει, για κάποιες παραμέτρους π1, π2, π3:

i) Αν ισχύει Διάταξη(π1,π2,…) = Αληθής και Διάταξη(π2,π1,…) = Αληθής, τότε ισχύει π1=π2

ii) Αν ισχύει Διάταξη(π1,π2,…) = Αληθής και Διάταξη(π2, π3,…) = Αληθής, τότε ισχύει Διάταξη(π1,π3,…) = Αληθής

Σημειώνεται ότι η σημασία της έκφρασης Αν…, τότε … στα i) και ii) αμέσως παραπάνω δεν έχει καμία σχέση με την “δομή επιλογής” της Γλώσσας της ΑΕΠΠ, αλλά είναι η “λογική συνεπαγωγή” (γνωστή ίσως και από τα Μαθηματικά), η οποία συμβολίζεται συνήθως με “. Για κάθε ζεύγος προτάσεων (λογικών εκφράσεων) Α, Β ο πίνακας τιμών της λογικής συνεπαγωγής είναι:

Παρατηρούμε, δηλαδή, ότι η λογική συνεπαγωγή Α → Β είναι Ψευδής μόνο όταν η Α είναι Αληθής και η Β είναι Ψευδής.

Οπότε, η συνάρτηση Συνεπάγεται(Α,Β) μπορεί να κατασκευαστεί στην Γλώσσα της ΑΕΠΠ:

Μ’ αυτόν τον τρόπο, θεωρώντας τις λογικές μεταβλητές Α, Β, Γ και Δ οι παραπάνω δύο προϋποθέσεις i), ii) γράφονται (και απαιτείται να είναι Αληθείς) στην Γλώσσα της ΑΕΠΠ:

i) Συνεπάγεται(Α, Β), όπου:

Α <- Διάταξη(π1,π2,…) KAI Διάταξη(π2,π1,…) και

Β <- π1 = π2

ii) Συνεπάγεται(Γ, Δ), όπου

Γ <- Διάταξη(π1,π2,…) ΚΑΙ Διάταξη(π2, π3,…) και

Δ<- Διάταξη(π1,π3,…)

Ορισμός: ο πίνακας Α[μ] είναι ταξινομημένος σύμφωνα με την συνάρτηση Διάταξη(π1,π2,…) όταν για κάθε ζευγάρι διαδοχικών στοιχείων του πίνακα με δείκτες i και i -1, με 2i≤μ, ισχύει Διάταξη(Α[i-1], Α[i],…) = Αληθής.

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

Συνεπάγεται από τον παραπάνω ορισμό ότι:

Ο πίνακας Α[μ] δεν είναι ταξινομημένος σύμφωνα με την συνάρτηση Διάταξη(π1,π2,…) όταν υπάρχει (τουλάχιστον ένα) ζευγάρι διαδοχικών στοιχείων του πίνακα με δείκτες i και i -1, με 2≤i≤μ, τέτοιο ώστε Διάταξη(Α[i-1], Α[i],…) = Ψευδής.

Θεώρημα: Ο πίνακας Α μπορεί να ταξινομηθεί σύμφωνα με την συνάρτηση Διάταξη(π1,π2,…) με τον παρακάτω αλγόριθμο, τον οποίο θα ονομάζαμε “γενικό αλγόριθμο ταξινόμησης φυσαλίδας”:

Όπου η διαδικασία ΑΝΤΙΜΕΤΑΘΕΣΕ ορίζεται ως εξής, για κάθε τύπο Τ δεδομένων της Γλώσσας:

Για παράδειγμα, αν θεωρήσουμε ότι ο πίνακας Α είναι πίνακας ακεραίων, τότε η συνάρτηση Διάταξη η οποία αντιστοιχεί στην γνωστή αύξουσα ταξινόμηση ακεραίων του πίνακα είναι:

Ας δούμε τώρα όμως την περίπτωση του υποερωτήματος Γ3. Εύκολα μπορούμε να διαπιστώσουμε ότι η συνάρτηση Διάταξη(χ1,χ2,…) η οποία αντιστοιχεί στην συγκεκριμένη περίπτωση είναι:

Και ο γενικός αλγόριθμος φυσαλίδας για αυτήν την περίπτωση:

Ένα επιπλέον παράδειγμα:

Δίνεται πίνακας χαρακτήρων Π[100] με κάθε στοιχείο να παίρνει μία από τις ακόλουθες τρεις δυνατές τιμές: “Πρώτος”, “Δεύτερος”, “Τρίτος”. Να κατασκευάσετε τμήμα προγράμματος, το οποίο να αναδιατάσσει τον πίνακα Π έτσι ώστε όλα τα στοιχεία με την τιμή “Πρώτος” να βρίσκονται στην αρχή του πίνακα, να ακολουθούν όλα τα στοιχεία με την τιμή “Δεύτερος” και στο τέλος όλα τα στοιχεία με την τιμή “Τρίτος”.

Θεωρούμε την παρακάτω συνάρτηση Διάταξη(χ1,χ2):

Και την χρησιμοποιούμε στον “γενικό αλγόριθμο ταξινόμησης φυσαλίδας”:

Φυσικά, όπως σε κάθε περίπτωση, μπορούμε να μην εμφανίσουμε “ρητά” την συνάρτηση Διάταξη:

Γιώργος Μπουγιούκας

πηγή: https://gbougioukas.wordpress.com/2017/08/09/aepp_2017_c/