Λοιπόν πείτε σας παρακαλώ, στην ταξινομήση_ευθείας_εισαγωγής(ΔΡΑΣΤΗΡΙΟΤΗΤΑ ΔΣ3) και ταξινόμηση_ευθείας_επιλογής(βιβλίο καθηγητή παραγραφος 3.9.1) οφείλω να δώσω μεγάλη βάση ή απλά να τις λύσω και να τις εξηγήσω;
Απλά να τις λύσεις και να τις εξηγήσεις ώστε οι μαθητές να καταλάβουν ότι η φυσσαλίδα δεν είναι παρά μία από τις λύσεις στο πρόβλημα της ταξινόμησης.
Μπορείς να θέλεις να τους τη δώσεις ως άσκηση για το σπίτι, να τους δώσεις δεδομένα να πειραματιστοπυν και να τους ζητήσεις να καταλάβουν ΤΙ κάνει ο αλγόριθμος και (σε δεύτερο στάδιο) να εξηγήσουν τη λειτουργία του.
Θα κερδίσουν αν απλά δουν ότι ένα πρόβλημα μπορεί να λυθεί με πολλούς τρόπους.
Αν υπάρχει έλλειψη χρόνου απλά εξήγησε τον τρόπο λειτουργίας τους και δώστους έτοιμο τον αλγόριθμο. Οι λόγοι είναι αυτοί που αναφέρει ο Φίλιππος.
Αν έχεις χρόνο (συνήθως σπάνια) είναι ενδιαφέρον να δείξεις πως "χτίζεις" σταδιακά έναν απο αυτούς τους αλγορίθμους. Ξεκινώντας απο την αρχική ιδέα, δημιουργώντας τις κατάλληλες δομές, έλεγχος να μην "βγώ" απο τον πίνακα, να μην ξεχάσω κανέναν στοιχείο του κ.λπ. ΄
Γενικά πάντως δεν αποτελούν θέμα εξέτασης και οι μαθητές δεν πολυενδιαφέρονται.
Βαγγέλης
Θέλω να ρωτήσω αν υπάρχει "έξυπνη" bubble sort η οποία να σταματά χωρίς να απαιτεί ένα επιπλέον πέρασμα;
δεν γίνεται με τίποτε ....
Παράθεση από: kyramas στις 09 Φεβ 2009, 12:35:49 ΜΜ
Θέλω να ρωτήσω αν υπάρχει "έξυπνη" bubble sort η οποία να σταματά χωρίς να απαιτεί ένα επιπλέον πέρασμα;
Υπάρχει στο τετράδιο μαθητή (κεφάλαιο 3, ΔΤ2, σελίδα 33) η έξυπνη φυσαλίδα που καταλαβαίνει πότε ο πίνακας έχει ταξινομηθεί "πρόωρα". Εννοείς αυτό ή κάτι πιο έξυπνο ακόμα;
Εννοώ αν υπάρχει πιο "έξυπνη" χωρίς να απαιτεί την προσπέλαση στην οποία δεν γίνεται καμία αντιμετάθεση. Να "καταλαβαίνει" δηλαδή ότι ο πίνακας ταξινομήθηκε ακόμη και αν έχουν γίνει αντιμεταθέσεις
Νομίζω όχι. Ας δούμε ένα παράδειγμα. Πες πως έχουμε τον πίνακα
2
3
4
5
1
και πάμε για αύξουσα ταξινόμηση. Στην πρώτη ολοκληρωμένη σάρωση από κάτω προς τα πάνω θα γίνει:
1
2
3
4
5
Η ταξινόμηση έχει τελειώσει και τώρα θέλουμε ένα τρόπο να το καταλάβουμε. Ας το δούμε σαν άνθρωποι πέρα από τις μηχανές. Είναι δυνατόν να καταλάβεις ότι τελείωσε χωρίς να κοιτάξεις τον πίνακα; Όχι. Το κοίταγμα του πίνακα ισοδυναμεί με σάρωση. Εκτός βέβαια αν με κάποιο τρόπο καταλάβεις από πριν ότι είσαι ένα βήμα πριν την τελική σάρωση. Πχ εγώ τον πίνακα του παραδείγματος τον έφτιαξα έτσι ώστε να ταξινομηθεί σε μια μόνο σάρωση. Αλλά και πάλι είχα κάνει από πριν τη σάρωση που γλίτωσα.
Γενικά πάντως δε νομίζω ότι είναι ζήτημα που αξίζει να απασχολήσει κάποιον. Αν γίνεται, θα γίνεται με δυσκολία μεγαλύτερη από αυτή που απαιτείται για να ασχοληθείς με άλλες γρηγορότερες ταξινομήσεις. Οπότε πας παρακάτω και τελειώνεις. Είναι σαν να μας απασχολεί το να βρούμε τη γρηγορότερη έκδοση της σειριακής αναζήτησης. Πας στη διαδική και τελειώνεις. (Αναγνωρίζω ότι η τελευταία παράγραφος είναι ντρίμπλα ;) )
Παράθεση από: kyramas στις 10 Φεβ 2009, 09:38:11 ΜΜ
Εννοώ αν υπάρχει πιο "έξυπνη" χωρίς να απαιτεί την προσπέλαση στην οποία δεν γίνεται καμία αντιμετάθεση. Να "καταλαβαίνει" δηλαδή ότι ο πίνακας ταξινομήθηκε ακόμη και αν έχουν γίνει αντιμεταθέσεις
Παράδειγμα (αύξουσα από αριστερά προς τα δεξιά, με έντονα οι συγκρίσεις):
1 2
8 6 5
1 2 6
8 51 2 6 5 8
Για να καταλάβει ότι ο παραπάνω πίνακας δεν είναι ταξινομημένος και ότι χρειάζεται κι άλλη "γύρα", θα πρέπει τη στιγμή που αντιμεταθέτει το 8 με το 5, να καταλάβει ότι το 5 είναι μικρότερο του 6.
Επομένως γίνεται, απλά χρειάζεται μια ακόμα σύγκριση, δηλαδή μια λογική μεταβλητή
ταξινομημένος η οποία αρχικοποιείται σε ΑΛΗΘΗΣ και γίνεται ΨΕΥΔΗΣ αν (μετά από μια αντιμετάθεση του α[ι] με το α[ι+1]) το α[ι] είναι μικρότερο του α[ι-1].
Βέβαια το να προσθέτεις μια σύγκριση σε
κάθε αντιμετάθεση για να γλυτώσεις μια επιπλέον "γύρα" στο τέλος
δεν είναι βελτιστοποίηση (παρά μόνο σε κάποιες πολύ εξεζητημένες περιπτώσεις).
πολύ καλή λύση. Ευχαριστώ
Αν καταλαβαίνω καλά, τις συγκρίσεις της σάρωσης που γλιτώνεις τις κάνεις νωρίτερα. Αλλά τι νόημα έχει κάτι τέτοιο;
Πχ ακόμα και στο στημένο παράδειγμα που έδωσα και θέλει μόνο μια σάρωση
2 3 4 5 1
την ώρα που το έφτιαξα έκανα τη σάρωση που γλίτωσα μετά (είναι στημμένο). Το θέμα από ότι κατάλαβα είναι αν γίνεται να γλιτώσεις τελείως τα βήματα της επιπλέον σάρωσης και να καταλήξεις σε κάτι... ας πούμε πιο γρήγορο.
Να τονίσουμε πάντως ότι ακόμα κι αν γλιτώσεις τη σάρωση η τάξη του αλγορίθμου δεν αλλάζει και παραμένει ν2