Τετράδιο μαθητή
ΘΕ17: Ταξινόμηση
Όνομα(τα):___________________________________________________
Όνομα Η/Υ:___________________________________________________
Τμήμα:_______________________Ημερομηνία:___________________
Βάζοντας ΟΛΑ τα στοιχεία .
.. στη σειρά
Βάζοντας ΟΛΑ τα στοιχεία .
.. στη σειρά
Ξεκινήστε το Χώρο Δραστηριοτήτων, επιλέξτε τη θεματική ενότητα:
ΘΕ17:
Ταξινόμηση
και επιλέξτε την πρώτη δραστηριότητα (Βάζοντας ΟΛΑ τα στοιχεία .
..
στη σειρά).
Aνακεφαλαιώνοντας
, τα .
.. ευρήματα από τη δραστηριότητα 1 αυτής της ενότητας, μπορούμε να
πούμε ότι έχουμε αναπτύξει ένα
μηχανισμό
ο οποίος
προωθεί
το μικρότερο στοιχείο στην
κορυφή
(αρχή) του πίνακα, αφού προηγούμενα εξετάσει
όλα
τα
γειτονικά ζευγάρια
στοιχείων.
Κάποια συμπεράσματα στα οποία μπορούμε να καταλήξουμε σχετικά με το
μηχανισμό
προώθησης
που αναπτύξαμε είναι τα παρακάτω:
Τα
γειτονικά ζευγάρια
είναι
4
οπότε γίνονται
4
επαναλήψεις
Οι επαναλήψεις ξεκινάνε με το τελευταίο ζευγάρι (
5
, 4), συνεχίζουνε με το
προηγούμενο (
4
, 3), πάλι το προηγούμενο (
3
, 2) και τελειώνουν με το πρώτο (
2
, 1).
Οι επαναλήψεις γίνονται
από το τελευταίο ζευγάρι (
5
) προς το πρώτο ζευγάρι (
2
)
προκειμένου το τελικό αποτέλεσμα των συγκρίσεων να καταλήξει στην πρώτη θέση
(κορυφή) του πίνακα.
Επομένως η μεταβλητή της επανάληψης ξεκινάει από την τιμή
5
και συνεχίζει μέχρι
την τιμή
2
με βήμα
-1
.
Στο τέλος του αλγόριθμου, το μικρότερο στοιχείο του πίνακα βρίσκεται στην κορυφή
(θέση ) και τα υπόλοιπα σε τυχαίες θέσεις.
Ας εξετάσουμε τώρα το ίδιο πρόβλημα με μία λίγο διαφορετική εκφώνηση:
Ο προπονητής της ομάδας μπάσκετ ενός σχολείου θέλει να παρακολουθεί τα ύψη των 5
παικτών της βασικής ομάδας. Για το σκοπό αυτό χρειάζεται ένα πρόγραμμα το οποίο θα
τακτοποιεί τα ύψη των παικτών από το μικρότερο προς το μεγαλύτερο, δηλαδή θα τα ταξινομεί
σε
αύξουσα
σειρά.
στόχος μας τώρα είναι άλλος.
.. πιο σύνθετος. Πρέπει να
ταξινομήσουμε
ΟΛΑ τα
στοιχεία του πίνακα. Όμως, μέχρι στιγμής, το μόνο που .
.. έχουμε καταφέρει είναι να
προωθήσουμε μόνο το 1 (το
μικρότερο
από τα 5 στοιχεία) στην .
..κορυφή. Απομένει να
'προωθήσουμε' και τα υπόλοιπα 4, ένα προς ένα με τη σειρά. Και αυτό είναι που θα πρέπει να
κάνουμε σε αυτή τη δραστηριότητα.
Ο
δη γνωρίζουμε τον τρόπο!
Ό, τι κάναμε για το ένα στοιχείο μπορούμε να κάνουμε και για
τα υπόλοιπα, ένα προς ένα, με τη σειρά. Ο μηχανισμός που έχουμε υλοποιήσει προωθεί
ένα στοιχείο (το μικρότερο) στην κορυφή.
Ή
πομένως χρειάζεται πλέον να ασχοληθούμε μόνο με το .
..
αταξινόμητο
κομμάτι του πίνακα
(τα στοιχεία 2 έως 5) και να
προωθήσουμε
(με όμοιο τρόπο) το μικρότερο από αυτά τα
στοιχεία στην κορυφή του (υπόλοιπου) πίνακα.
Ε
Eπεκτείνετε τη λογική του αλγόριθμου
πό το χώρο δραστηριοτήτων επιλέξτε τον σύνδεσμο
που περιέχει το
πρόγραμμα που κατασκευάσατε στην 1η Δραστηριότητα. Προσθέστε στο τμήμα
Α
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 1 -
Αλγοριθμική & Προγραμματισμός
Βάζοντας ΟΛΑ τα στοιχεία .
.. στη σειρά
Τετράδιο μαθητή
επεξεργασίας του αλγόριθμου, ένα όμοιο τμήμα εντολών (
μηχανισμό προώθησης
) που θα
εξετάζει τα
3
ζευγάρια τιμών που απομένουν (
5
, 4) - (
4
, 3) - (
3
, 2) και θα
προωθεί
τη
μικρότερη τιμή στη θέση
2
του πίνακα. Το τμήμα αυτό θα έχει τη μορφή που δίνεται στη
συνέχεια.
Συμπληρώστε
την
αρχική
και
τελική
τιμή της μεταβλητής της επανάληψης, ώστε να
γίνουν οι
σωστές
3
επαναλήψεις, ξεκινώντας από το ζευγάρι στη θέση 5 και καταλήγοντας στο
ζευγάρι της θέσης 3:
Εξέταση των τελευταίων 3 'ζευγών τιμών' του πίνακα
Προώθηση του μικρότερου στη δεύτερη θέση του πίνακα
ΓΙΑ i ΑΠΟ ____ ΜΕΧΡΙ ____ ΜΕ_ΒΗΜΑ -1
ΑΝ Ύψος[ i ] < Ύψος[ i-1 ] ΤΟΤΕ
πρόχειρο <-- Ύψος[ i ]
Ύψος[ i ] <-- Ύψος[ i-1 ]
Ύψος[ i-1 ] <-- πρόχειρο
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
εταφέρετε τις εντολές στο
χώρο κωδικοποίησης
του Διερμηνευτή ώστε να έχετε τις δύο
δομές επανάληψης με τη σειρά, τη μία κάτω από την άλλη και δοκιμάστε με πραγματικές
τιμές: 1.88, 1.92, 1.83, 1.90, 1.85,
με αυτή τη σειρά
. Σημειώστε στο παρακάτω πλαίσιο τη
σειρά με την οποία περιμένετε να εμφανιστούν τα νούμερα κατά την έξοδο και επιβεβαιώστε το
με τις τιμές που θα εμφανίσει το πρόγραμμα.
Μ
Οι τιμές που θα εμφανίσει το πρόγραμμα με τη σειρά, είναι οι εξής:
κτελέστε το πρόγραμμα και σημειώστε τις τιμές που εμφανίστηκαν με τη σειρά στο
παρακάτω πλαίσιο κειμένου.
Ε
Οι τιμές που εμφάνισε το πρόγραμμα με τη σειρά, ήταν οι εξής:
ξετάζοντας
τους δύο
μηχανισμούς προώθησης
που έχουμε ήδη υλοποιήσει, καταλήγουμε
στα εξής συμπεράσματα:
Ε
όταν ο βρόχος καταλήγει
στην τιμή 2, εξετάζει όλες τις θέσεις του πίνακα ανάποδα
μέχρι και τη θέση 1 και
προωθεί
τη μικρότερη τιμή, στη θέση 1
όταν ο βρόχος καταλήγει
στην τιμή 3,
εξετάζει
όλες τις θέσεις του πίνακα ανάποδα
μέχρι και τη θέση 2 και
προωθεί
τη μικρότερη τιμή, στη θέση 2
πεκτείνετε
αυτή τη σκέψη καi προσθέστε στον αλγόριθμο τις επαναληπτικές δομές που θα
ολοκληρώσουν την εργασία της ταξινόμησης
με τα παρακάτω δύο βήματα:
Ε
να προωθεί τη μικρότερη από τις τελευταίες 3 τιμές στη θέση 3 (εξετάζοντας όλες τις
θέσεις του πίνακα ανάποδα μέχρι και τη θέση 3) και στη συνέχεια
να προωθεί τη μικρότερη από τις τελευταίες 2 τιμές στη θέση 4 (εξετάζοντας όλες τις
θέσεις του πίνακα ανάποδα μέχρι και τη θέση 4)
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 2 -
Αλγοριθμική & Προγραμματισμός
Τετράδιο μαθητή
ΘΕ17: Ταξινόμηση
ροσέξτε
ότι εφόσον ταξινομηθούν σωστά τα 4 από τα 5 στοιχεία,
δε
χρειάζεται να γίνει
κάτι αντίστοιχο για το τελευταίο, αφού αυτό θα είναι πλέον στη .
.. σωστή θέση!
Π
εταφέρετε τις εντολές στο
χώρο κωδικοποίησης
του Διερμηνευτή ώστε να έχετε όλες
τις δομές επανάληψης με τη σειρά, τη μία κάτω από την άλλη και δοκιμάστε με
πραγματικές τιμές: 1.88, 1.92, 1.83, 1.90, 1.85,
με αυτή τη σειρά
. Σημειώστε στο παρακάτω
πλαίσιο τη σειρά με την οποία περιμένετε να εμφανιστούν τα νούμερα κατά την έξοδο και
επιβεβαιώστε το με τις τιμές που θα εμφανίσει το πρόγραμμα.
Μ
Οι τιμές που θα εμφανίσει το πρόγραμμα με τη σειρά, είναι οι εξής:
κτελέστε το πρόγραμμα και σημειώστε τις τιμές που εμφανίστηκαν με τη σειρά στο
παρακάτω πλαίσιο κειμένου.
Ε
Οι τιμές που εμφάνισε το πρόγραμμα με τη σειρά, ήταν οι εξής:
Τα στοιχεία είναι ταξινομημένα σε αύξουσα σειρά.
..
... από το μικρότερο προς το μεγαλύτερο
Ας γενικεύσουμε τον αλγόριθμο
νακεφαλαιώνοντας
, μπορούμε να πούμε ότι μέχρι τώρα έχουμε καταλήξει στα εξής
συμπεράσματα:
A
Ο αλγόριθμος βασίζεται στο
μηχανισμό προώθησης
που αναπτύξαμε στο προηγούμενο
βήμα.
Κάθε φορά που εκτελείται, ο
μηχανισμός προώθησης
στέλνει στην κορυφή το μικρότερο
από τα στοιχεία που εξέτασε (σα να ανεβάζει στην επιφάνεια μία
φυσσαλίδα
)
Για να επιτύχουμε την ταξινόμηση των 5 στοιχείων του πίνακα εφαρμόζουμε το
μηχανισμό προώθησης
4 φορές
Ξεκινώντας με ένα αταξινόμητο πίνακα εφαρμόζουμε το
μηχανισμό προώθησης
σε όλα
του τα στοιχεία προκειμένου να 'ανεβάσουμε' στην επιφάνεια το μικρότερο
Στη συνέχεια εφαρμόζουμε κατ' επανάληψη το μηχανισμό προώθησης στα υπόλοιπα
στοιχεία του πίνακα, κατεβάζοντας κάθε φορά την .
..
επιφάνεια
(την τιμή τερματισμού
της δομής επανάληψης) κατά 1
υμπεραίνουμε λοιπόν ότι
η ταξινόμηση των στοιχείων πετυχαίνεται με διαδοχικές
προωθήσεις τιμών (
φυσσαλίδων
) στην κορυφή, χαμηλώνοντας κάθε φορά την .
..
επιφάνεια
κατά 1.
Σε αυτό το συμπέρασμα καταλήγουμε εύκολα και αν παρατηρήσουμε τον
κώδικα που προοδευτικά κατασκευάσαμε στο πρόγραμμά μας:
Σ
ο αλγόριθμος περιλαμβάνει 4 φορές την (σχεδόν) ίδια δομή επανάληψης (τον ίδιο
μηχανισμό προώθησης)
το μόνο που αλλάζει σε κάθε ενεργοποίηση του μηχανισμού είναι η τιμή τερματισμού (
η
επιφάνεια
του μηχανισμού
προώθησης της φυσσαλίδας
)
φού λοιπόν ο ίδιος μηχανισμός επαναλαμβάνεται 4 φορές, θα μπορούσαμε να συμπτύξουμε
τον αλγόριθμο ώστε να εκτελεί πολλές φορές διαδοχικά το
μηχανισμό προώθησης
,
εμφωλεύοντάς τον
σε επανάληψη. Αφού το μόνο που αλλάζει από επανάληψη σε επανάληψη
Α
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 3 -
Αλγοριθμική & Προγραμματισμός
Βάζοντας ΟΛΑ τα στοιχεία .
.. στη σειρά
Τετράδιο μαθητή
είναι η τιμή της .
.. επιφάνειας
στο μηχανισμό
προώθησης
, η επανάληψη που θα εμφωλεύσει το
μηχανισμό θα πρέπει να φροντίζει για τη σωστή τιμή της .
..
επιφάνειας
.
τον αλγόριθμο που παρουσιάζεται στη συνέχεια υλοποιεί την ταξινόμηση με αυτό τον
τρόπο. Ο μηχανισμός προώθησης βρίσκεται εμφωλευμένος σε επανάληψη η οποία
καθορίζει την .
.. επιφάνεια για την .
.. ανάδυση της φυσσαλίδας. Ο
μηχανισμός φυσσαλίδας
(
εσωτερικός
βρόχος) χρησιμοποιεί πλέον τη μεταβλητή
j
για να προσπελάσει τα στοιχεία του
πίνακα ενώ η
επιφάνεια
(
εξωτερικός
βρόχος)
παριστάνεται με τη μεταβλητή
i
.
Σ
υμπληρώστε
την
αρχική
και
τελική
τιμή της μεταβλητής
i
επανάληψης, ώστε ο αλγόριθμος
να έχει το ίδιο αποτέλεσμα με εκείνο που είχε στο προηγούμενο βήμα:
Σ
Ταξινόμηση των 5 στοιχείων του πίνακα
ΓΙΑ i ΑΠΟ ____ ΜΕΧΡΙ ____
ΓΙΑ j ΑΠΟ 5 ΜΕΧΡΙ
i
ΜΕ_ΒΗΜΑ -1
ΑΝ Ύψος[ j ] < Ύψος[ j-1 ] ΤΟΤΕ
πρόχειρο <-- Ύψος[ j ]
Ύψος[ j ] <-- Ύψος[ j-1 ]
Ύψος[ j-1 ] <-- πρόχειρο
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
εταφέρετε τις εντολές στο
χώρο κωδικοποίησης
του Διερμηνευτή και δοκιμάστε πάλι με
τις ίδιες τιμές: 1.88, 1.92, 1.83, 1.90, 1.85,
με αυτή τη σειρά
. Σημειώστε στο παρακάτω
πλαίσιο τη σειρά με την οποία περιμένετε να εμφανιστούν τα νούμερα κατά την έξοδο και
επιβεβαιώστε το με τις τιμές που θα εμφανίσει το πρόγραμμα.
Μ
Οι τιμές που θα εμφανίσει το πρόγραμμα με τη σειρά, είναι οι εξής:
κτελέστε το πρόγραμμα και σημειώστε τις τιμές που εμφανίστηκαν με τη σειρά στο
παρακάτω πλαίσιο κειμένου.
Ε
Οι τιμές που εμφάνισε το πρόγραμμα με τη σειρά, ήταν οι εξής:
ι δημιουργοί του αλγόριθμου, που μόλις ολοκληρώσατε, τον έχουν βαφτίσει
ταξινόμηση
φυσσαλίδας
.
Μπορείτε να καταλάβετε γιατί;
Συμπληρώστε τα κενά στο κείμενο:
Ο
Αύξουσα Ταξινόμηση με τον αλγόριθμο
Φυσσαλίδας (BubbleSort)
- Ο _ σ _ _ _ _ _ _ _ _ βρόχος (_ _ φ _ _ _ _ _ _ _ _ _) ανεβάζει
στην _ _ _ φ _ _ _ _ _ (κορυφή του πίνακα) τη μικρότερη τιμή
σαν να ανεβάζει μία _ _ _ _ _ λ _ _ _ στην επιφάνεια
- στη συνέχεια η επιφάνεια χαμηλώνει (_ ξ _ _ _ _ _ _ _ _ βρόχος)
και ο μηχανισμός επαναλαμβάνεται για τις _ _ _ λ _ _ _ _ _ τιμές
του πίνακα ώστε να 'ανεβάσει' την επόμενη _ _ _ _ _ _ _ δ _
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 4 -
Αλγοριθμική & Προγραμματισμός
Τετράδιο μαθητή
ΘΕ17: Ταξινόμηση
να προωθεί τη μικρότερη από τις τελευταίες 2 τιμές στη θέση 4 (εξετάζοντας όλες τις
θέσεις του πίνακα ανάποδα μέχρι και τη θέση 4)
ίδιος αλγόριθμος ταξινόμησης συναντιέται επίσης συχνά με το όνομα
ταξινόμηση ευθείας
ανταλλαγής
!
Ο
Παραλλαγές στο .
.. ίδιο θέμα
το προηγούμενο βήμα, ολοκληρώσαμε την ταξινόμηση των στοιχείων σε
αύξουσα
σειρά με
τη μέθοδο της φυσσαλίδας (bubblesort).
Για αύξουσα ταξινόμηση προσέχουμε τα εξής:
Σ
Αύξουσα
σειρά σημαίνει ότι οι τιμές του πίνακα θα αυξάνονται, επομένως
στην αρχή του πίνακα θα υπάρχει η
μικρότερη
τιμή και στο τέλος η μεγαλύτερη,
επομένως
η
φυσσαλίδα
που θα προωθείται κάθε φορά
στην επιφάνεια
(κορυφή του πίνακα) θα
πρέπει να είναι η
μικρότερη
από τις τιμές, επομένως
.η
συνθήκη προώθησης (
που συγκρίνει τις φυσσαλίδες και
ενεργοποιεί
την
αντιμετάθεσή τους) θα ισχύει όταν η (υποψήφια) φυσσαλίδα είναι
μικρότερη
από την
προηγούμενή της (ΑΝ Ύψος[j]
<
Ύψος[j-1])
κολουθώντας όμοιο συλλογισμό, συμπληρώστε το παρακάτω κείμενο που αναφέρεται στην
ταξινόμηση φυσσαλίδας με
φθίνουσα
σειρά:
Α
Φθίνουσα Ταξινόμηση με τον αλγόριθμο
Φυσσαλίδας (BubbleSort)
- Φθίνουσα σειρά σημαίνει ότι οι τιμές του πίνακα, αντί να αυξάνονται,
θα _ _ _ ώ _ _ _ _ _ _,
επομένως
- στην αρχή του πίνακα θα υπάρχει η
_ _ _ _ _ _ _ _ _ _
τιμή και
στο τέλος η _ _ κ _ _ _ _ _ _, επομένως
- η φυσσαλίδα που θα προωθείται
στην επιφάνεια
(_ _ _ _ _ _ του
πίνακα) θα πρέπει να είναι η _ _ γ _ _ _ _ _ _ _ από τις τιμές,
επομένως
.- η συνθήκη προώθησης που συγκρίνει τις φυσσαλίδες (και ενεργοποιεί
την αντιμετάθεσή τους) θα ισχύει όταν η (υποψήφια) φυσσαλίδα είναι
_ _ _ _ _ _ _ _ _ _
από την προηγούμενή της
(ΑΝ Ύψος[j]
___
Ύψος[j-1])
ροποιείστε τον αλγόριθμο ώστε να ταξινομεί τα στοιχεία σε φθίνουσα σειρά. Μεταφέρετε
τις εντολές στο
χώρο κωδικοποίησης
του Διερμηνευτή και δοκιμάστε πάλι με τις ίδιες
τιμές: 1.88, 1.92, 1.83, 1.90, 1.85,
με αυτή τη σειρά
. Σημειώστε στο παρακάτω πλαίσιο τη
σειρά με την οποία περιμένετε να εμφανιστούν τα νούμερα κατά την έξοδο και επιβεβαιώστε το
με τις τιμές που θα εμφανίσει το πρόγραμμα.
Τ
Οι τιμές που θα εμφανίσει το πρόγραμμα με τη σειρά, είναι οι εξής:
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 5 -
Αλγοριθμική & Προγραμματισμός
Βάζοντας ΟΛΑ τα στοιχεία .
.. στη σειρά
Τετράδιο μαθητή
κτελέστε το πρόγραμμα και σημειώστε τις τιμές που εμφανίστηκαν με τη σειρά στο
παρακάτω πλαίσιο κειμένου.
Ε
Οι τιμές που εμφάνισε το πρόγραμμα με τη σειρά, ήταν οι εξής:
Μία (ακόμη) άσκηση εμπέδωσης
ία δυσκολία που συνήθως αντιμετωπίζουμε στα προβλήματα ταξινόμησης είναι αυτή που
ίσως να αντιμετωπίσετε και εσείς προσπαθώντας να λύσετε την άσκηση που ακολουθεί.
Μ
Κατά τη διάρκεια του αγώνα μπάσκετ της ομάδας μπάσκετ του σχολείου (που μας απασχόλησε
σε .
.. όλες τις προηγούμενες ασκήσεις), ο προπονητής κρατάει για κάθε παίκτη το όνομά του και
τον αριθμό πόντων που πέτυχε. Κατασκευάστε πρόγραμμα που θα ζητάει τα στοιχεία για κάθε
παίκτη και θα τα καταχωρεί σε δύο (παράλληλους) πίνακες. Στη συνέχεια θα ταξινομεί τα
στοιχεία με φθίνουσα σειρά πόντων και θα εμφανίζει για κάθε παίκτη, το όνομά του και τους
πόντους που πέτυχε(από τον καλύτερο προς το χειρότερο σκόρερ) με κατάλληλα διαμορφωμένο
μήνυμα.
...
κτελέστε το πρόγραμμα δίνοντας τις παρακάτω τιμές για τα ονόματα και τους πόντους των
παικτών της ομάδας:
Ε
1.
Φάνης
20
2.
Παναγιώτης
10
3.
Κώστας
12
4.
Παναγιώτης
19
5.
Νίκος
25
α πρέπει να εμφανιστούν τα μηνύματα που παρουσιάζονται στη συνέχεια. Αν όχι,
συζητείστε το με τους συμμαθητές και τον καθηγητή σας για να βρείτε το λάθος και
διορθώστε το.
Εκτελέστε το πρόγραμμα μέχρι να πάρετε σωστά αποτελέσματα:
Θ
1ος
scorer, με 25 πόντους, είναι ο Νίκος
2ος scorer, με 20 πόντους, είναι ο Φάνης
3ος scorer, με 19 πόντους, είναι ο Παναγιώτης
4ος scorer, με 12 πόντους, είναι ο Κώστας
5ος scorer, με 10 πόντους, είναι ο Παναγιώτης
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 6 -
Αλγοριθμική & Προγραμματισμός
Τετράδιο μαθητή
ΘΕ17: Ταξινόμηση
1.
Επανάληψη με .
.. “σταυρούς και λέξεις”
οκιμάστε τις νέες σας γνώσεις (και τη φαντασία σας) συμπληρώνοντας ένα σταυρόλεξο.
Μπορείτε να το συμπληρώσετε στο χαρτί, ή στον υπολογιστή επιλέγοντας το σύνδεσμο
Σταυρόλεξο
.
Δ
Οριζόντια
1. Ο μηχανισμός αυτός μετακινεί μία τιμή στην άκρη του πίνακα
3. ΑΝ Π[i] < Π[i-1] ΤΟΤΕ.
.. αυτό ανεβαίνει στην επιφάνεια
5. αυτός ο βρόχος ανεβάζει τη φυσσαλίδα
7. αυτός ο βρόχος κατεβάζει την επιφάνεια
11. στην φθίνουσα ταξινόμηση πάει στην επιφάνεια αυτό
12.Τέτοια η ταξινόμηση όταν ξεκινάει με το μεγαλύτερο
13.ΑΝ Π[i] < Π[i-1] ΤΟΤΕ.
.. τέτοια γίνεται η ταξινόμηση
14.τέτοιο είναι το βήμα του εσωτερικού βρόχου
15.και τέτοιας .
.. ευθείας ονομάζεται ο αλγόριθμος φυσσαλίδας
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 7 -
Αλγοριθμική & Προγραμματισμός
Βάζοντας ΟΛΑ τα στοιχεία .
.. στη σειρά
Τετράδιο μαθητή
Κατακόρυφα
2. τέτοιο είναι το βήμα του εξωτερικού βρόχου
4. τέτοιος είναι ο βρόχος που ανεβάζει τη φυσσαλίδα
6. η ανταλλαγή τιμής δύο μεταβλητών
8. Από αυτή την τιμή ξεκινάει ο εξωτερικός βρόχος (ολογράφως)
9. ονομάζεται και έτσι ο αλγόριθμος ταξινόμησης που μάθαμε σε αυτή τη δραστηριότητα
10.αυτή .
.. αποφασίζει εάν θα γίνει αντιμετάθεση
2.
Εμβαθύνοντας.
..
ν πιστεύετε ότι έχετε κατανοήσει τον αλγόριθμο της
ταξινόμησης ευθείας ανταλλαγής
προσπαθήστε να υλοποιήσετε ένα παρόμοιο αλγόριθμο στη συνέχεια. Ο αλγόριθμος
ακολουθεί ακριβώς την ίδια αρχή αλλά εντελώς αντίστροφα: αντί να ανεβάζει .
..
φυσσαλίδες
,
κατεβάζει.
..
βαρίδια
αφού, αντίθετα με τη .
.. φυσσαλίδα:
Α
εξετάζει τα στοιχεία του πίνακα από την αρχή προς το τέλος.
Συγκρίνει κάθε στοιχείο με το επόμενο
κορμός του ‘αντεστραμμένου’ αλγορίθμου δίνεται στη συνέχεια και εσείς πρέπει να
συμπληρώσετε τα κενά που υπάρχουν
Ο
Ταξινόμηση.
.. Βαριδίου
ΓΙΑ i ΑΠΟ 4 ΜΕΧΡΙ ____
ΜΕ_ΒΗΜΑ
____
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ
____
ΑΝ Ύψος[ j ]
____
Ύψος[ j+1 ] ΤΟΤΕ
πρόχειρο <--
____
Ύψος[ j ] <-- ____
____
<--
____
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Ο αλγόριθμος να ταξινομεί τα στοιχεία σε αύξουσα σειρά, δηλαδή:
Ύψος[1]<Ύψος[2]<Ύψος[3]<Ύψος[4]<Ύψος[5]
Ελέγξτε την ορθότητα της λύσης σας δοκιμάζοντας τον αλγόριθμο στο χώρο κωδικοποίησης
του Διερμηνευτή
Έργο ΠΛΕΙΑΔΕΣ/Νηρηίδες, Γ΄ ΚΠΣ
ΕΑ.ΙΤΥ / Υπ.Ε.Π.Θ.
- σελ. 8 -
Αλγοριθμική & Προγραμματισμός