Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Μονοδιάστατοι πίνακες => Γ΄ Λυκείου => Ταξινόμηση => Μήνυμα ξεκίνησε από: Kalli στις 09 Φεβ 2007, 01:05:12 μμ

Τίτλος: "Οι Ταξινομήσεις"
Αποστολή από: Kalli στις 09 Φεβ 2007, 01:05:12 μμ
Λοιπόν πείτε σας παρακαλώ, στην ταξινομήση_ευθείας_εισαγωγής(ΔΡΑΣΤΗΡΙΟΤΗΤΑ ΔΣ3) και ταξινόμηση_ευθείας_επιλογής(βιβλίο καθηγητή παραγραφος 3.9.1) οφείλω να δώσω μεγάλη βάση ή απλά να τις λύσω και να τις εξηγήσω;
 
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: filippos στις 11 Φεβ 2007, 08:33:37 μμ
Απλά να τις λύσεις και να τις εξηγήσεις ώστε οι μαθητές να καταλάβουν ότι η φυσσαλίδα δεν είναι παρά μία από τις λύσεις στο πρόβλημα της ταξινόμησης.

Μπορείς να θέλεις να τους τη δώσεις ως άσκηση για το σπίτι, να τους δώσεις δεδομένα να πειραματιστοπυν και να τους ζητήσεις να καταλάβουν ΤΙ κάνει ο αλγόριθμος και (σε δεύτερο στάδιο) να εξηγήσουν τη λειτουργία του.

Θα κερδίσουν αν απλά δουν ότι ένα πρόβλημα μπορεί να λυθεί με πολλούς τρόπους.
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: Vangelis στις 12 Φεβ 2007, 08:34:35 μμ
Αν υπάρχει έλλειψη χρόνου απλά εξήγησε τον τρόπο λειτουργίας τους και δώστους έτοιμο τον αλγόριθμο.   Οι λόγοι είναι αυτοί που αναφέρει ο Φίλιππος.

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

Γενικά πάντως δεν αποτελούν θέμα εξέτασης και οι μαθητές δεν πολυενδιαφέρονται.

Βαγγέλης
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: kyramas στις 09 Φεβ 2009, 12:35:49 μμ
Θέλω να ρωτήσω αν υπάρχει "έξυπνη" bubble sort η οποία να σταματά χωρίς να απαιτεί ένα επιπλέον πέρασμα;
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: stavrax στις 09 Φεβ 2009, 01:30:25 μμ
δεν γίνεται με τίποτε ....
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: gpapargi στις 10 Φεβ 2009, 09:13:52 πμ
Θέλω να ρωτήσω αν υπάρχει "έξυπνη" bubble sort η οποία να σταματά χωρίς να απαιτεί ένα επιπλέον πέρασμα;

Υπάρχει στο τετράδιο μαθητή (κεφάλαιο 3, ΔΤ2, σελίδα 33) η έξυπνη φυσαλίδα που καταλαβαίνει πότε ο πίνακας έχει ταξινομηθεί "πρόωρα". Εννοείς αυτό ή κάτι πιο έξυπνο ακόμα;
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: kyramas στις 10 Φεβ 2009, 09:38:11 μμ
Εννοώ αν υπάρχει πιο "έξυπνη" χωρίς να απαιτεί την προσπέλαση στην οποία δεν γίνεται καμία αντιμετάθεση. Να "καταλαβαίνει" δηλαδή ότι ο πίνακας ταξινομήθηκε ακόμη και αν έχουν γίνει αντιμεταθέσεις
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: gpapargi στις 11 Φεβ 2009, 08:22:55 πμ
Νομίζω όχι. Ας δούμε ένα παράδειγμα. Πες πως έχουμε τον πίνακα
2
3
4
5
1
και πάμε για αύξουσα ταξινόμηση. Στην πρώτη ολοκληρωμένη σάρωση από κάτω προς τα πάνω θα γίνει:
1
2
3
4
5

Η ταξινόμηση έχει τελειώσει και τώρα θέλουμε ένα τρόπο να το καταλάβουμε. Ας το δούμε σαν άνθρωποι πέρα από τις μηχανές. Είναι δυνατόν να καταλάβεις ότι τελείωσε χωρίς να κοιτάξεις τον πίνακα; Όχι. Το κοίταγμα του πίνακα ισοδυναμεί με σάρωση. Εκτός βέβαια αν με κάποιο τρόπο καταλάβεις από πριν ότι είσαι ένα βήμα πριν την τελική σάρωση. Πχ εγώ τον πίνακα του παραδείγματος τον έφτιαξα έτσι ώστε να ταξινομηθεί σε μια μόνο σάρωση. Αλλά και πάλι είχα κάνει από πριν τη σάρωση που γλίτωσα.

Γενικά πάντως δε νομίζω ότι είναι ζήτημα που αξίζει να απασχολήσει κάποιον. Αν γίνεται, θα γίνεται με δυσκολία μεγαλύτερη από αυτή που απαιτείται για να ασχοληθείς με άλλες γρηγορότερες ταξινομήσεις. Οπότε πας παρακάτω και τελειώνεις. Είναι σαν να μας απασχολεί το να βρούμε τη γρηγορότερη έκδοση της σειριακής αναζήτησης. Πας στη διαδική και τελειώνεις. (Αναγνωρίζω ότι η τελευταία παράγραφος είναι ντρίμπλα  ;)  )
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: alkisg στις 11 Φεβ 2009, 09:16:23 πμ
Εννοώ αν υπάρχει πιο "έξυπνη" χωρίς να απαιτεί την προσπέλαση στην οποία δεν γίνεται καμία αντιμετάθεση. Να "καταλαβαίνει" δηλαδή ότι ο πίνακας ταξινομήθηκε ακόμη και αν έχουν γίνει αντιμεταθέσεις
Παράδειγμα (αύξουσα από αριστερά προς τα δεξιά, με έντονα οι συγκρίσεις):
1 2 8 6 5
1 2 6 8 5
1 2 6 5 8

Για να καταλάβει ότι ο παραπάνω πίνακας δεν είναι ταξινομημένος και ότι χρειάζεται κι άλλη "γύρα", θα πρέπει τη στιγμή που αντιμεταθέτει το 8 με το 5, να καταλάβει ότι το 5 είναι μικρότερο του 6.
Επομένως γίνεται, απλά χρειάζεται μια ακόμα σύγκριση, δηλαδή μια λογική μεταβλητή ταξινομημένος η οποία αρχικοποιείται σε ΑΛΗΘΗΣ και γίνεται ΨΕΥΔΗΣ αν (μετά από μια αντιμετάθεση του α[ι] με το α[ι+1]) το α[ι] είναι μικρότερο του α[ι-1].

Βέβαια το να προσθέτεις μια σύγκριση σε κάθε αντιμετάθεση για να γλυτώσεις μια επιπλέον "γύρα" στο τέλος δεν είναι βελτιστοποίηση (παρά μόνο σε κάποιες πολύ εξεζητημένες περιπτώσεις).
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: kyramas στις 12 Φεβ 2009, 10:09:28 πμ
πολύ καλή λύση. Ευχαριστώ
Τίτλος: Απ: "Οι Ταξινομήσεις"
Αποστολή από: gpapargi στις 12 Φεβ 2009, 11:54:42 πμ
Αν καταλαβαίνω καλά, τις συγκρίσεις της σάρωσης που γλιτώνεις τις κάνεις νωρίτερα. Αλλά τι νόημα έχει κάτι τέτοιο;
Πχ ακόμα και στο στημένο παράδειγμα που έδωσα και θέλει μόνο μια σάρωση
2 3 4 5 1
την ώρα που το έφτιαξα έκανα τη σάρωση που γλίτωσα μετά (είναι στημμένο). Το θέμα από ότι κατάλαβα είναι αν γίνεται να γλιτώσεις τελείως τα βήματα της επιπλέον σάρωσης και να καταλήξεις σε κάτι... ας πούμε πιο γρήγορο.
Να τονίσουμε πάντως ότι ακόμα κι αν γλιτώσεις τη σάρωση η τάξη του αλγορίθμου δεν αλλάζει και παραμένει ν2