Αποστολέας Θέμα: Φυσαλίδα σε πίνακα με λογικές τιμές  (Αναγνώστηκε 797 φορές)

giannakos

  • Οπαδός
  • **
  • Μηνύματα: 10
Φυσαλίδα σε πίνακα με λογικές τιμές
« στις: 26 Μάι 2020, 11:21:51 μμ »
Καλησπέρα σας.

Ερώτηση μαθητή μου: Στην ταξινόμηση όταν ο πίνακας περιέχει λογικά δεδομένα στηρίζεται στην αλφαβητική σειρά?

Του απάντησα ότι δεν γίνεται αλφαβητικά και του πρότεινα τον παρακάτω (έστω ότι θέλουμε να μπουν πρώτα τα ΑΛΗΘΗΣ):

ΓΙΑ κ ΑΠΟ 2 ΜΕΧΡΙ Ν
     ΓΙΑ λ ΑΠΟ Ν ΜΕΧΡΙ κ ΜΕ_ΒΗΜΑ -1
          ΑΝ Α[λ-1] = ΨΕΥΔΗΣ ΚΑΙ Α[λ] = ΑΛΗΘΗΣ ΤΟΤΕ
               temp <-- A[λ-1]
               A[λ-1] <-- Α[λ]
               Α[λ] <-- temp
          ΤΕΛΟΣ_ΑΝ
     ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Θα ήθελα, λοιπόν να ρωτήσω αν είναι αποδεκτός ο παραπάνω κώδικας ή πρέπει στην δομή επιλογής να υπάρχει συγκριτικός τελεστής για να θεωρηθεί αλγόριθμος ταξινόμησης ευθείας ανταλλαγής?

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 492
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: Φυσαλίδα σε πίνακα με λογικές τιμές
« Απάντηση #1 στις: 27 Μάι 2020, 12:53:45 πμ »
Απλή παρατήρηση: Δεν χρειάζεται η temp
αφού ξέρουμε ότι  Α[λ-1] = ΨΕΥΔΗΣ  και η  Α[λ] = ΑΛΗΘΗΣ
με αυτά είμαστε εντάξει!
 Α[λ-1] <-- ΑΛΗΘΗΣ
 Α[λ] <--  ΨΕΥΔΗΣ

pgrontas

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 1426
  • There are always possibilities...
Απ: Φυσαλίδα σε πίνακα με λογικές τιμές
« Απάντηση #2 στις: 27 Μάι 2020, 12:50:59 μμ »
Η ταξινόμηση χρειάζεται διάταξη. Μεταξύ των λογικών τιμών δεν ορίζεται διάταξη.
Κατά συνέπεια δεν έχει νόημα.

Αν θες να τα ξεχωρίσεις, μπορείς απλά να μετρήσεις πόσα είναι αληθής και να θέσεις τόσα κελιά σε αυτή την τιμή και τα υπολοιπα να τα βάλεις ψευδή.
Νομίζω κάποια χρόνια πριν είχε πέσει σχετικό θέμα.
Programs must be written for people to read, and only incidentally for machines to execute - Harold Abelson

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 5523
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Φυσαλίδα σε πίνακα με λογικές τιμές
« Απάντηση #3 στις: 27 Μάι 2020, 01:23:35 μμ »
Στη ΓΛΩΣΣΑ δεν ορίζεται διάταξη λογικών εκφράσεων. Αυτό σημαίνει ότι δεν μπορούμε να πούμε ότι το "ΨΕΥΔΗΣ" είναι μικρότερο ή μεγαλύτερο του "ΑΛΗΘΗΣ", είναι απλά διαφορετικά.

ΕΜΕΙΣ όμως μπορούμε να ορίσουμε ότι θέλουμε. Να υλοποιήσουμε εμείς μια συνάρτηση διάταξης λογικών όπου το ΑΛΗΘΗΣ θεωρείται μεγαλύτερο του ΨΕΥΔΗΣ:

Κώδικας: ΓΛΩΣΣΑ
  1. ΣΥΝΑΡΤΗΣΗ Διάταξη(α, β): ΑΚΕΡΑΙΑ
  2. ΑΡΧΗ
  3.   ΑΝ α = β ΤΟΤΕ
  4.     Διάταξη <- 0
  5.   ΑΛΛΙΩΣ_ΑΝ α = ΑΛΗΘΗΣ ΤΟΤΕ
  6.     Διάταξη <- 1
  7.   ΑΛΛΙΩΣ
  8.     Διάταξη <- -1
  9.   ΤΕΛΟΣ_ΑΝ
  10. ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

(Οι τιμές -1, 0, 1 είναι αντίστοιχες της strcmp της C)

Με αυτό το σκεπτικό, εφόσον ορίσαμε εμείς συνάρτηση διάταξης, ικανοποιείται και ο ορισμός της ταξινόμησης (το κουτί με τον επιστημονικό ορισμό με τη συνάρτηση διάταξης).
Και εκ των υστέρων, εφόσον έχεις κάνει ακριβώς το ίδιο πράγμα, απλά χωρίς να ορίσεις τυπικά τη συνάρτηση, ε, μια χαρά είναι η ταξινόμησή σου. :)

Θέλει μόνο προσοχή το ότι δεν ορίζεται αυτόματα αυτή η διάταξη. Θα πρέπει να οριστεί είτε από τον θεματοδότη είτε από τον λύτη.

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3513
  • to Iterate is human to Recurse divine
Απ: Φυσαλίδα σε πίνακα με λογικές τιμές
« Απάντηση #4 στις: 27 Μάι 2020, 01:37:17 μμ »
Τι μου θύμισες Παναγιώτη, ήταν το θέμα Β2 του 2013. Η εκφώνηση ήταν :
Έστω μονοδιάστατος πίνακας Π[100], του οποίου τα στοιχεία περιέχουν τις λογικές τιμές ΑΛΗΘΗΣ και ΨΕΥΔΗΣ. Να γραφεί τμήμα αλγορίθμου που χωρίς τη χρήση «αλγορίθμων ταξινόμησης» να τοποθετεί στις πρώτες θέσεις του πίνακα την τιμή ΑΛΗΘΗΣ και στις τελευταίες την τιμή ΨΕΥΔΗΣ.

Δηλαδή ήθελαν λύση χωρίς τη χρήση αλγορίθμων ταξινόμησης. Η λύση που πρότειναν είναι ίδια με αυτή που προτείνεις εσύ. Μόνο που υπήρχε ένα ...... μικρό πρόβλημα.
Ο αλγόριθμος αυτός είναι γνωστός ως Counting Sort και είναι αλγόριθμος ταξινόμησης.
Δηλαδή ζήταγαν λύση χωρίς αλγόριθμο ταξινόμησης και έδιναν αλγόριθμο ταξινόμησης!
Άρα το θέμα είχε επιστημονικό λάθος, όμως δεν ασχολήθηκε κανένας.

ΥΓ. Προφανώς εννοούσαν comparison sort, αλλά άλλο τι έχεις στο μυαλό του και άλλο τι λες.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr