Καλησπέρα σας.
Ερώτηση μαθητή μου: Στην ταξινόμηση όταν ο πίνακας περιέχει λογικά δεδομένα στηρίζεται στην αλφαβητική σειρά?
Του απάντησα ότι δεν γίνεται αλφαβητικά και του πρότεινα τον παρακάτω (έστω ότι θέλουμε να μπουν πρώτα τα ΑΛΗΘΗΣ):
ΓΙΑ κ ΑΠΟ 2 ΜΕΧΡΙ Ν
ΓΙΑ λ ΑΠΟ Ν ΜΕΧΡΙ κ ΜΕ_ΒΗΜΑ -1
ΑΝ Α[λ-1] = ΨΕΥΔΗΣ ΚΑΙ Α[λ] = ΑΛΗΘΗΣ ΤΟΤΕ
temp <-- A[λ-1]
A[λ-1] <-- Α[λ]
Α[λ] <-- temp
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Θα ήθελα, λοιπόν να ρωτήσω αν είναι αποδεκτός ο παραπάνω κώδικας ή πρέπει στην δομή επιλογής να υπάρχει συγκριτικός τελεστής για να θεωρηθεί αλγόριθμος ταξινόμησης ευθείας ανταλλαγής?
Απλή παρατήρηση: Δεν χρειάζεται η temp
αφού ξέρουμε ότι Α[λ-1] = ΨΕΥΔΗΣ και η Α[λ] = ΑΛΗΘΗΣ
με αυτά είμαστε εντάξει!
Α[λ-1] <-- ΑΛΗΘΗΣ
Α[λ] <-- ΨΕΥΔΗΣ
Η ταξινόμηση χρειάζεται διάταξη. Μεταξύ των λογικών τιμών δεν ορίζεται διάταξη.
Κατά συνέπεια δεν έχει νόημα.
Αν θες να τα ξεχωρίσεις, μπορείς απλά να μετρήσεις πόσα είναι αληθής και να θέσεις τόσα κελιά σε αυτή την τιμή και τα υπολοιπα να τα βάλεις ψευδή.
Νομίζω κάποια χρόνια πριν είχε πέσει σχετικό θέμα.
Στη ΓΛΩΣΣΑ δεν ορίζεται διάταξη λογικών εκφράσεων. Αυτό σημαίνει ότι δεν μπορούμε να πούμε ότι το "ΨΕΥΔΗΣ" είναι μικρότερο ή μεγαλύτερο του "ΑΛΗΘΗΣ", είναι απλά διαφορετικά.
ΕΜΕΙΣ όμως μπορούμε να ορίσουμε ότι θέλουμε. Να υλοποιήσουμε εμείς μια συνάρτηση διάταξης λογικών όπου το ΑΛΗΘΗΣ θεωρείται μεγαλύτερο του ΨΕΥΔΗΣ:
ΣΥΝΑΡΤΗΣΗ Διάταξη(α, β): ΑΚΕΡΑΙΑ
ΑΡΧΗ
ΑΝ α = β ΤΟΤΕ
Διάταξη <- 0
ΑΛΛΙΩΣ_ΑΝ α = ΑΛΗΘΗΣ ΤΟΤΕ
Διάταξη <- 1
ΑΛΛΙΩΣ
Διάταξη <- -1
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
(Οι τιμές -1, 0, 1 είναι αντίστοιχες της strcmp της C)
Με αυτό το σκεπτικό, εφόσον ορίσαμε εμείς συνάρτηση διάταξης, ικανοποιείται και ο ορισμός της ταξινόμησης (το κουτί με τον επιστημονικό ορισμό με τη συνάρτηση διάταξης).
Και εκ των υστέρων, εφόσον έχεις κάνει ακριβώς το ίδιο πράγμα, απλά χωρίς να ορίσεις τυπικά τη συνάρτηση, ε, μια χαρά είναι η ταξινόμησή σου. :)
Θέλει μόνο προσοχή το ότι δεν ορίζεται αυτόματα αυτή η διάταξη. Θα πρέπει να οριστεί είτε από τον θεματοδότη είτε από τον λύτη.
Αντίστοιχη "προσαρμοσμένη συνάρτηση διάταξης" μπορούμε να ορίσουμε και για αριθμούς, π.χ. "ταξινομήστε έναν πίνακα ακεραίων με βάση το ποιος είναι πιο κοντά στο μηδέν, να είναι και πιο κοντά στην αρχή του πίνακα". Και εκεί η λύση θέλει απλά μια απόλυτη τιμή στην ΑΝ, δεν χρειάζεται ξεχωριστή υλοποίηση συνάρτησης.
Τι μου θύμισες Παναγιώτη, ήταν το θέμα Β2 του 2013. Η εκφώνηση ήταν :
Έστω μονοδιάστατος πίνακας Π[100], του οποίου τα στοιχεία περιέχουν τις λογικές τιμές ΑΛΗΘΗΣ και ΨΕΥΔΗΣ. Να γραφεί τμήμα αλγορίθμου που χωρίς τη χρήση «αλγορίθμων ταξινόμησης» να τοποθετεί στις πρώτες θέσεις του πίνακα την τιμή ΑΛΗΘΗΣ και στις τελευταίες την τιμή ΨΕΥΔΗΣ.
Δηλαδή ήθελαν λύση χωρίς τη χρήση αλγορίθμων ταξινόμησης. Η λύση που πρότειναν είναι ίδια με αυτή που προτείνεις εσύ. Μόνο που υπήρχε ένα ...... μικρό πρόβλημα.
Ο αλγόριθμος αυτός είναι γνωστός ως Counting Sort (https://en.wikipedia.org/wiki/Counting_sort) και είναι αλγόριθμος ταξινόμησης.
Δηλαδή ζήταγαν λύση χωρίς αλγόριθμο ταξινόμησης και έδιναν αλγόριθμο ταξινόμησης!
Άρα το θέμα είχε επιστημονικό λάθος, όμως δεν ασχολήθηκε κανένας.
ΥΓ. Προφανώς εννοούσαν comparison sort, αλλά άλλο τι έχεις στο μυαλό του και άλλο τι λες.