Γενικό Λύκειο > Ταξινόμηση

Διπλή Ταξινόμηση Με Επιλογή

(1/2) > >>

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

bugman:
Ο πιο εύκολος τρόπος εξήγησης "Διπλής" ταξινόμησης γίνεται με τον τύπο μεταβλητής αλφαριθμητικό. Τα αλφαριθμητικά ως σειρές χαρακτήρων μπορούν να έχουν κοινούς χαρακτήρες στις πρώτες θέσεις, οπότε αν έχουν ας πούμε στις τρεις πρώτες θέσεις ίδιους χαρακτήρες τότε αυτό λογαριάζεται για διπλή ταξινόμηση αφού δυο στοιχεία με όμοια τους τρεις πρώτους χαρακτήρες "ισοβαθμούν" μέχρι εκεί.
Το πραγματικό ζήτημα δεν είναι αν το "κλειδί" έχει δυο ή περισσότερα πεδία, αφού με τη σειρά θα εξεταστούν όλα μέχρι να βρεθεί κάτι που να δηλώνει διαφορά ή να μη βρεθεί, και άρα θα φθάσει ο έλεγχος μέχρι το τέλος, αλλά αν στην τεχνική ταξινόμησης έχει επιλεχθεί "stable" ή μη ταξινόμηση. Η "stable" ταξινόμηση σε περίπτωση "ισοβαθμίας" διατηρεί την σειρά των στοιχείων. Μια μη "stable" ταξινόμηση είναι η Quicksort η οποία στις ισοβαθμίες μπορεί να ανακατεύει τα στοιχεία.
Η ταξινόμηση με παρεμβολή (insertion sort) είναι "stable", και είναι πολύ απλός ο κώδικας.
Πιστεύω λοιπόν πως αν κάποιος θα ήθελε να δείξει κάτι περί "ισοβαθμίας" (ο όρος όπως χρησιμοποιήθηκε από τον OP), αυτό θα ήταν η διαφορά του "stable" από εκείνου του μη "stable".
Αν τώρα απλά μας ενδιαφέρει η "διπλή" ταξινόμηση, τότε μόνο με το παράδειγμα με τα αλφαριθμητικά είναι καλυμμένος!

anestis85:
Η ένσταση μου αγαπητέ είναι ότι με την ταξινόμηση με επιλογή η τεχνική της διπλής ταξινόμησης υλοποιείται με εναν αρκετά πιο πολύπλοκο τρόπο... Φοβάμαι ότι τα ίδια τα παιδιά θα τα βρουν σκούρα!!!

gpapargi:

--- Παράθεση από: anestis85 στις 30 Δεκ 2017, 06:52:36 μμ ---Καλησπέρα Συνάδερφοι και χρόνια πολλά.,
θα ήθελα τη γνώμη σας στο εξής ζήτημα. Η διλπή ταξινόμηση (σε περίπτωση ισοβαθμίας, κλπ) με τη τεχνική της φυσαλίδας είναι δεδομένα εντός ύλης. Έχει νόημα να δείξουμε στα παιδιά μας διπλή ταξινόμηση με τη χρήση της τεχνικής ταξινόμηση με επιλογή; Ούτε οι οδηγίες αναφέρουν κάποια τέτοια παραλλαγή αλλά ούτε και στο τετράδιο του μαθητή (από όσο μπορώ να θυμηθώ) υπάρχει αντίστοιχη προσέγγιση.
Σας ευχαριστώ.


--- Τέλος παράθεσης ---

Συνήθως χρησιμοποιώ το «ταξινόμηση με δευτερεύον κριτήριο». Μια απλή λύση είναι να σκεφτείς πως θα έκανες εύρεση θέσεως μεγίστου σε παράλληλους πίνακες με δευτερεύον κριτήριο. Δηλαδή κάτι σαν
Αν συνθήκη_πρωτεύοντος_κριτηρίου ή (Ισότητα_πρωτεύοντος_κριτηρίου και συνθήκη_δευτερεύοντος_κριτηρίου)
Δηλαδή θα έχεις μια σύνθετη συνθήκη θα περιγράφει πότε κάποιος είναι «μεγαλύτερος» από κάποιον άλλο. 
Η ίδια ιδέα μπορεί να χρησιμοποιηθεί και στη φυσαλίδα, ουσιαστικά περιγράφοντας με μια σύνθετη συνθήκη πότε γίνεται η αντιμετάθεση.

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

Όπως ανέφερα σε προηγούμενο μήνυμα, υπάρχει η περίπτωση μη "stable" ταξινόμησης, και εκεί η ισότητα δύναται να δημιουργήσει αντιμετάθεση και στο δεύτερο πίνακα αν και με το δεύτερο κριτήριο έχουμε ισότητα. Τώρα ενδέχεται κανείς να το αντιμετωπίσει αυτό βάζοντας ξεχωριστό έλεγχο και ισότητα και ανισότητες, που σημαίνει θα επιβαρύνει την ταξινόμηση με περισσότερες συγκρίσεις. Υπάρχουν για το λόγο αυτό συγκρίσεις που δίνουν απευθείας ένα νούμερο, πχ -1, 0 και 1 που δηλώνει με μια σύγκριση το αποτέλεσμά της (με 0 το ίσο), αλλά η ΓΛΩΣΣΑ του σχολείου δεν την υποστηρίζει. Θα μπορούσε κάποιος να φτιάξει μια συνάρτηση σύγκρισης, πχ για αριθμούς θα ήταν το πρόσημο(α-β), όπου αν το πρόσημο έδινε -1 θα είχαμε το  α<β αν έδινε 0 θα είχαμε ισότητα και αν έδινε 1 θα είχαμε α>β, αλλά και πάλι στη ΓΛΩΣΣΑ λείπει η SGN() ή sign (πρόσημο).

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση