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

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

35 λεπτά

Οι αλγόριθμοι ταξινόμησης επιλογής και παρεμβολής

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

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

Αρχικά αναπτύσσουμε τον αλγόριθμο εντοπισμού του ελαχίστου σε πίνακα και χρησιμοποιούμε κατάλληλες εντολές για την αντιμετάθεση των στοιχείων ώστε το μικρότερο να τοποθετηθεί στην κορυφή του πίνακα (Δραστηριότητα ΔΕ16).

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

Ως επέκταση, τον αλγόριθμο ταξινόμησης με επιλογή, μπορούμε να τον αναπτύξουμε στα υποπρογράμματα.

Τέλος, εργαζόμαστε στον αλγόριθμο ταξινόμησης με τη μέθοδο της παρεμβολής ή ταξινόμησης ευθείας εισαγωγής. Έτσι, με μία νέα δραστηριότητα καλούμαστε να υλοποιήσουμε το σχετικό αλγόριθμο (Δραστηριότητα ΔΕ18). Πριν την υλοποίηση είναι σημαντικό να παρακολουθήσουμε την διαδραστική παρουσίαση στο http://aesop.iep.edu.gr/, ώστε να μπορούμε να περιγράφουμε την λειτουργία του αλγορίθμου.

Αυτό που μπορούμε να περιγράψουμε είναι ότι:

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

Ο αλγόριθμος της ταξινόμησης ευθείας εισαγωγής ή παρεμβολής είναι ιδανικός για περιπτώσεις δεδομένων που είναι «περίπου» ταξινομημένα.

Μια δραστηριότητα δίνεται για εργασία στο σπίτι (ΔΣ20).

Αλγόριθμος ταξινόμησης ευθείας εισαγωγής

Ταξινόμηση

Προγράμματα δραστηριοτήτων

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