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

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

Γενική περιγραφή περιεχομένου: 

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

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

Δοθέντων των στοιχείων a1, a2, …, an η ταξινόμηση συνίσταται στη μετάθεση της θέσης των στοιχείων ώστε να τοποθετούνται σε μια σειρά ak1, ak2, …, akn, προκειμένου δοθείσης μιας συνάρτησης διάταξης f, να ισχύει: f(ak1) ≤ f(ak2) ≤ … ≤ f(akn). Ο ορισμός αφορά την ταξινόμηση των στοιχείων σε αύξουσα τάξη. Για φθίνουσα ταξινόμηση των στοιχείων η συνάρτηση διάταξης τροποποιείται ως εξής: f(ak1) ≥ f(ak2) ≥ …≥ f(akn).

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

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

Το ψηφιακό σενάριο θα υλοποιηθεί εξ ολοκλήρου στο σχολικό εργαστήριο πληροφορικής και εφαρμογών ηλεκτρονικών υπολογιστών (ΣΕΠΕΗΥ). Οι μαθητές θα εργαστούν σε ομάδες των δύο ατόμων (ζεύγη), όπου κάθε ζεύγος θα χρησιμοποιεί έναν υπολογιστή, ώστε να ευνοηθεί η αλληλεπίδραση μεταξύ των μαθητών. Το σενάριο λαμβάνει υπόψη του τις πραγματικές συνθήκες διεξαγωγής του μαθήματος ώστε να είναι ρεαλιστικά πραγματοποιήσιμο στον προβλεπόμενο χρόνο.

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

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

Η επίτευξη των στόχων θα επιχειρηθεί με μία αλληλουχία δραστηριοτήτων που θα λάβουν χώρα στο ΣΕΠΕΗΥ, όπου οι μαθητές θα εργαστούν στον υπολογιστή με το λογισμικό «Ο Διερμηνευτής της ΓΛΩΣΣΑΣ», αναπτύσσοντας τμήματα αλγορίθμου σε ΓΛΩΣΣΑ, τα οποία θα οδηγήσουν μέσω μιας σκαλωσιάς μάθησης στην ανάπτυξη αλγορίθμων ταξινόμησης όπως: του αλγόριθμου ταξινόμησης φυσαλίδας ή ευθείας εισαγωγής, του αλγόριθμου ταξινόμησης με επιλογή και του αλγορίθμου ταξινόμησης με παρεμβολή ή ευθείας ανταλλαγής. Οι μαθητές θα προσεγγίσουν το θέμα μέσα από κατάλληλα εργαλεία συγγραφής και παρακολούθησης της εκτέλεσης αλγορίθμων σε κατάλληλη γλώσσα προγραμματισμού. Επιπλέον, με τη χρήση του πίνακα θα επιχειρηθεί η οπτικοποίηση του αλγορίθμου, ενώ έχει αναπτυχθεί και ένα ενδιαφέρον οπτικοακουστικό υλικό που παρουσιάζει μέσω κατάλληλων εικονικών αναπαραστάσεων τη διαδικασία ταξινόμησης. Τέλος, οι μαθητές εργαζόμενοι στα φύλλα εργασίας τους, έχουν την ευκαιρία να χρησιμοποιήσουν συμβολικές αναπαραστάσεις.

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

Εκπαιδευτικό Πρόβλημα: 

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

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

Δοθέντων των στοιχείων a1, a2, …, an η ταξινόμηση συνίσταται στη μετάθεση της θέσης των στοιχείων ώστε να τοποθετούνται σε μια σειρά ak1, ak2, …, akn, προκειμένου δοθείσης μιας συνάρτησης διάταξης f, να ισχύει: f(ak1) ≤ f(ak2) ≤ … ≤ f(akn). Ο ορισμός αφορά την ταξινόμηση των στοιχείων σε αύξουσα τάξη. Για φθίνουσα ταξινόμηση των στοιχείων η συνάρτηση διάταξης τροποποιείται ως εξής: f(ak1) ≥ f(ak2) ≥ …≥ f(akn).

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

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

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

Φάσεις Ψηφιακού Σεναρίου: 
10 λεπτά
Φάση 1: Εισαγωγικές δραστηριότητες
Χώρος Διεξαγωγής: Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)
15 λεπτά
Φάση 2: Δραστηριότητες με χρήση πίνακα
Χώρος Διεξαγωγής: Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)
15 λεπτά
Φάση 3: Ο αλγόριθμος ταξινόμησης φυσαλίδας
Χώρος Διεξαγωγής: Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)
40 λεπτά
Φάση 4: Βελτιώσεις του αλγορίθμου ταξινόμησης φυσαλίδας
Χώρος Διεξαγωγής: Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)
35 λεπτά
Φάση 5: Οι αλγόριθμοι ταξινόμησης επιλογής και παρεμβολής
Χώρος Διεξαγωγής: Σχολικό Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ (ΣΕΠΕΗΥ)
Διδακτικοί Στόχοι: 
  1. Να εξηγούν τον αλγόριθμο ευθείας ανταλλαγής ή ταξινόμησης φυσαλίδας
  2. Να εξηγούν τον αλγόριθμο ταξινόμησης με επιλογή
  3. Να εξηγούν τον αλγόριθμο ταξινόμησης ευθείας εισαγωγής ή παρεμβολής
  4. Να εφαρμόζουν αλγόριθμο ταξινόμησης για την επίλυση προβλημάτων
  5. Να σχεδιάζουν άλλους αλγόριθμους ταξινόμησης
Λέξεις κλειδιά που χαρακτηρίζουν τη θεματική του σεναρίου: 
Ταξινόμηση
μονοδιάστατος πίνακας
ευθεία ανταλλαγή
φυσαλίδα
επιλογή
ευθεία εισαγωγή
παρεμβολή
Υλικοτεχνική υποδομή: 
Εργαστήριο Πληροφορικής & Εφαρμογών Η/Υ, Διερμηνευτής της Γλώσσας
Δημιουργός Σεναρίου: ΣΠΥΡΙΔΩΝ ΔΟΥΚΑΚΗΣ (Εκπαιδευτικός)
Έλεγχος Σεναρίου με τα Προγράμματα Σπουδών: ΚΩΤΣΑΚΗΣ ΣΤΑΥΡΟΣ (Σχολικός Σύμβουλος)
Έλεγχος Επιστημονικής Επάρκειας Σεναρίου: ΒΕΡΥΚΙΟΣ ΒΑΣΙΛΕΙΟΣ (Συντονιστής)