Πληροφορική (Γενικό Λύκειο)
Κατεβάστε σε μορφή PDF
 3 ώρες

Ταξινόμηση στοιχείων μονοδιάστατου πίνακα

15 λεπτά

Ο αλγόριθμος ταξινόμησης φυσαλίδας

Φύλλα Εργασίας

Με την ολοκλήρωση της 2ης φάσης και την ανάπτυξη του αλγορίθμου Α10, έχουμε επιτύχει την ανάπτυξη ενός αλγορίθμου ταξινόμησης των στοιχείων ενός πίνακα κατά αύξουσα διάταξη. Επιπλέον έχουμε αναδείξει για ποιό λόγο ή λόγους η εξωτερική εντολή επανάληψης χρειάστηκε να εκτελεστεί 4 φορές για την ταξινόμηση των στοιχείων ενός πίνακα 5 στοιχείων ή ακόμα σε ποιες περιπτώσεις μπορεί η εξωτερική επανάληψη να εκτελεστεί λιγότερες από 4 φορές. Από τις δραστηριότητες που έχουμε ήδη υλοποιήσει έχει φανεί ότι σε κάθε εκτέλεση της εξωτερικής επανάληψης ένα στοιχείο του πίνακα διατάσσεται σε σχέση με τα υπόλοιπα. Έτσι, για τα 5 στοιχεία του πίνακα χρειάστηκαν 4 περάσματα για να επιτευχθεί η ταξινόμησή του. Αν θέλαμε να βάλουμε σε μία σειρά διάταξης λιγότερα στοιχεία, τότε θα πραγματοποιούσαμε λιγότερα περάσματα (π.χ. για να βάλουμε σε σειρά διάταξης 3 από τα 5 στοιχεία του πίνακα σε σχέση με τα υπόλοιπα, θα πραγματοποιούσαμε 3 περάσματα). Συνεπώς μόνο στην περίπτωση που θέλουμε να ταξινομήσουμε όλο τον πίνακα πραγματοποιούμε ένα πέρασμα λιγότερο. Σε κάθε άλλη περίπτωση πραγματοποιούμε τόσα περάσματα όσα και τα στοιχεία που θέλουμε να διατάξουμε σε σχέση με τα υπόλοιπα.

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

Έτσι, το ΠΡΟΓΡΑΜΜΑ Α10 μπορεί να βελτιωθεί ώστε η αρχική και η τελική τιμή της εξωτερικής εντολής επανάληψης να έχουν τις ίδιες τιμές με την τελική και αρχική τιμή της εσωτερικής εντολής επανάληψης αντίστοιχα (ΠΡΟΓΡΑΜΜΑ Α11).

Στο τρίτο φύλλο εργασίας (fe3.docx) εκτελούμε με τη βοήθεια του λογισμικού το ΠΡΟΓΡΑΜΜΑ Α10 και το ΠΡΟΓΡΑΜΜΑ Α11 και αναγνωρίζουμε τι συμβαίνει (Δραστηριότητα ΔΕ10). Στη συνέχεια με την εικονική εκτέλεση του προγράμματος Α11, είναι πιθανό να καταδείξουμε ότι ο αλγόριθμος που έχουμε αναπτύξει πραγματοποιεί περιττούς ελέγχους. Πιο συγκεκριμένα με την εικονική εκτέλεση θα μπορέσουμε να περιγράψουμε ότι όταν ολοκληρωθεί μία φορά η εκτέλεση της εσωτερικής επανάληψης, το μικρότερο στοιχείο θα τοποθετηθεί στην κορυφή του πίνακα. Κατά συνέπεια όταν εκτελεστεί η εξωτερική επανάληψη δεύτερη φορά, δεν χρειάζεται η εσωτερική επανάληψη να ελέγξει και το πρώτο στοιχείο του πίνακα, αφού αυτό έχει ήδη τοποθετηθεί στη σωστή θέση. Ομοίως όταν εκτελεστεί η εξωτερική επανάληψη τρίτη φορά, η εσωτερική επανάληψη δεν χρειάζεται να ελέγξει τα στοιχεία της πρώτης και δεύτερης θέσης του πίνακα αφού έχουν ήδη τοποθετηθεί στη σωστή θέση κ.ο.κ. Για το λόγο αυτό, είναι σημαντικό να προσδιορίσουμε την ανάγκη καθορισμού του πλήθους των επαναλήψεων της εσωτερικής επανάληψης από το πλήθος των στοιχείων που έχουν ήδη τοποθετηθεί στη σωστή θέση διάταξης. Με την χρήση του δείκτη της εξωτερικής επανάληψης (έστω i) μπορεί να επιτευχθεί η εξάλειψη των περιττών ελέγχων (Δραστηριότητα ΔΕ11). Η μεταβλητή i αποτελεί την τελική τιμή της εσωτερικής επανάληψης, μιας και στον πίνακα των 5 στοιχείων:

Κατά την πρώτη εκτέλεση της εξωτερικής επανάληψης η εσωτερική επανάληψη χρειάζεται να εκτελεστεί 4 φορές (από 5 μέχρι 2, όπου 2 η τιμή του i), ώστε να τοποθετηθεί το μικρότερο στοιχείο στην κορυφή του πίνακα.

Κατά την δεύτερη εκτέλεση της εξωτερικής επανάληψης η εσωτερική επανάληψη εκτελείται 3 φορές (από 5 μέχρι 3, όπου 3 η τιμή του i), ώστε να τοποθετηθεί το δεύτερο μικρότερο στοιχείο στη δεύτερη θέση του πίνακα.

Κατά την τρίτη εκτέλεση της εξωτερικής επανάληψης η εσωτερική επανάληψη εκτελείται 2 φορές (από 5 μέχρι 4, όπου 4 η τιμή του i), ώστε να τοποθετηθεί το τρίτο μικρότερο στοιχείο στην τρίτη θέση του πίνακα.

Κατά την τέταρτη εκτέλεση της εξωτερικής επανάληψης η εσωτερική επανάληψη εκτελείται 1 φορά (από 5 μέχρι 5, όπου 5 η τιμή του i), ώστε να τοποθετηθεί το τέταρτο μικρότερο στοιχείο στην τέταρτη θέση του πίνακα και το μεγαλύτερο στοιχείο να μείνει στην τελευταία θέση του πίνακα.

Επομένως, μπορούμε να γενικεύσουμε τον αλγόριθμο για έναν πίνακα οποιουδήποτε πλήθους στοιχείων (Δραστηριότητα ΔΕ11).

Στη συνέχεια είναι χρήσιμο να προσδιορίσουμε τον τρόπο υλοποίησης του αλγόριθμου της ταξινόμησης των στοιχείων του πίνακα κατά φθίνουσα διάταξη (Δραστηριότητα ΔΕ11), αλλά και να συσχετίζουμε τον αλγόριθμο της ταξινόμησης φυσαλίδας με τον αλγόριθμο ταξινόμησης που τοποθετεί τη σωστή τιμή (μικρότερη ή μεγαλύτερη) στο τελευταίο στοιχείο του πίνακα (Δραστηριότητα ΔΕ12).

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

Η Δραστηριότητα ΔΣ13 είναι για εργασία στο σπίτι.

Προγράμματα δραστηριότητας ΔΕ10

Πρόγραμμα ταξινόμησης με τη μέθοδο της φυσαλίδας

Αλγόριθμος ταξινόμησης που τοποθετεί τη σωστή τιμή (μικρότερη ή μεγαλύτερη) στο τελευταίο στοιχείο του πίνακα (ΔΕ12)

Δημιουργός Σεναρίου: ΣΠΥΡΙΔΩΝ ΔΟΥΚΑΚΗΣ (Εκπαιδευτικός)
Έλεγχος Σεναρίου με τα Προγράμματα Σπουδών: ΚΩΤΣΑΚΗΣ ΣΤΑΥΡΟΣ (Σχολικός Σύμβουλος)
Έλεγχος Επιστημονικής Επάρκειας Σεναρίου: ΒΕΡΥΚΙΟΣ ΒΑΣΙΛΕΙΟΣ (Συντονιστής)