Καλησπέρα Συνάδερφοι και χρόνια πολλά.,
θα ήθελα τη γνώμη σας στο εξής ζήτημα. Η διλπή ταξινόμηση (σε περίπτωση ισοβαθμίας, κλπ) με τη τεχνική της φυσαλίδας είναι δεδομένα εντός ύλης. Έχει νόημα να δείξουμε στα παιδιά μας διπλή ταξινόμηση με τη χρήση της τεχνικής ταξινόμηση με επιλογή; Ούτε οι οδηγίες αναφέρουν κάποια τέτοια παραλλαγή αλλά ούτε και στο τετράδιο του μαθητή (από όσο μπορώ να θυμηθώ) υπάρχει αντίστοιχη προσέγγιση.
Σας ευχαριστώ.
Ο πιο εύκολος τρόπος εξήγησης "Διπλής" ταξινόμησης γίνεται με τον τύπο μεταβλητής αλφαριθμητικό. Τα αλφαριθμητικά ως σειρές χαρακτήρων μπορούν να έχουν κοινούς χαρακτήρες στις πρώτες θέσεις, οπότε αν έχουν ας πούμε στις τρεις πρώτες θέσεις ίδιους χαρακτήρες τότε αυτό λογαριάζεται για διπλή ταξινόμηση αφού δυο στοιχεία με όμοια τους τρεις πρώτους χαρακτήρες "ισοβαθμούν" μέχρι εκεί.
Το πραγματικό ζήτημα δεν είναι αν το "κλειδί" έχει δυο ή περισσότερα πεδία, αφού με τη σειρά θα εξεταστούν όλα μέχρι να βρεθεί κάτι που να δηλώνει διαφορά ή να μη βρεθεί, και άρα θα φθάσει ο έλεγχος μέχρι το τέλος, αλλά αν στην τεχνική ταξινόμησης έχει επιλεχθεί "stable" ή μη ταξινόμηση. Η "stable" ταξινόμηση σε περίπτωση "ισοβαθμίας" διατηρεί την σειρά των στοιχείων. Μια μη "stable" ταξινόμηση είναι η Quicksort η οποία στις ισοβαθμίες μπορεί να ανακατεύει τα στοιχεία.
Η ταξινόμηση με παρεμβολή (insertion sort) είναι "stable", και είναι πολύ απλός ο κώδικας.
Πιστεύω λοιπόν πως αν κάποιος θα ήθελε να δείξει κάτι περί "ισοβαθμίας" (ο όρος όπως χρησιμοποιήθηκε από τον OP), αυτό θα ήταν η διαφορά του "stable" από εκείνου του μη "stable".
Αν τώρα απλά μας ενδιαφέρει η "διπλή" ταξινόμηση, τότε μόνο με το παράδειγμα με τα αλφαριθμητικά είναι καλυμμένος!
Η ένσταση μου αγαπητέ είναι ότι με την ταξινόμηση με επιλογή η τεχνική της διπλής ταξινόμησης υλοποιείται με εναν αρκετά πιο πολύπλοκο τρόπο... Φοβάμαι ότι τα ίδια τα παιδιά θα τα βρουν σκούρα!!!
Παράθεση από: anestis85 στις 30 Δεκ 2017, 06:52:36 ΜΜ
Καλησπέρα Συνάδερφοι και χρόνια πολλά.,
θα ήθελα τη γνώμη σας στο εξής ζήτημα. Η διλπή ταξινόμηση (σε περίπτωση ισοβαθμίας, κλπ) με τη τεχνική της φυσαλίδας είναι δεδομένα εντός ύλης. Έχει νόημα να δείξουμε στα παιδιά μας διπλή ταξινόμηση με τη χρήση της τεχνικής ταξινόμηση με επιλογή; Ούτε οι οδηγίες αναφέρουν κάποια τέτοια παραλλαγή αλλά ούτε και στο τετράδιο του μαθητή (από όσο μπορώ να θυμηθώ) υπάρχει αντίστοιχη προσέγγιση.
Σας ευχαριστώ.
Συνήθως χρησιμοποιώ το «ταξινόμηση με δευτερεύον κριτήριο». Μια απλή λύση είναι να σκεφτείς πως θα έκανες εύρεση θέσεως μεγίστου σε παράλληλους πίνακες με δευτερεύον κριτήριο. Δηλαδή κάτι σαν
Αν συνθήκη_πρωτεύοντος_κριτηρίου ή (Ισότητα_πρωτεύοντος_κριτηρίου και συνθήκη_δευτερεύοντος_κριτηρίου)
Δηλαδή θα έχεις μια σύνθετη συνθήκη θα περιγράφει πότε κάποιος είναι «μεγαλύτερος» από κάποιον άλλο.
Η ίδια ιδέα μπορεί να χρησιμοποιηθεί και στη φυσαλίδα, ουσιαστικά περιγράφοντας με μια σύνθετη συνθήκη πότε γίνεται η αντιμετάθεση.
Για να πάμε στο δεύτερο κριτήριο πρέπει να έχουμε ισότητα στο πρώτο. Ακόμα και αν στο πρώτο πίνακα θέλουμε ταξινόμηση από τον μεγαλύτερο στο μικρότερο, και στο δεύτερο το ανάποδο, η ισότητα είναι απαραίτητη στο πρώτο κριτήριο για να εξετάσουμε το δεύτερο. Σε περίπτωση ανισότητας του πρώτου κριτηρίου η τύχη αντιμετάθεσης (swap) στο δεύτερο πίνακα είναι ίδια με αυτή του πρώτου, ενώ σε περίπτωση ισότητας στο πρώτο κριτήριο η αντιμετάθεση στο δεύτερο γίνεται με το κανόνα του δεύτερου, εφόσον υπάρχει ανισότητα.
Όπως ανέφερα σε προηγούμενο μήνυμα, υπάρχει η περίπτωση μη "stable" ταξινόμησης, και εκεί η ισότητα δύναται να δημιουργήσει αντιμετάθεση και στο δεύτερο πίνακα αν και με το δεύτερο κριτήριο έχουμε ισότητα. Τώρα ενδέχεται κανείς να το αντιμετωπίσει αυτό βάζοντας ξεχωριστό έλεγχο και ισότητα και ανισότητες, που σημαίνει θα επιβαρύνει την ταξινόμηση με περισσότερες συγκρίσεις. Υπάρχουν για το λόγο αυτό συγκρίσεις που δίνουν απευθείας ένα νούμερο, πχ -1, 0 και 1 που δηλώνει με μια σύγκριση το αποτέλεσμά της (με 0 το ίσο), αλλά η ΓΛΩΣΣΑ του σχολείου δεν την υποστηρίζει. Θα μπορούσε κάποιος να φτιάξει μια συνάρτηση σύγκρισης, πχ για αριθμούς θα ήταν το πρόσημο(α-β), όπου αν το πρόσημο έδινε -1 θα είχαμε το α<β αν έδινε 0 θα είχαμε ισότητα και αν έδινε 1 θα είχαμε α>β, αλλά και πάλι στη ΓΛΩΣΣΑ λείπει η SGN() ή sign (πρόσημο).
Με την φυσαλίδα μπορούσαμε να κάνουμε την παρακάτω τεχνική της Διπλής Ταξινόμησης. Ωραία και απλά! Δεν ήταν ιδιαίτερα δύσκολο για την πλειοψηφία των μαθητών καθώς εδώ είχαμε διαδοχικούς ελέγχους και αντιμεταθέσεις γειτονικών στοιχείων! Όμως στην ταξινόμηση με επιλογή δεν έχει τέτοια λογική. Άρα πως θα μπορούσε να γίνει εκεί;
Για ί από 2 μέχρι 220
Για j από 220 μέχρι ί με_βήμα-1
Αν Μ[j-1]< Μ[j] τότε
Αντιμετάθεσε Τ[j-1], Τ[j]
Αντιμετάθεσε Μ[j-1], Μ[j]
Αλλιώς_αν Μ[j-1] = Μ[j] τότε
Αν Ε[j- 1] > Ε [j] τότε
ΑντιμετάθεσεT[j-1], T[j]
Τέλος_αν
Τέλος_αν
Τέλος_επανάληψης
Τέλος_επανάληψης
Με μπέρδεψες...ο πίνακας Ε[] τι θέλει εκεί;
Παράθεση από: anestis85 στις 14 Ιαν 2018, 06:43:03 ΜΜ
Όμως στην ταξινόμηση με επιλογή δεν έχει τέτοια λογική. Άρα πως θα μπορούσε να γίνει εκεί;
Η λογική είναι παρόμοια. Ο κώδικας είναι :
Για i από 1 μέχρι Ν - 1
θέση_min ← i
Για k από i + 1 μέχρι Ν
Αν A[k] < A[θέση_min] ή (A[k] = A[θέση_min] και Β[k] < Β[θέση_min]) τότε
θέση_min ← k
Τέλος_αν
Τέλος_επανάληψης
Αντιμετάθεσε A[i], A[θέση_min]
Αντιμετάθεσε Β[i], Β[θέση_min]
Τέλος_επανάληψηςΤα κριτήρια ταξινόμησης μπορεί να είναι διαφορετικά.