Ταξινόμηση σε δισδιάστατους πίνακες???

[bookitsa]

Γεια σας..
Έβαλα σε τεστ μια ερώτηση Σ-Λ από το βιβλίο του κυρίου Τσιωτάκη που έχει ως εξής:
Η ταξινόμηση της φυσαλίδας μπορεί να εφαρμοστεί και σε δισδιάστατους πίνακες.
Από τις απαντήσεις στο πίσω μέρος του βιβλίου είδα ότι είναι λάθος, γεγονός που το ήξερα, γιατί και στο σχολικό βιβλίο η ταξινόμηση λαμβάνει χώρα σε μονοδιάστατους πίνακες.
Καποια παιδιά λοιπόν αντέδρασαν στο λάθος γιατί μου είπαν ότι σε φροντιστήρια έχουν κάνει την ταξινόμηση και σε δισδιάστατους πίνακες.
Είναι αυτό δυνατόν?

[sstergou]

Έστω ότι έχεις ένα μονοδιάστατο πίνακα 10 θέσεων στον οποίο είναι αποθηκευμένοι οι βαθμοί ενός φοιτητή σε 10 μαθήματα.
Εάν ταξινομήσεις τον πίνακα θα πάρεις τους βαθμούς του φοιτητή είτε σε αύξουσα είτε σε φθίνουσα σειρά.

Ένας αντίστοιχος δισδιάστατος πίνακας με  50 γραμμές και 10 στήλες μπορεί να χρησιμοποιηθεί για να αποθηκέυσεις τους βαθμούς 50 φοιτητών στα 10 μαθήματα. Τι θα κάνεις αν θες να ταξινομήσεις τους βαθμούς του κάθε φοιτητή ώστε να φαίνονται σε φθίνουσα σειρά;
Θα ταξινομήσεις τον δισδιάστατο ανά γραμμή με όποια μέθοδο ταξινόμησης μονοδιάστατου θες αφού κάθε γραμμή του δισδιάστατου είναι ένας μονοδιάστατος πίνακας.

Το ίδιο μπορεί να γίνει και με τις στήλες.

Η ταξινόμηση φυσσαλίδας έτσι όπως είναι ορισμένη στο βιβλίο χρησιμοποιείται μόνο σε μονοδιάστατους πίνακες. Με μια μικρή τροποποίηση όμως μπορείς να την χρησιμοποιήσεις για να ταξινομήσεις κάθε γραμμή του δισδιάστατου.

[evry]

  Η ταξινόμηση των γραμμών ενός πίνακα δυο διαστάσεων δε νομίζω ότι είναι σωστή, διότι έτσι χαλάς τον πίνακα, δηλαδή πριν την ταξινόμηση ξέρεις ότι οι βαθμοί του φοιτητή i στα 10 μαθήματα είναι Β[i,1], Β[i,2], Β[i,3], ..., Β[i,10] και ότι οι βαθμοί όλων των φοιτητών στο τυχαίο j μάθημα είναι Β[1, j], Β[2, j], Β[3, j], ..., Β[50, j]. Μετά την ταξινόμηση όμως,  η τυχαία στήλη j του πίνακα δεν θα έχει τους βαθμούς των φοιτητών στο j μάθημα αλλά τον j-οστό μεγαλύτερο βαθμό κάθε φοιτητή. Έτσι χαλάς τη σημασιολογία του πίνακα και δεν ξέρεις μετά ο κάθε βαθμός ποιου μαθήματος είναι.
    Δηλαδή η ταξινόμηση σε πίνακα δυο διαστάσεων εκτός του ότι δεν είναι ορισμένη στο βιβλίο δεν έχει και νόημα ορισμού γενικότερα, δε μπορώ να φανταστώ κάποια εφαρμογή της γενικότερα.
   Όσον αφορά το πρόβλημα στο οποίο αναφέρεσαι, δηλαδή την ταξινόμηση των βαθμών των φοιτητών σε φθίνουσα σειρά είναι απλή ταξινόμηση της κάθε γραμμής του πίνακα σαν να πρόκειται για μονοδιάστατο. Ωστόσο όπως είπα και πριν χαλάς τη σημασία που έχει ο πίνακας.
  Από την άλλη όλα είναι θέμα ορισμού..

Ένας αντίστοιχος δισδιάστατος πίνακας με  50 γραμμές και 10 στήλες μπορεί να χρησιμοποιηθεί για να αποθηκέυσεις τους βαθμούς 50 φοιτητών στα 10 μαθήματα. Τι θα κάνεις αν θες να ταξινομήσεις τους βαθμούς του κάθε φοιτητή ώστε να φαίνονται σε φθίνουσα σειρά;
Θα ταξινομήσεις τον δισδιάστατο ανά γραμμή με όποια μέθοδο ταξινόμησης μονοδιάστατου θες αφού κάθε γραμμή του δισδιάστατου είναι ένας μονοδιάστατος πίνακας.

Το ίδιο μπορεί να γίνει και με τις στήλες.

Η ταξινόμηση φυσσαλίδας έτσι όπως είναι ορισμένη στο βιβλίο χρησιμοποιείται μόνο σε μονοδιάστατους πίνακες. Με μια μικρή τροποποίηση όμως μπορείς να την χρησιμοποιήσεις για να ταξινομήσεις κάθε γραμμή του δισδιάστατου.

[alkisg]

Άλλο καθημερινό παράδειγμα:
Ανοίγουμε τον τηλεφωνικό κατάλογο του ΟΤΕ και βλέπουμε ότι πρόκειται για δισδιάστατο πίνακα πολλών γραμμών και 5 στηλών ταξινομημένων ανά ονοματεπώνυμο, με παράλληλο πίνακα τηλεφώνων.
Μάλιστα αν κάποιος θέλει μπορεί να θεωρήσει τις σελίδες ως τρίτη διάσταση, εκφράζοντάς τον έτσι με 3σδιάστατο πίνακα.

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

Αν έχεις όρεξη διάβασε και αυτά:
https://alkisg.mysch.gr/steki/index.php?topic=310.0
https://alkisg.mysch.gr/steki/index.php?topic=794.0

[sstergou]

  Η ταξινόμηση των γραμμών ενός πίνακα δυο διαστάσεων δε νομίζω ότι είναι σωστή, διότι έτσι χαλάς τον πίνακα, δηλαδή πριν την ταξινόμηση ξέρεις ότι οι βαθμοί του φοιτητή i στα 10 μαθήματα είναι .....και ότι οι βαθμοί όλων των φοιτητών στο τυχαίο j μάθημα είναι......Μετά την ταξινόμηση όμως,  η τυχαία στήλη j του πίνακα δεν θα έχει τους βαθμούς των φοιτητών στο j μάθημα αλλά τον j-οστό μεγαλύτερο βαθμό κάθε φοιτητή

Το ίδιο όμως συμβαίνει και με τους μονοδιάστατους.

Όταν αντιμεταθέτεις στοιχεία των οποίων η θέση σημαίνει κάτι, πρέπει να κάνεις και κάποια πράγματα παραπάνω. Στο προηγούμενο παράδειγμα η θέση δεν σημαίνει τίποτε, μάλλον έπρεπε να το τονίσω.

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

[bookitsa]

Ουσιαστικά απ'ότι καταλαβαίνω στην ταξινόμηση δισδιάστατων πινάκων αναφερόμαστε στην ταξινόμηση γραμμής ή στήλης, δηλαδή και πάλι σε ταξινόμηση μονοδιάστατου πίνακα.Οπότε στο ερώτημά μου απαντάμε ότι γίνεται η ταξινόμηση σε δισδιάστατους πίνακες?Να το πιάσω σωστό δηλαδή στα παιδιά?

[evry]

  Άλκη στην περίπτωση του τηλεφωνικού καταλόγου που λες, αν υποθέσουμε ότι ο κατάλογος δεν είναι ταξινομημένος και τον ταξινομήσουμε με βάση το όνομα όπως λες, τότε δεν ταξινομούμε όπως λέει ο sstergou αλλά πρέπει σε κάθε αντιμετάθεση να αλλάζουμε και τα τηλέφωνα, δηλαδή τα τηλέφωνα να ακολουθούν το όνομα, σαν να είχαμε μια παράλληλη ταξινόμηση 5 πινάκων, όπως είπες.
    Το παράδειγμα που ψάχνω είναι μια ταξινόμηση κάθε γραμμής ή στήλης του πίνακα ξεχωριστά. Δηλαδή στην πρώτη στήλη να είναι τα ελάχιστα ή μέγιστα κάθε γραμμής κλπ. Στην περίπτωση του τηλεφωνικού καταλόγου αυτό δεν ισχύει.

[alkisg]

Το ερώτημα της bookitsa δεν είναι συγκεκριμένα για την περίπτωση που έθεσε ο Στάθης, αλλά γενικά, αν υφίσταται ταξινόμηση σε δισδιάστατους. Προφανώς και υφίσταται, αρκεί να ορίσουμε πως τη θέλουμε.

Τώρα για την περίπτωση που είπε ο Στάθης:
α) Παράδειγμα που να παίζει ρόλο η θέση:
Θέλουμε να ταξινομήσουμε τις βαθμολογίες των μαθητών ενός σχολείου ανά τμήμα. Έχουμε λοιπόν ένα δισδιάστατο πίνακα βαθμολογιών όπου οι γραμμές εκφράζουν τους μαθητές και οι στήλες τα τμήματα. Έχουμε κι έναν παράλληλο δισδιάστατο πίνακα με τα ονόματα.
Έτσι κάνουμε ταξινομήσεις ανά στήλη, και επειδή έχουμε και παράλληλο πίνακα, σε κάθε αντιμετάθεση βαθμολογιών αντιμεταθέτουμε και τα ονόματα.
Το να χρησιμοποιήσουμε μονοδιάστατους δεν θα βόλευε, γιατί αν είχαμε 10 τμήματα θα έπρεπε να γράφουμε 10 φορές τον ίδιο κώδικα, ενώ τώρα ξεμπερδεύουμε με μια τρίτη ΓΙΑ (2 ΓΙΑ για κάθε φυσαλίδα + 1 ακόμα για όλες τις στήλες).

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

[pgrontas]

Ανοίγουμε τον τηλεφωνικό κατάλογο του ΟΤΕ και βλέπουμε ότι πρόκειται για δισδιάστατο πίνακα πολλών γραμμών και 5 στηλών ταξινομημένων ανά ονοματεπώνυμο, με παράλληλο πίνακα τηλεφώνων.

Θα διαφωνήσω σε αυτό. Ο κατάλογος του ΟΤΕ είναι ΜΟΝΟΔΙΑΣΤΑΤΟΣ πίνακας εγγραφών. Άσχετα αν οι εγγραφές έχουν μπει χωρικά σε στήλες και σελίδες για να μην σέρνουμε μια ουρά από χαρτί.

Για μένα ταξινόμηση σε δισδιάστατο γενικά δεν υφίσταται γιατί δεν μπορείς να ορίσεις συνάρτηση διάταξης.
Έστω ένας πίνακας με βαθμολογίες μαθητών σε μαθήματα (Γραμμές μαθητές - Στήλες μάθημα).
Δεν έχει νόημα - δεν είναι λογικό - να συγκρίνεις την βαθμολογία του μαθητή I στο μάθημα J με την βαθμολογία του μαθητή Κ στο  μάθημα Λ.
Αν απλά πεις ότι συγκρίνεις βαθμολογίες, τότε ουσιαστικά καταργείς τις δύο διαστάσεις (μαθητής -μάθημα) και τις μετατρέπεις σε μία - βαθμολογίες.

[sstergou]

Για μένα ταξινόμηση σε δισδιάστατο γενικά δεν υφίσταται γιατί δεν μπορείς να ορίσεις συνάρτηση διάταξης.

Μα γιατί όχι!

Δεν έχει νόημα - δεν είναι λογικό - να συγκρίνεις την βαθμολογία του μαθητή I στο μάθημα J με την βαθμολογία του μαθητή Κ στο  μάθημα Λ.
Αν απλά πεις ότι συγκρίνεις βαθμολογίες, τότε ουσιαστικά καταργείς τις δύο διαστάσεις (μαθητής -μάθημα) και τις μετατρέπεις σε μία - βαθμολογίες.

Μα δεν συγκρίνουμε στοιχεία από διαφορετικές γραμμές αλλά στοιχεία από την ίδια γραμμή. Δεν έχει νόημα να συγκρίνουμε τις διαδοχικές βαθμολογίες του ίδιου μαθητή μεταξύ τους και να τις ταξινομήσουμε (αν και εφόσον δεν μας ενδιαφέρουν τα μαθήματα στα οποία τις πέτυχε) και θέλουμε απλά να τις εμφανίσουμε σε φθίνουσα σειρά;

Στην ουσία δεν μιλάμε για δισδιάστατο αλλά για πολλούς μονοδιάστατους......

Άμα η ταξινόμηση αναφέρεται στην αντιμετάθεση ολόκληρων γραμμών ; Δηλαδή για να χρησιμοποιήσω παράδειγμα παρόμοιο με του ʼλκη:
Έχω 30 αχθοφόρους με 20 βαλίτσες ο καθένας και έρχονται φορτηγά τα οποία φορτώνονται και ξαναφεύγουν. Αυτό που θέλω να κάνω είναι να φορτώνονται πρώτα οι βαλίτσες του αχθοφόρου που έχει υπό την ευθύνη του τα περισσότερα κιλά.
Οπότε σύμφωνα με τον ορισμό του βιβλίου, έχω τα στοιχεία a1,a2,an τα οποία αναφέρονται στους μονοδιάστατους πίνακες των αχθοφόρων
και ορίζω σαν συνάρτηση διάταξης την f όπου f(a1) θα είναι το άθροισμα των κιλών των βαλιτσών του πρώτου αχθοφόρου κοκ.

Ομοίως μπορώ να ορίσω για οποιαδήποτε διάσταση.

[sstergou]

Παράδειγμα με φοιτητές 2η έκδοση 
Γραμμές=φοιτητές, στήλες=μαθήματα

Κώδικας: Ψευδογλώσσα

Για ι από 1 μέχρι 10
  Διάβασε ΌνομαΜαθήματος[ι]
Τέλος_επανάληψης

Για ι από 1 μέχρι 30
  Για j από 1 μέχρι 10
    Διάβασε Βαθμοί[ι,j]
    ΌνοματαΜαθημάτωνΦοιτητή[ι,j] <- ΌνομαΜαθήματος[j]
  Τέλος_επανάληψης
Τέλος_επανάληψης

Για κ από 1 μέχρι 30
  Για ι από 2 μέχρι 10
    Για j από 10 μέχρι ι με_βήμα -1
      Αν Βαθμοί[κ, j-1] < Βαθμοί[κ, j] τότε
        αντιμετάθεσε Βαθμοί[κ, j-1], [κ, j]
        αντιμετάθεσε ΌνοματαΜαθημάτωνΦοιτητή[κ, j-1], ΌνοματαΜαθημάτωνΦοιτητή[κ, j]
      τέλος_αν
    Τέλος_επανάληψης
  Τέλος_επανάληψης
Τέλος_επανάληψης

Για ι από 1 μέχρι 30
  Για j από 1 μέχρι 10
    Εμφάνισε Βαθμοί[ι, j], " στο μάθημα ", ΌνοματαΜαθημάτωνΦοιτητή[ι, j]
  Τέλος_επανάληψης
Τέλος_επανάληψης

Αν θέλω μπορώ να το επεκτείνω ώστε να εμφανίζεται πρώτα ο φοιτητής με το μεγαλύτερο μέσο όρο κοκ

[P.Tsiotakis]

Ουσιαστικά απ'ότι καταλαβαίνω στην ταξινόμηση δισδιάστατων πινάκων αναφερόμαστε στην ταξινόμηση γραμμής ή στήλης, δηλαδή και πάλι σε ταξινόμηση μονοδιάστατου πίνακα.

Αυτή ακριβώς είναι η φιλοσοφία της ερώτησης. Η ταξινόμηση φυσαλίδας εφαρμόζεται σε μονοδιάστατους πίνακες. Δεν εφαρμόζεται σε δισδιάστατους πίνακες γενικά.
Εφαρμόζεται σε ΜΙΑ διάσταση ενός δισδιάστατου πίνακα (ή προς τη γραμμή ή ως προς τη στήλη, όλες τις γραμμές/στήλες ή και μόνο μια γραμμή/στήλη). Γι αυτό και απαντάται ως Λάθος.

Ο δισδιάστατος πίνακας Κ[Μ, Ν] δεν ταξινομείται, καθώς τα ΜxN στοιχεία του πως θα διαταχθούν;

Εγώ θα την έκοβα στο διαγώνισμα. Μερικές Σ/Λ ερωτήσεις στην προετοιμασία μπαίνουν για να μας θυμίζουν κάτι. Μετά τη συζήτηση στην τάξη, θα το θυμούνται οι μαθητές. Και κυρίως θα θυμούνται πως πρέπει να διαβάζουν την ερώτηση και να σκέφτονται.

Άλλο παράδειγμα είναι και η άσκηση 8 στο http://users.kor.sch.gr/ptsiotakis/aepp/aepp_ask3_4.htm
αλλά και το θέμα 4, στα περσινά θέματα του ΟΕΦΕ

[sstergou]

Αν ταξινομήσω τους φοιτητές ανάλογα με το μέσο όρο και τους βαθμούς τους κατά φθίνουσα σειρά τότε τι γίνεται;

Πόσες διαστάσεις έχω;

Η εντολή

SELECT * FROM users ORDERBY firstname τι κάνει; Δεν ταξινομεί δισδιάστατο πίνακα;

[P.Tsiotakis]

Στη ΓΛΩΣΣΑ η εντολή   SELECT * FROM users ORDERBY firstname

παραβιάζει την καθοριστικότητα και την αποτελεσματικότητα

[sstergou]

Να πάρει... με πιάσανε!!

[pgrontas]

Η εντολή

SELECT * FROM users ORDERBY firstname τι κάνει; Δεν ταξινομεί δισδιάστατο πίνακα;

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

[sstergou]

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

Μα αυτό είναι ο δισδιάστατος  : ένας πίνακας εγγραφών, μόνο που οι εγγραφές είναι πίνακες, κάθε πεδίο είναι στήλη.

Γιατί θα πρέπει να σκεφτόμαστε την ταξινόμηση δισδιάστατων όπως αυτή των μονοδιάστατων;

Δηλ :
Μονοδιάστατος : Ν στοιχεία, οπότε ταξινόμηση : διάταξη Ν στοιχείων
Δισδιάστατος : Μ*Ν στοιχεία, οπότε ταξινόμηση : διάταξη Μ*Ν στοιχείων

Για μένα αυτό είναι λάθος. Ο edit: δισδιάστατος δεν είναι απλά μια διάταξη Μ*Ν στοιχείων αλλά Μ στοιχεία που το καθένα από αυτά έχει Ν στοιχεία.

Οπότε δεν είναι σωστό να βάλω όλα αυτά τα στοιχεία σε αύξουσα ή φθίνουσα σειρά, πρέπει να λάβω υπόψη μου και άλλα πράγματα.

Ο πίνακας, η ταξινόμηση, η φυσαλίδα είναι πράγματα που υπήρχαν και υπάρχουν και θα υπάρχουν, άσχετα με το μάθημα της ΑΕΠΠ στην ββάθμια.

Η ταξινόμηση δισδιάστατων υπάρχει, τώρα αν στο μάθημά μας δεν υπάρχει.... 

[alkisg]

Θα διαφωνήσω σε αυτό. Ο κατάλογος του ΟΤΕ είναι ΜΟΝΟΔΙΑΣΤΑΤΟΣ πίνακας εγγραφών. Άσχετα αν οι εγγραφές έχουν μπει χωρικά σε στήλες και σελίδες για να μην σέρνουμε μια ουρά από χαρτί.

Περί ...υλοποιήσεως... κολοκυθόπιτα (πώς λέμε περί ορέξεως).
Και ο δισδιάστατος πίνακας του Excel με τις γνωστές γραμμές και στήλες, εσωτερικά ΔΕΝ είναι πίνακας αλλά ένα σωρό δυναμικές δομές δεδομένων.
Μην το σκέφτεσαι για το πώς θα το υλοποιούσες αν έφτιαχνες το "κείμενο σε στήλες" του Word και είχες να κάνεις page layout.

Πες ότι σου έδιναν ένα δισδιάστατο πινακάκι με κονκάρδες με ονόματα. Φυσικό, χειροπιαστό, καμία σχέση με προγραμματισμό. Και σου έλεγαν "ταξινόμησέ το όπως φαίνονται τα ονόματα σε έναν τηλεφωνικό κατάλογο". Τι θα έκανες; Δεν θα εφάρμοζες φυσαλίδα κατευθείαν πάνω στο δισδιάστατο πινακάκι με τις κονκάρδες; Ή θα τα ξάπλωνες όλα κάτω στο χώμα, φτιάχνοντας ουσιαστικά ένα ακόμα μονοδιάστατο πινακάκι, ώστε να μπορείς να εφαρμόσεις φυσαλίδα σε μονοδιάστατο;
Κι αν δεν είχες χώμα; Δηλαδή, αν π.χ. δεν ήταν ονόματα αλλά κάτι σε υγρή μορφή, και είχες μόνο ένα επιπλέον κουβαδάκι (=temp);

Γενικότερα περί Πληροφορικής, ΑΕΠΠ και θεμάτων: Όταν δίνουμε κάποια ερώτηση στο μάθημα, θα πρέπει να προσέχουμε ώστε η απάντηση να είναι σύμφωνη και με την Πληροφορική γενικότερα, όχι μόνο με την ύλη του μαθήματος. Αλλιώς και ένας δάσκαλος της πρώτης δημοτικού θα έχει δίκιο να βάζει θέματα του στυλ
"γίνεται να χωρίσουμε τον αριθμό 3 σε δύο ίσα μέρη;"
και να απαιτεί από τους μαθητές να απαντούν "όχι" επειδή δεν έχουν μάθει ακόμα δεκαδικούς αριθμούς. Κι αν ένα παιδί χωρίσει 3 μήλα σε 1,5 και 1,5 θα πρέπει να του πει "όχι, κάνεις λάθος, αυτό δεν γίνεται".

[alkisg]

Και ένα ακόμα πιο καθημερινό παράδειγμα,
έστω ότι έχουμε ένα ράφι από σουπερμάρκετ με γάλατα μακράς διαρκείας και θέλουμε να φέρουμε τα πιο παλιά μπροστά.

Δεν είναι ούτε ανά γραμμή ούτε ανά στήλη. Μάλιστα δεν μας ενδιαφέρει καν αν στην πρώτη γραμμή τα παλιότερα είναι αριστερά ή δεξιά.
Όμως προφανώς ΕΙΝΑΙ ταξινόμηση δισδιάστατου πίνακα, απλά με λίγο περίεργη συνάρτηση διάταξης.

[sstergou]

Ενδιαφέρουσα προσέγγιση αυτή με τα γάλατα.
Θεωρούμε ότι υπάρχει μια κάποια διάταξη πριν την ταξινόμηση κάπως έτσι : οι αριθμοί είναι οι μέρες πριν την ημερομηνία λήξης.

1η γραμμή :777766
   2η          666555
                554444
                444333
                333222
                222111

Για ι από Μ μέχρι (Ν div 2) με_βήμα -1 ! άρτιος αριθμός γραμμών
   Για j από Ν μέχρι 1 με_βήμα -1
     Αντιμετάθεσε Π[ι,j] Π[Μ-ι+1,Ν-j+1)]
  Τέλος_επανάληψης
Τέλος_επανάληψης

[alkisg]

Στάθη θέλει τρία ΓΙΑ, επειδή π.χ. οι αρχικές τιμές μπορεί να είναι

123456
723456
723456
723456
777111

οπότε θα πρέπει όλα τα 7ρια να βγουν στην πρώτη γραμμή.

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

[pgrontas]

Και ένα ακόμα πιο καθημερινό παράδειγμα,
έστω ότι έχουμε ένα ράφι από σουπερμάρκετ με γάλατα μακράς διαρκείας και θέλουμε να φέρουμε τα πιο παλιά μπροστά.

Δεν είναι ούτε ανά γραμμή ούτε ανά στήλη. Μάλιστα δεν μας ενδιαφέρει καν αν στην πρώτη γραμμή τα παλιότερα είναι αριστερά ή δεξιά.
Όμως προφανώς ΕΙΝΑΙ ταξινόμηση δισδιάστατου πίνακα, απλά με λίγο περίεργη συνάρτηση διάταξης.

Σε όλα τα παραδείγματα που αναφέρεις μπερδεύεις περιορισμούς που υφίστανται λόγω έλλειψης χώρου με την δεύτερη διάσταση του πίνακα.
Στο ράφι με γάλατα επειδή κάθε ράφι έχει περιορισμένο χώρο τα γάλατα διπλώνουν προς τα πίσω, σχηματίζοντας δεύτερη, τρίτη σειρά κόκ. Πρόκειται όμως για μονοδιάστατο πίνακα.
Στο κατάλογο του ΟΤΕ οι εγγραφές μπαίνουν σε σελίδες και στήλες για να αποφευχθεί να είναι ο κατάλογος ένας τεράστιος πάπυρος που διπλώνει. (όταν αναφέρυμε σε εγγραφές δεν έχει καμία σχέση με την υλοποίηση - μια εγγραφή είναι μια αναπαράσταση ενός αντικειμένου με πολλές ιδιότητες - αλλά παραμένει ένα αντικείμενο).
Στην παρέλαση οι μαθητές μπαίνουν σε στήλες για παρόμοιο λόγο.
Όλα αυτά μπορεί να φαίνονται ως δύο διαστάσεις (επειδή έτσι διατάσσονται οπτικά) αλλά είναι μία.
Δύο διαστάσεις έχουμε στο παράδειγμα του βιβλίου (κεφ. 9 νομίζω) με τις θερμοκρασίες. Κάθε θερμοκρασία αναλύεται σε ότι αφορά τον μήνα (διάσταση 1) και σε ότι αφορά την πόλη (διάσταση 2). Η σημασία του κάθε δεδομένου είναι διαφορετική (δίνει διαφορετική πληροφορία) ανάλογα  με την διάσταση που κοιτας. Δεν μπορείς να πεις το ίδιο και για τα  γάλατα ή τα υπόλοιπα.

Εννοιολογικά λοιπόν τα περιεχόμενα ενός δισδιάστατου πίνακα πρέπει να ερμηνευθούν με δύο τρόπους. Η ταξινόμηση όμως (για να έχει κάποιο νόημα το αποτέλεσμα της) πρέπει να διατάξει τα δεδομένα κατά ένα τρόπο. Για αυτό κατά τη γνώμη μου δεν έχει νόημα η ταξινόμηση δισδιάστατου (τεχνικά μπορεί να γίνει με δεκαπέντε τρόπους - αλλά πάντα θα αφαιρεί την μία διάσταση).
Τα ταξινομημένα δεδομένα δηλαδή θα χάσουν το νόημα τους.

[sstergou]

Σε όλα τα παραδείγματα που αναφέρεις μπερδεύεις περιορισμούς που υφίστανται λόγω έλλειψης χώρου με την δεύτερη διάσταση του πίνακα

Έχεις ένα μονοδιάστατο πίνακα με βάρη δεμάτων τα οποία θα διανεμηθούν σε ένα συγκεκριμένο προορισμό από μια ταχυδρομική εταιρεία.
Πως ονομάζεται η διαδικασία με την οποία ο πίνακας θα αναδιαταχθεί έτσι ώστε :

στην 1η θέση να υπάρχει το πιο βαρύ, στην 2η το δεύτερο κοκ.

Έχεις έναν δισδιάστατο πίνακα όπου κάθε γραμμή αντιστοιχεί σε έναν προορισμό και κάθε στήλη σε βάρη δεμάτων τα οποία πρέπει να διανεμηθούν από μια ταχυδρομική εταιρεία στον προορισμό της γραμμής στην οποία ανήκουν.

Πως ονομάζεται η διαδικασία με την οποία ο πίνακας θα αναδιαταχθεί έτσι ώστε :

α)Στην 1η γραμμή να είναι ο προορισμός με τα πιο βαριά δέματα, στην 2η ο δεύτερος κοκ
β)Στην 1η στήλη της πρώτης γραμμής θα υπάρχει το πιο βαρύ δέμα του 1ου προορισμού, στην 2η το δεύτερο κοκ;

Αυτό δεν είναι ταξινόμηση;

[alkisg]

Παναγιώτη, έχω την εντύπωση ότι μπερδεύεις τον ορισμό της συνάρτησης διάταξης με τη διάσταση των πινάκων.

Προφανώς κάθε πολυδιάστατος πίνακας μπορεί να αναπαρασταθεί με μονοδιάστατο, αφού έχει σταθερό αριθμό στοιχείων.
Επίσης προφανώς κάθε ταξινόμηση είναι "μονοδιάστατη", αφού αυτός είναι ο ορισμός της συνάρτησης διάταξης:
http://en.wikipedia.org/wiki/Total_order
http://en.wikipedia.org/wiki/Sorting_algorithm

Με το "μονοδιάστατη" εννοώ ότι θα υπάρχει συγκεκριμένη τελική σειρά,
a <= b <= c <= d κτλ.
η οποία είναι ...σε μία σειρά, "μονοδιάστατη".

Η συνάρτηση διάταξης όμως δεν έχει καμία σχέση με τη δομή στην οποία έχεις τα στοιχεία που θες να ταξινομήσεις. Μπορείς να ταξινομήσεις απλά στοιχεία (όχι πίνακα), μονοδιάστατους πίνακες, πολυδιάστατους πίνακες, λίστες με records, δέντρα, ακόμα και σύνολα (sets). Μάλιστα ο ορισμός της διάταξης (βλ. wikipedia) δίνεται σε set, όχι σε μονοδιάστατο πίνακα.


Ας αναλύσω λίγο περισσότερο δυο παραδείγματα μπας και σε πείσω:
1ο παράδειγμα: Αυτό με τα γάλατα.
Αρχική τιμή δισδιάστατου πίνακα:

1114
1124
4311
2231

όπου οι αριθμοί σημαίνουν πόσων ημερών παλιό είναι το γάλα.

Θέλουμε τα παλιά γάλατα να έρθουν μπροστά. Αυτό σημαίνει ότι η τελική πρώτη γραμμή μπορεί να είναι
4443 ή 4434 ή 4344 ή 3444

Δεν μας νοιάζει δηλαδή που θα μπει το γάλα των 3 ημερών στην πρώτη γραμμή. Με βάση την συνάρτηση διάταξης που θα πρέπει να επιλέξουμε το (4) στην πρώτη γραμμή είναι ΙΣΟ με το (3) στην πρώτη γραμμή.
(Αν θέλουμε να το φτάσουμε σε υλοποίηση, η συνάρτηση διάταξης εδώ εξαρτάται από το min στοιχείο της προηγούμενης γραμμής).

Πώς μπορείς να εκφράσεις αυτήν την ταξινόμηση με μονοδιάστατο;
Ναι, αν θες μπορείς να κάνεις div 4 και να χρησιμοποιήσεις μονοδιάστατο, αλλά δεν έχει νόημα. Σε δισδιάστατο είναι η σωστή φυσική αναπαράσταση του προβλήματος.


2ο παράδειγμα: "Polar" ταξινόμηση
Έστω πάλι ένας δισδιάστατος πίνακας,

1112
3344
4444
5555

Θέλω να ταξινομήσω τα στοιχεία με βάση την απόστασή τους από το "κέντρο των αξόνων", δηλαδή με βάση το πόσο απέχει (distance) το (i,j) από το Α[1,1]. Σαν να έχει μέλι η πάνω αριστερή γωνία του πίνακα και να θέλουν όλοι οι μικροί αριθμοί να πάνε πιο κοντά σ' αυτήν.
Αποδεκτό αποτέλεσμα:

1134
1244
3445
4455

Προφανώς δεν έχει νόημα να αναπαραστήσεις το πρόβλημα με μονοδιάστατο. Θα μπορούσες, αν ήθελες. Αλλά η φυσική του αναπαράσταση είναι με δισδιάστατο.



Πέρα από όλα τα παραπάνω:
Η Πληροφορική δεν εξετάζει μόνο τις optimal λύσεις. Εξετάζει και τις λύσεις υπό περιορισμούς. Ναι, θεωρητικά θα μπορούσες να βάλεις όλα τα γάλατα σε μονοδιάστατο πίνακα και να κάνεις απλή φυσαλίδα. Από το σουπερμάρκετ όμως σου θέτουν τον περιορισμό (και χωρικό και εννοιολογικό) ότι τα χρειάζονται σε δισδιάστατο. Είμαστε σε σουπερμάρκετ του 2100 που έχει δύο ηλεκτρονικά χεράκια πάνω από το ράφι που ταξινομούν τα γάλατα και σου λένε απλά να τα προγραμματίσεις, αλλά δεν έχουν να σου δώσουν άλλο ράφι που να χωράει 100 γάλατα σε μία διάσταση.
Επομένως δεν έχεις καν "μνήμη" (=θέση) για μονοδιάστατο πίνακα, ούτε καν για temp, το μόνο που μπορείς να κάνεις με δύο ηλεκτρονικά χέρια είναι swap.
Από την άλλη όμως σου δίνουν και πιο relaxed κριτήρια ταξινόμησης, αφού το 4434 είναι ισοδύναμο με το 4443 σαν πρώτη γραμμή.
Έτσι μελετώντας το συγκεκριμένο πρόβλημα που σου δίνουν μπορείς να καταλήξεις ακόμα και σε κάποιον πιο γρήγορο αλγόριθμο ταξινόμησης, το οποίο δεν θα το κατάφερνες αν τα έβαζες σε μονοδιάστατο και αδιαφορούσες για τα πιο relaxed κριτήρια.

[alkisg]

Για να καταλήξω σε συμπέρασμα,

• Η ταξινόμηση ορίζεται σε οποιοδήποτε σύνολο (set). Επομένως τα στοιχεία του συνόλου (αντίθετα π.χ. από τη δομή bag) πρέπει να είναι διατεταγμένα, να μπορούμε να πούμε ποιο θεωρούμε πρώτο, ποιο δεύτερο κτλ.
• Εφόσον υπάρχει το αντίστοιχο πρόβλημα, μπορούμε να θεωρήσουμε διατεταγμένα τα στοιχεία οποιαδήποτε δομής, είτε απλών μεταβλητών (α, β, γ, δ), είτε μονοδιάστατων πινάκων, είτε δισδιάστατων, είτε λιστών, είτε δέντρων.
• Επομένως, με βάση τα δύο παραπάνω, η ταξινόμηση ορίζεται σε δισδιάστατους πίνακες, αρκεί να υπάρχει διάταξη των στοιχείων με βάση το πρόβλημα.
  

Στο παραπάνω παράδειγμα με την "polar" ταξινόμηση του δισδιάστατου πίνακα,
πρώτο στοιχείο του δισδιάστατου πίνακα θεωρούμε το Α[1,1],
δεύτερο το Α[1,2],
τρίτο στοιχείο το Α[2,1]
τέταρτο στοιχείο το Α[2,2]
πέμπτο στοιχείο το Α[1,3]
κτλ
Και τα ταξινομούμε σαν να ταξινομούσαμε μονοδιάστατο, αλλάζοντας με την κατάλληλη συνάρτηση τη διάταξη των δεικτών i, j. Αυτό όμως δε σημαίνει ότι έχει νόημα να τα βάλουμε σε μονοδιάστατο. Δισδιάστατο ταξινομούμε.

Επίσης στο παράδειγμα με τα ονόματα και τα τηλέφωνα
πρώτο στοιχείο του μονοδιάστατου πίνακα θεωρούμε το Α[1],
δεύτερο το Α[3]
τρίτο το A[5]
κτλ.
Δεν παίζει ρόλο που είναι μονοδιάστατος, δεν παίρνουμε τα στοιχεία με τη "μαθηματική" τους σειρά. Το διατεταγμένο σύνολο πάνω στο οποίο θα γίνει η ταξινόμηση είναι το {A[1], A[3], A[5] ...}.

[pgrontas]

Βασικά εξακολουθώ να διαφωνώ:

1ο παράδειγμα: Αυτό με τα γάλατα.
Αρχική τιμή δισδιάστατου πίνακα:

1114
1124
4311
2231

Γιατί να τα βάλεις σε δισδιάστατο; Ποιες είναι οι διαστάσεις; Τι αντιπροσωπεύει το στοιχείο (i,j); Mην μου πεις την θέση στο ράφι γιατί αυτό είναι φυσική διάταξη και δεν προσφέρει πληροφορία.

2ο παράδειγμα: "Polar" ταξινόμηση
Έστω πάλι ένας δισδιάστατος πίνακας,

1112
3344
4444
5555

Θέλω να ταξινομήσω τα στοιχεία με βάση την απόστασή τους από το "κέντρο των αξόνων", δηλαδή με βάση το πόσο απέχει (distance) το (i,j) από το Α[1,1]. Σαν να έχει μέλι η πάνω αριστερή γωνία του πίνακα και να θέλουν όλοι οι μικροί αριθμοί να πάνε πιο κοντά σ' αυτήν.
Αποδεκτό αποτέλεσμα:

1134
1244
3445
4455

Προφανώς δεν έχει νόημα να αναπαραστήσεις το πρόβλημα με μονοδιάστατο. Θα μπορούσες, αν ήθελες. Αλλά η φυσική του αναπαράσταση είναι με δισδιάστατο.

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

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

Σε όλα τα παραδείγματα που αναφέρεις μπερδεύεις περιορισμούς που υφίστανται λόγω έλλειψης χώρου με την δεύτερη διάσταση του πίνακα

Έχεις ένα μονοδιάστατο πίνακα με βάρη δεμάτων τα οποία θα διανεμηθούν σε ένα συγκεκριμένο προορισμό από μια ταχυδρομική εταιρεία.
Πως ονομάζεται η διαδικασία με την οποία ο πίνακας θα αναδιαταχθεί έτσι ώστε :

στην 1η θέση να υπάρχει το πιο βαρύ, στην 2η το δεύτερο κοκ.

Έχεις έναν δισδιάστατο πίνακα όπου κάθε γραμμή αντιστοιχεί σε έναν προορισμό και κάθε στήλη σε βάρη δεμάτων τα οποία πρέπει να διανεμηθούν από μια ταχυδρομική εταιρεία στον προορισμό της γραμμής στην οποία ανήκουν.

Πως ονομάζεται η διαδικασία με την οποία ο πίνακας θα αναδιαταχθεί έτσι ώστε :

α)Στην 1η γραμμή να είναι ο προορισμός με τα πιο βαριά δέματα, στην 2η ο δεύτερος κοκ
β)Στην 1η στήλη της πρώτης γραμμής θα υπάρχει το πιο βαρύ δέμα του 1ου προορισμού, στην 2η το δεύτερο κοκ;

Αυτό δεν είναι ταξινόμηση;

Δεν κατάλαβα τι ακριβώς θα περιέχει ο δισδιάστατος πίνακας. Αν θες εξήγησε μου περισσότερο

[alkisg]

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

Εσύ αν κατάλαβα καλά θα έφτιαχνες ένα μονοδιάστατο πίνακα αποστάσεων, τον οποίο θα τον είχες σαν παράλληλο με τις τιμές βαλμένες σε μονοδιάστατο πίνακα, και θα ταξινομούσες τις αποστάσεις.

Έτσι θα χρειαζόσουν διπλάσια RAM. Ας υποθέσουμε ότι δεν την είχες (είτε μικροελεγκτής με περιορισμένη RAM είτε πίνακας πολλών Gb). Δεν έχει λοιπόν λόγο ύπαρξης η ταξινόμηση κατευθείαν σε δισδιάστατο;

Δεχόμαστε νομίζω κι οι δυο, ότι οποιοδήποτε πρόβλημα λύνεται με μονοδιάστατους, μπορεί να λυθεί και με δισδιάστατους και αντίστροφα. Όμως στο συγκεκριμένο χαλάς τη φυσική πληροφορία (i,j), η οποία στο δισδιάστατο δε χρειάζεται να αποθηκευτεί, και όταν το ανάγεις σε μονοδιάστατο αναγκάζεσαι να την μετατρέπεις στο κριτήριο ταξινόμησης (απόσταση) και να την κρατάς σε ένα δεύτερο μονοδιάστατο. Μάλιστα έτσι έχασες και την αρχική πληροφορία της θέσης, δηλαδή αν σου έλεγαν να κάνεις animation με το πώς γίνεται live η ταξινόμηση, θα έπρεπε να κρατάς άλλους δύο παράλληλους πίνακες με τα i και j.
(Με το live εννοώ αν στο ζητούσαν συγκεκριμένα να το βλέπουν σε δισδιάστατο, λόγω της φύσης του προβλήματος, ότι δηλαδή η θέση έχει κάποιο φυσικό νόημα.)


Νομίζω όμως ότι θα συμφωνήσουμε πιο γρήγορα αν βάλουμε στη συζήτηση και άλλες δομές.
Ας πάρουμε τα binary search trees. Αυτά είναι ταξινομημένα με βάση τη διάσχιση inorder.

Άρα, καταρχάς ορίζεται η ταξινόμηση και σε άλλες δομές εκτός από μονοδιάστατους πίνακες. Λογικό είναι, αφού τα δέντρα είναι σύνολα (sets), αρκεί προηγουμένως να ορίζουμε ποια συνάρτηση διάταξης των στοιχείων θα επιλέξουμε (=διάσχιση inorder, preorder, postorder κτλ).

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

[pgrontas]

Εσύ αν κατάλαβα καλά θα έφτιαχνες ένα μονοδιάστατο πίνακα αποστάσεων, τον οποίο θα τον είχες σαν παράλληλο με τις τιμές βαλμένες σε μονοδιάστατο πίνακα, και θα ταξινομούσες τις αποστάσεις.

Αν ήθελα και την αρχική πληροφορία (τις τιμές) θα έφτιαχνα μονοδιάστατο εγγραφών (αποστάσεις,α[i,j]).

Έτσι θα χρειαζόσουν διπλάσια RAM. Ας υποθέσουμε ότι δεν την είχες (είτε μικροελεγκτής με περιορισμένη RAM είτε πίνακας πολλών Gb). Δεν έχει λοιπόν λόγο ύπαρξης η ταξινόμηση κατευθείαν σε δισδιάστατο;

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

Δεχόμαστε νομίζω κι οι δυο, ότι οποιοδήποτε πρόβλημα λύνεται με μονοδιάστατους, μπορεί να λυθεί και με δισδιάστατους και αντίστροφα.

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

τι διαφορετικό έχουν οι δισδιάστατοι από τα δέντρα;

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

Άλκη, η διαφωνία μου εμένα δεν είναι στο αν μπορεί να γίνει ταξινόμηση στοιχείων δισδιάστατου. Ασφαλώς και μπορεί.
Λέω ότι δεν έχει νόημα, ότι με την ταξινόμηση αναιρείς το λόγο που τα έβαλες σε δισδιάστατο.

[alkisg]

Ο λόγος που τα βάζεις σε δισδιάστατο ορίζεται από το πρόβλημα, όχι από την ταξινόμηση. Η ταξινόμηση είναι απλά ένα μικρό κομμάτι του όλου προβλήματος, δεν είναι αυτοσκοπός.

Δυο ερωτησούλες για να καταλάβω που ακριβώς είναι η διαφωνία μας, ώστε να βρω πιο κατάλληλο παράδειγμα.
Έστω ότι μια εταιρία έχει λύσει ένα πρόβλημα χρησιμοποιώντας δισδιάστατο πίνακα στο κυρίως πρόγραμμα. Και σου αναθέτουν εσένα ΜΟΝΟ να φτιάξεις μια
ΔΙΑΔΙΚΑΣΙΑ ΤαξινόμησηΔισδιάστατου(Α, N, M)
που θα τον ταξινομεί με κάποιον από τους παραπάνω τρόπους που λέγαμε.

Εσύ λοιπόν θα μετέτρεπες το δισδιάστατο σε μονοδιάστατο, θα έκανες ταξινόμηση, και στη συνέχεια θα τον ξαναέκανες δισδιάστατο για να τους τον επιστρέψεις.
Εγώ θα ταξινομούσα απευθείας το δισδιάστατο.

Η αντίρρησή σου ποια από τις δύο είναι;
α) Ότι ο δικός σου κώδικας θα είναι πιο λογικός/ευκολοδιάβαστος από το δικό μου;
β) Ή ότι η εταιρία έκανε λάθος και δεν έπρεπε να χρησιμοποιεί δισδιάστατο στο κυρίως πρόγραμμα;

[alkisg]

Υ.Γ. για το κλασσικό puzzle που παίζαμε μικροί,


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

[pgrontas]

Ο λόγος που τα βάζεις σε δισδιάστατο ορίζεται από το πρόβλημα, όχι από την ταξινόμηση. Η ταξινόμηση είναι απλά ένα μικρό κομμάτι του όλου προβλήματος, δεν είναι αυτοσκοπός.

Σε αυτό συμφωνώ - πώς ήρθαμε στο συμπέρασμα αυτό από διαφορετικούς δρόμους είναι περίεργο

Εσύ λοιπόν θα μετέτρεπες το δισδιάστατο σε μονοδιάστατο, θα έκανες ταξινόμηση, και στη συνέχεια θα τον ξαναέκανες δισδιάστατο για να τους τον επιστρέψεις.
Εγώ θα ταξινομούσα απευθείας το δισδιάστατο.

Δεν θεωρώ ότι η μετατροπή ΔΙΣ->ΜΟΝ->ΤΑΞ->ΔΙΣ είναι ευκολοσυντήρητη, ούτε καν από αυτόν που έγραψε τον κώδικα. ΥΓ: και αυτό χακεριά είναι (με αρνητική όμως επίδραση στην απόδοση - σε σχέση με αυτήν που πρότεινες στην polar ταξινόμηση)

Η αντίρρησή σου ποια από τις δύο είναι;
α) Ότι ο δικός σου κώδικας θα είναι πιο λογικός/ευκολοδιάβαστος από το δικό μου;
β) Ή ότι η εταιρία έκανε λάθος και δεν έπρεπε να χρησιμοποιεί δισδιάστατο στο κυρίως πρόγραμμα;

Η αντίρρηση μου είναι στο Β. Δεν θα έπρεπε να χρησιμοποιηθεί δισδιάστατος εφόσον το πρόβλημα εμπεριέχει και ταξινόμηση.

[pgrontas]

Υ.Γ. για το κλασσικό puzzle που παίζαμε μικροί,


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

Αυτό το πρόβλημα οπτικά μόνο έχει δισδιάστατη αναπαράσταση - τα δεδομένα δεν σημαίνουν τίποτα.

[alkisg]

Όταν όμως ήθελες να δεις ποια κομμάτια μπορείς να κινήσεις, στο δισδιάστατο θα κοιτούσες τα
A[i-1,j], A[i+1,j], A[i,j-1], A[i,j+1]
όπου i,j η θέση της τρύπας (που στον κώδικα θα εκφραζόταν με μηδενικό). Το +-1 εδώ προφανώς εκφράζει προηγούμενη ή επόμενη γραμμή/στήλη. Κι αν ήθελες να ελέγξεις για τοίχωμα θα έλεγες αν i=1 ή i=N.

Αν το έκανες με μονοδιάστατο θα έπρεπε να κοιτάς τα κομμάτια
A[i-1], A[i+1], A[i-N], A[i+N]
όπου πλέον i είναι η θέση της τρύπας στο μονοδιάστατο.

Ουσιαστικά δηλαδή θα μετέτρεπες τις συντεταγμένες του μονοδιάστατου σε συντεταγμένες δισδιάστατου για τις ανάγκες του αλγορίθμου, προσθέτοντας ή αφαιρώντας Ν για να πας στην πάνω ή κάτω γραμμή. Κι αν ήθελες να ελέγξεις για τοίχωμα, θα έπρεπε να παίρνεις (i-1) mod N + 1 και (i-1) div N + 1 για να δεις αν είναι 1 ή Ν.

Δεν είναι πολύ πιο λογικό να αναπαρασταθεί απευθείας με δισδιάστατο;

[pgrontas]

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

Και εγώ συμφωνώ, και έτσι θα το έκανα πιθανότατα - αλλά στην περίπτωση αυτή τα περιεχόμενα δεν σημαίνουν τίποτα.
Αυτή είναι η διαφορά μας.

[alkisg]

Τι εννοείς; Τι θα έπρεπε να σημαίνουν τα δεδομένα; Πραγματικά μετά από αυτά δεν έχω καταλάβει τη διαφορά μας!
edit: Τι σημαίνουν π.χ. τα δεδομένα που είναι στην ταξινόμηση φυσαλίδας που παρουσιάζει το βιβλίο;

Ο δισδιάστατος πίνακας είναι απλά η δομή που βολεύει να χρησιμοποιήσουμε για να λύσουμε το πρόβλημα.
Τα δεδομένα π.χ. θα μπορούσαν να είναι records με τον αριθμό και με handles για bitmaps, ώστε να μπορούν να ζωγραφιστούν οι αντίστοιχες εικόνες του puzzle στην οθόνη του Η/Υ.

edit#2:

Ο λόγος που τα βάζεις σε δισδιάστατο ορίζεται από το πρόβλημα, όχι από την ταξινόμηση. Η ταξινόμηση είναι απλά ένα μικρό κομμάτι του όλου προβλήματος, δεν είναι αυτοσκοπός.

Σε αυτό συμφωνώ - πώς ήρθαμε στο συμπέρασμα αυτό από διαφορετικούς δρόμους είναι περίεργο

Η αντίρρησή σου ποια από τις δύο είναι;
α) Ότι ο δικός σου κώδικας θα είναι πιο λογικός/ευκολοδιάβαστος από το δικό μου;
β) Ή ότι η εταιρία έκανε λάθος και δεν έπρεπε να χρησιμοποιεί δισδιάστατο στο κυρίως πρόγραμμα;

Η αντίρρηση μου είναι στο Β. Δεν θα έπρεπε να χρησιμοποιηθεί δισδιάστατος εφόσον το πρόβλημα εμπεριέχει και ταξινόμηση.

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

[sstergou]

Δηλαδή, αυτό που καταλαβαίνω εγώ :

Ο δισδιάστατος πίνακας είναι μια δομή δεδομένων που τα δεδομένα χωρίζονται σε γραμμές και σε στήλες και κάθε δεδομένο μπορεί να προσπελαστεί χρησιμοποιώντας δύο δείκτες, αυτόν της γραμμής και αυτόν της στήλης.

Το να πούμε ότι το γεγονός ότι τα δεδομένα τα οποία βρίσκονται στην πρώτη γραμμή ή στην πρώτη στήλη σημαίνει κάτι (φοιτητής-μαθήματα) είναι μια παραδοχή που κάνουμε εμείς εφόσον μας βοηθάει για να λύσουμε το πρόβλημά μας.

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

Όσον αφορά το γεγονός ότι οι γραμμές και οι στήλες σημαίνουν κάτι π.χ. στο παράδειγμα με τους φοιτητές :
1η γραμμή - Φοιτητής : Παναγιώτης
2η γραμμή - Φοιτητής : Άλκης

...
1η στήλη - Μάθημα : Δίκτυα
2η στήλη - Μάθημα : Αλγόριθμοι

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

[alkisg]

Σχετικά με το να "σημαίνουν κάτι" οι γραμμές και οι στήλες (γραμμές = φοιτητές, στήλες = μαθήματα, περιεχόμενα = βαθμοί κτλ):

Όπως είπε και ο Στάθης, αυτό είναι υποπερίπτωση των προβλημάτων που μπορούν να αναπαρασταθούν με δισδιάστατο πίνακα. Δεν είναι υποχρέωση. Μπορούν απλά να σημαίνουν τη γραμμή και τη στήλη, όπως και στην ταξινόμηση φυσαλίδας το i εκφράζει απλά τη στήλη και όχι μαθήματα.

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

Για να βρούμε φυσικό παράδειγμα για την τρίτη περίπτωση, θα πρέπει και οι στήλες και οι γραμμές να εκφράζουν το ίδιο πράγμα. Π.χ. ομάδες και ομάδες. Θέση puzzle και θέση puzzle. Όχι όμως μαθήματα-φοιτητές, γιατί τότε δεν μπορούμε να κάνουμε αλλαγή στήλης.

Παναγιώτη, ένα τέτοιο παράδειγμα θα σε έπειθε; Να υπάρχει και ένας φυσικός τίτλος των γραμμών/στηλών πέρα από το "δίνεται ένας πίνακας με αριθμούς";

[pgrontas]

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

Αυτό πρέπει να το έχω πει καμιά 10αριά φορές 

Σχετικά με το να "σημαίνουν κάτι" οι γραμμές και οι στήλες (γραμμές = φοιτητές, στήλες = μαθήματα, περιεχόμενα = βαθμοί κτλ):

Όπως είπε και ο Στάθης, αυτό είναι υποπερίπτωση των προβλημάτων που μπορούν να αναπαρασταθούν με δισδιάστατο πίνακα. Δεν είναι υποχρέωση. Μπορούν απλά να σημαίνουν τη γραμμή και τη στήλη, όπως και στην ταξινόμηση φυσαλίδας το i εκφράζει απλά τη στήλη και όχι μαθήματα.

Η γραμμή και η στήλη είναι αποτέλεσμα της σημασίας.
Αν δεν σημαίνουν τίποτα γιατί να χρησιμοποίησεις δισδιάστατο-ας τα έχει χύμα - σε μονοδιάστατο.

[sstergou]

Αν δεν σημαίνουν τίποτα γιατί να χρησιμοποίησεις δισδιάστατο-ας τα έχει χύμα - σε μονοδιάστατο.

Γιατί να χρησιμοποιήσεις 50 μονοδιάστατους 10 στοιχείων (φοιτητές - μαθήματα) και όχι δισδιάστατο με 50 γραμμές και 10 στήλες. Γιατί να βάλεις αυτόν το περιορισμό;

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

Άμα είναι έτσι ο μονοδιάστατος πίνακας ο οποίος εκφράζει τους βαθμούς ενός φοιτητή σε 10 μαθήματα δεν πρέπει να ταξινομείται γιατί αλλάζει η σειρά των μαθημάτων.

Στο παράδειγμα του ʼλκη με τον παιχνίδι  οι γραμμές και οι στήλες σημαίνουν κάτι
Η 1η γραμμή του πίνακα ανιστοιχεί στην 1η γραμμή του παιχνιδιού, η 1η στήλη στην 1η στήλη του παιχνιδιού κοκ.

Χρειαζόμαστε κάτι παραπάνω από αυτό για να χρησιμοποιήσουμε δισδιάστατο;

[pgrontas]

Γιατί η ταξινόμηση των βαθμών στον μονοδιάστατο έχει νόημα και δεν έχει στον δισδιάστατο; Ποια είναι η διαφορά; Αν μπορώ να αντιμεταθέσω στοιχεία στον μονοδιάστατο γιατί να μην μπορώ να αντιμεταθέσω στοιχεία της ίδιας γραμμής στον δισδιάστατο; Και στην συνέχεια να αντιμεταθέσω και ολόκληρες γραμμές αν θέλω. Αυτή η αναδιάταξη δεν είναι μια ταξινόμηση;
Άμα είναι έτσι ο μονοδιάστατος πίνακας ο οποίος εκφράζει τους βαθμούς ενός φοιτητή σε 10 μαθήματα δεν πρέπει να ταξινομείται γιατί αλλάζει η σειρά των μαθημάτων

Αν αντιμεταθέσεις στοιχεία μιας γραμμής σε δισδιάστατο θα χαλάσεις το νόημα των δεδομένων.
Για τον μαθητή i1 θα αλλάξει οι βαθμός στο μάθημα j1 (θα αντιμετατεθεί με το j2), κάτι που δεν θα είναι σίγουρο ότι θα γίνει για όλες τις γραμμές-μαθητές. Οπότε για κάποιους θα οι βαθμοί στο ένα μάθημα θα είναι στην μια στήλη, για κάποιους στην άλλη. Μπορεί να αλλάξει και γραμμή και ξαφνικά θα αναφέρεται σε άλλο μαθητή. Προφανώς κάτι τέτοιο δεν μας επηρεάζει στον μονοδιάστατο ο οποίος θα περιέχει τους βαθμούς ενός μόνο μαθητή.
Στο παράδειγμα του ʼλκη με το παιχνίδι τα δεδομένα του δισδιάστατου δεν σημαίνουν τίποτα, οπότε μπορούν να μετακινηθούν.

Νομίζω ότι έχουμε μπει σε endless loop.
Δυστυχώς ούτε έχω πειστεί, αλλά ούτε σας έχω πείσει. Δεν πειράζει - δεν χρειάζεται να συμφωνούμε σε όλα - παρόλα αυτά η συζήτηση ήταν άκρως ενδιαφέρουσα.
Πάντως νομίζω ότι το καλύτερο παράδειγμα για το πού ορίζεται η ταξινόμηση, το δίνουν τα περισσότερα βιβλία αλγορίθμων και δομών δεδομένων, που στην ταξινόμηση αναφέρονται σε μονοδιάστατες δομές (πίνακες, λίστες).
Αυτό δεν νομίζω ότι είναι τυχαίο, ούτε παράλειψη.

[alkisg]

Παναγιώτη αν έχεις όρεξη επίτρεψέ μου να επιμείνω λίγο, γιατί νομίζω ότι υπάρχουν περιπτώσεις που δεν συζητήσαμε και θα ήθελα να ακούσω τη γνώμη σου γι' αυτές.

Η τρίτη ...υποπερίπτωση ταξινόμησης δισδιάστατου όπως την είπα παραπάνω είναι να μετακινούνται τα στοιχεία οπουδήποτε στον πίνακα. Σ' αυτό δεν βρήκα καλό παράδειγμα με "σημασία" στις γραμμές και στις στήλες (π.χ. μαθητές/βαθμοί), αν βρω θα ποστάρω. Δεν κατάλαβα όμως αν στα παραδείγματα χωρίς "σημασία" που έδωσα, θα έκανες τελικά ταξινόμηση δισδιάστατου ή όχι.

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

Η μονοδιάστατη version:
Φτιάξτε μια λίστα με τους μαθητές μιας τάξης, ταξινομημένη ανά βαθμολογία. Θεωρούμε ότι υπάρχουν Ν μαθητές, όπου 1 <= Ν <= 30, και το Ν θα μας το δώσει ο χρήστης.

Λύση: δηλώνουμε ένα πίνακα με 30 βαθμούς και έναν παράλληλο ακόμα με 30 ονόματα. Διαβάζουμε το Ν από το χρήστη, διαβάζουμε τα δεδομένα και κάνουμε κλασσική ταξινόμηση με παράλληλο πίνακα.

Η δισδιάστατη version:
Ένα σχολείο έχει Μ τμήματα, 1 <= Μ <= 10, με Ν μαθητές το καθένα, 1 <= Ν <= 30.
α) Για κάθε τμήμα κάντε λίστα ταξινομημένη ανά βαθμολογία
β) (εδώ ζητάμε κι άλλα πράγματα, π.χ. τους 3 καλύτερους κάθε τμήματος, απλά και μόνο για να υποχρεώσουμε τον προγραμματιστή να θυμάται τους βαθμούς και να μην μπορεί να χρησιμοποιήσει έναν μόνο πίνακα Ν στοιχείων)...

Λύση: Δηλώνουμε δύο δισδιάστατους ΜxN, έναν για τους βαθμούς και έναν παράλληλο για τα ονόματα.
Διαβάζουμε τον αριθμό τμημάτων Μ,
Για j από 1 μέχρι Μ
  Διαβάζουμε το Ν
  Διαβάζουμε τα ονόματα και τους βαθμούς και τα βάζουμε στη στήλη Μ των δισδιάστατων πινάκων,
  Ταξινομούμε τη στήλη Μ
κτλ κτλ



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

Η ερώτηση είναι, θεωρείς το παραπάνω παράδειγμα ταξινόμηση δισδιάστατου ή όχι; Κι αν όχι, γιατί; Πώς αλλιώς θα μπορούσε να λυθεί σε ΓΛΩΣΣΑ; (με χακιά γίνεται, χρησιμοποιείς ένα μόνο μονοδιάστατο με ΝxM στοιχεία και κάνεις αλλαγή συντεταγμένων από συντεταγμένες δισδιάστατου, αλλά νομίζω συμφωνούμε ότι γι' αυτό βγήκαν οι δισδιάστατοι, για να μην κάνουμε τέτοιες χακιές).


Υ.Γ. η ταξινόμηση και στο σχολικό βιβλίο της ΑΕΠΠ και στη wikipedia δεν ορίζεται σε πίνακες, αλλά σε sets ή σε λίστες, δηλαδή απλά σε διατεταγμένα στοιχεία.

[pgrontas]

Η τρίτη ...υποπερίπτωση ταξινόμησης δισδιάστατου όπως την είπα παραπάνω είναι να μετακινούνται τα στοιχεία οπουδήποτε στον πίνακα. Σ' αυτό δεν βρήκα καλό παράδειγμα με "σημασία" στις γραμμές και στις στήλες (π.χ. μαθητές/βαθμοί), αν βρω θα ποστάρω. Δεν κατάλαβα όμως αν στα παραδείγματα χωρίς "σημασία" που έδωσα, θα έκανες τελικά ταξινόμηση δισδιάστατου ή όχι.

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

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

Εφόσον δεν ξέρεις πόσες στήλες θα βάλεις ο δισδιάστατος κάπου χαλάει νομίζω.

Η ερώτηση είναι, θεωρείς το παραπάνω παράδειγμα ταξινόμηση δισδιάστατου ή όχι;

Για μένα είναι M ταξινομήσεις μονοδιάστατων.

Υ.Γ. η ταξινόμηση και στο σχολικό βιβλίο της ΑΕΠΠ και στη wikipedia δεν ορίζεται σε πίνακες, αλλά σε sets ή σε λίστες, δηλαδή απλά σε διατεταγμένα στοιχεία.

Ο μονοδιάστατος πίνακας είναι ο πιο κοντινός συγγενής αυτών στην ΑΕΠΠ.

Για μένα είναι περισσότερο αποδεκτό να 'στερήσεις την ερμηνεία' των δεδομένων από μονοδιάστατο (βλέποντας τα δηλαδή ως λίστα upd:με προσπέλαση Ο(1)) παρά από δισδιάστατο (Ο δισδιάστατος θεωρώ πρέπει να έχει κάποιον ειδικό λόγο ύπαρξης - την επιπλέον πληροφορία που προσφέρουν οι δύο διαστάσεις)

[alkisg]

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

Επιφυλάσσομαι μέχρι να βρω σχετικό παράδειγμα, αλλά και μόνο χωρική έννοια να έχουν, αυτό δεν αναιρεί το γεγονός ότι χρειαζόμαστε ταξινόμηση δισδιάστατου.

Εφόσον δεν ξέρεις πόσες στήλες θα βάλεις ο δισδιάστατος κάπου χαλάει νομίζω.

Όχι, αυτό είναι λάθος.
Σε μονοδιάστατο πάλι βάζουμε άνω όριο: μέχρι 30 μαθητές.
Σε δισδιάστατο πάλι βάζουμε άνω όριο: μέχρι 10 τμήματα.
Είναι ακριβώς το ίδιο πράγμα, απλά σε μία δεύτερη διάσταση.

Για μένα είναι M ταξινομήσεις μονοδιάστατων.

ΟΚ, δώσε μια λύση της παραπάνω άσκησης σε ΓΛΩΣΣΑ. Δε νομίζω ότι γίνεται!
(πέρα από τη χακιά του να χρησιμοποιήσεις ΕΝΑΝ μόνο μονοδιάστατο με ΝxΜ στοιχεία).

(Ο δισδιάστατος θεωρώ πρέπει να έχει κάποιον ειδικό λόγο ύπαρξης - την επιπλέον πληροφορία που προσφέρουν οι δύο διαστάσεις)

Η επιπλέον πληροφορία στο παραπάνω παράδειγμα είναι τα τμήματα.

[pgrontas]

ΟΚ, δώσε μια λύση της παραπάνω άσκησης σε ΓΛΩΣΣΑ. Δε νομίζω ότι γίνεται!
(πέρα από τη χακιά του να χρησιμοποιήσεις ΕΝΑΝ μόνο μονοδιάστατο με ΝxΜ στοιχεία).

Εφόσον κάνεις το ίδιο πράγμα Μ φορές, δεν καταλαβαίνω γιατί δεν μπορεί να γίνει.

[alkisg]

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

Έτσι θα αναγκαστείς να δηλώσεις Μ μονοδιάστατους πίνακες. Δεν μπορείς όμως να δηλώσεις Μ, πρέπει να δηλώσεις συγκεκριμένο αριθμό.
Έτσι δηλώνεις 10 μονοδιάστατους πίνακες, τον Α1, τον Α2, τον Α3 κτλ. Δεν θα τους χρησιμοποιήσεις όμως όλους, αλλά τους Μ πρώτους από αυτούς.

Πώς μπορείς όμως να κάνεις επανάληψη με διαφορετικά ονόματα μεταβλητών; Δεν μπορείς. Χρειάζεσαι δισδιάστατο πίνακα.

Για ακριβώς τον ίδιο λόγο που χρειάζεσαι μονοδιάστατους (=μαθητές), όταν το πρόβλημα έχει και δεύτερη διάσταση (=τμήματα), χρειάζεσαι δισδιάστατους.

[pgrontas]

Νομίζω ότι το πρόβλημα στο συγκεκριμένο παράδειγμα αφορά μόνο την υλοποίηση σε ΓΛΩΣΣΑ. Σε αλγόριθμο γίνεται ή σε μια γλώσσα που επιτρέπει να δημιουργείς έναν πίνακα on the fly, όποτε τον χρειαστείς.
Στον τελικό δισδιάστατο θα αποθηκεύσεις μόνο αυτά που χρειάζεσαι ως απάντηση. Και γιατί στο τέλος χρησιμοποιείς δισδιάστατο; Επειδή θέλεις να αναλύσεις τα δεδομένα σε δύο διαστάσεις - όχι για ταξινόμηση.

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

Έτσι θα αναγκαστείς να δηλώσεις Μ μονοδιάστατους πίνακες. Δεν μπορείς όμως να δηλώσεις Μ, πρέπει να δηλώσεις συγκεκριμένο αριθμό.
Έτσι δηλώνεις 10 μονοδιάστατους πίνακες, τον Α1, τον Α2, τον Α3 κτλ. Δεν θα τους χρησιμοποιήσεις όμως όλους, αλλά τους Μ πρώτους από αυτούς.

Πώς μπορείς όμως να κάνεις επανάληψη με διαφορετικά ονόματα μεταβλητών; Δεν μπορείς. Χρειάζεσαι δισδιάστατο πίνακα.

Για ακριβώς τον ίδιο λόγο που χρειάζεσαι μονοδιάστατους (=μαθητές), όταν το πρόβλημα έχει και δεύτερη διάσταση (=τμήματα), χρειάζεσαι δισδιάστατους.

[alkisg]

Το να πεις ότι δεν χρειαζόμαστε δισδιάστατους αν μπορούμε να δημιουργήσουμε μονοδιάστατους on the fly,
είναι το ίδιο με το να λες ότι δεν χρειαζόμαστε μονοδιάστατους πίνακες αν η γλώσσα που χρησιμοποιούμε μας επιτρέπει να δημιουργούμε μεταβλητές on the fly.

Η απώλεια μνήμης με τη χρήση δισδιάστατου είναι ακριβώς ίδια με την απώλεια μνήμης μονοδιάστατου: εφόσον μας λένε ότι το πολύ θα έχουμε Μ*Ν βαθμούς, η στατική μας δομή πρέπει να έχει Μ*Ν θέσεις.

Αλλάζω την εκφώνηση και δίνω πλέον συγκεκριμένα νούμερα Μ και Ν:
έχουμε ακριβώς 100 τμήματα με ακριβώς 100 μαθητές το κάθε ένα.

Δεν είναι προφανές ότι πρέπει να χρησιμοποιηθεί δισδιάστατος;
Δεν είναι προφανές ότι χρειαζόμαστε ταξινόμηση δισδιάστατου, έστω ανά στήλη;


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

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

[pgrontas]

Το να πεις ότι δεν χρειαζόμαστε δισδιάστατους αν μπορούμε να δημιουργήσουμε μονοδιάστατους on the fly,
είναι το ίδιο με το να λες ότι δεν χρειαζόμαστε μονοδιάστατους πίνακες αν η γλώσσα που χρησιμοποιούμε μας επιτρέπει να δημιουργούμε μεταβλητές on the fly.

Όχι γιατί θα κρατήσεις όσα θες από τον κάθε μονοδιάστατο.

Δεν είναι προφανές ότι χρειαζόμαστε ταξινόμηση δισδιάστατου, έστω ανά στήλη;

Εφόσον κάθε 'στήλη' ταξινομείται ΑΝΕΞΑΡΤΗΤΑ, είναι προφανές για μένα ότι δεν χρειάζεται δισδιάστατος.

Όπως είπα και πριν διαφωνούμε. Η διαφωνία μας νομίζω δεν είναι τεχνικό θέμα αλλά είναι θέμα διαφορετικής φιλοσοφίας που έχουμε στην χρησιμότητα ενός δισδιάστατου. Δεν είναι κακό.

[gpapargi]

Καλημέρα

Επιτέλους μια θεωρητική κουβέντα με συμμετοχή.

Λοιπόν επειδή η συζήτηση άναψε το ΣΚ δεν την έχω παρακολουθήσει, αλλά έψαχνα μια αφορμή να γράψω μερικές σκέψεις που έκανα μετά την περυσινή κουβέντα.

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

Ας ξεχάσουμε για λίγο τους πίνακες και ας μιλήσουμε μόνο για την έννοια της ταξινόμησης.
Για να υπάρχει ταξινόμηση ν στοιχείων καταρχήν πρέπει να υπάρχει ένα κριτήριο ως προς το οποίο θα συγκριθούν τα στοιχεία. Η πιο απλή περίπτωση είναι να συγκρίνουμε τις τιμές τους. Αλλά δεν υπάρχει λόγος  να περιοριστούμε μόνο σε απλή σύγκριση των τιμών. Μπορεί να θέλουμε να συγκρίνουμε τα τετράγωνα των αριθμών ή τους κύβους τους ή γενικά την τιμή που έχουν μέσω μιας τυχαίας συνάρτησης f. Αυτή η συνάρτηση που αποτελεί το κριτήριο ως προς το οποίο θα γίνει η σύγκριση είναι η ordering function (συνάρτηση διάταξης) που λέει το βιβλίο στον ορισμό της σελίδας 66.

Πχ αν θέλουμε να ταξινομήσουμε τα στοιχεία ανάλογα με το ποιο έχει το μικρότερο ημίτονο τότε η ordering function f είναι η f(x) = ημ(x). Για κάθε αριθμό βρίσκουμε το ημίτονό του και αυτά τα ημίτονα των αριθμών είναι που συγκρίνουμε τελικά και κατατάσσουμε τους αριθμούς.     Αν θέλουμε μια απλή αύξουσα ταξινόμηση (δηλαδή απλώς να συγκρίνουμε τις τιμές των στοιχείων) τότε ουσιαστικά επιλέγουμε σαν ordering function την f(x) = x. Δηλαδή η τιμή (εικόνα) κάθε αριθμού μέσω της ordering function είναι ο ίδιος του ο εαυτός και έτσι πετυχαίνουμε απλά να συγκρίνουμε τις τιμές των στοιχείων (κι ας είναι μέσω της f). Αν θέλουμε να κάνουμε φθίνουσα ταξινόμηση απλά επιλέγουμε σαν ordering function την f(x) = -x και τελικά συγκρίνουμε τα στοιχεία ως προς το πιο έχει τον μικρότερο αντίθετο (άρα ως προς το ποιο είναι το μεγαλύτερο). Η χρήση της ordering function είναι πολύ βολική γιατί δεν χάνουμε αυτά που έχουμε (αύξουσα/φθίνουσα ταξινόμηση) και κερδίζουμε τη δυνατότητα να έχουμε επιλογή ως προς το κριτήριο ταξινόμησης.

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

Το δεύτερο που χρειάζεται για να γίνει η ταξινόμηση είναι η διάταξη των φυσικών χώρων που θα αποθηκεύσουν τα στοιχεία. Δηλαδή να ξεκαθαρίσουμε που θα μπει το πρώτο στοιχείο, που θα μπει το δεύτερο κλπ.

Αυτό που αισθάνομαι είναι ότι η ταξινόμηση είναι μονοδιάστατο πρόβλημα (προσοχή: καμία σχέση με μονοδιάστατο πίνακα). Για να γίνει κατανοητό αυτό που λέω, ας φανταστούμε ότι έχουμε ένα οικόπεδο σε ανώμαλο έδαφος (λοφάκια κλπ). Μέσα στο οικόπεδο επιλέγουμε κάποια σημεία σε τελείως τυχαίες θέσεις. Ορίζουμε λοιπόν κάποιο σημείο ως αυτό στο οποίο θα τοποθετήσουμε το πρώτο στοιχείο της ταξινόμησης, κάποιο άλλο σημείο ως  αυτό στο οποίο θα τοποθετήσουμε το δεύτερο στοιχείο της ταξινόμησης κλπ. Μπορεί το πρώτο να είναι δίπλα με το πέμπτο και πολύ μακριά από το δεύτερο. Όταν λέω ότι το πρόβλημα της ταξινόμησης είναι μονοδιάστατο εννοώ ότι μπορούμε να ενώσουμε με μια καμπύλη όλα τα σημεία στα οποία θα αποθηκευτούν τα ταξινομημένα στοιχεία μας και αυτή η καμπύλη θα πρέπει να περνάει από τα σημεία με τη σειρά. Πρώτα από το πρώτο μετά από το δεύτερο (κι ας είναι μακριά από το πρώτο) μετά από το τρίτο (που μπορεί να είναι κοντά στο πρώτο) κλπ. Η καμπύλη θα έχει τυχαίο σχήμα αλλά μόνο μία διάσταση. Παρά το ότι τα σημεία αποθήκευσης είναι διάσπαρτα στον δισδιάστατο χώρο του οικοπέδου (τρισδιάστατο αν λάβουμε υπόψη ότι υπάρχουν και λοφάκια),  η καμπύλη που τα διατρέχει ένα προς ένα με τη σειρά, είναι μονοδιάστατη. Αυτό είναι που λέει το βιβλίο «να τοποθετηθούν σε μια σειρά». Ανεξάρτητα από το που βρίσκονται οι χώροι αποθήκευσης των στοιχείων, η σειρά κάποιον πραγμάτων είναι έννοια μονοδιάστατη.

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

Πάμε τώρα στους πίνακες.

Αν έχουμε ορίσει την ordering function το μόνο που μας μένει είναι η διάταξη των αποθηκευτικών χώρων. Σε ένα μονοδιάστατο πίνακα τα κελιά είναι διατεταγμένα από μόνα τους, οπότε μπορούμε να χρησιμοποιήσουμε τη διάταξη των κελιών του πίνακα σαν διάταξη των αποθηκευτικών χώρων των στοιχείων μας. Κάποιος μπορεί να πει ότι είναι κάπως αυθαίρετο το να χρησιμοποιήσουμε την υπάρχουσα φυσική διάταξη των κελιών του μονοδιάστατου. Γιατί να μη βάλουμε το πρώτο στοιχείο της ταξινόμησης στην πέμπτη θέση του πίνακα, το δεύτερο στην όγδοη κλπ. Σωστό. Αλλά αν χρησιμοποιήσουμε ένα μονοδιάστατο πίνακα για να κρατήσουμε τη διάταξη των κελιών, τότε θα χρησιμοποιηθεί σε αυτόν τον πίνακα-ευρετήριο η φυσική διάταξη του μονοδιάστατου.  Ο μόνος τρόπος να μη χρησιμοποιηθεί η φυσική διάταξη του μονοδιάστατου είναι να ταξινομήσουμε χωρίς εντολή επανάληψης (αλλά με διαδοχικές Αν… τότε αντιμετάθεσε… όσες φορές χρειαστεί. Δηλαδή σαν να μην έχουμε πίνακα αλλά στοιχεία αποθηκευμένα σε μεταβλητές.   

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

Η αυθαιρεσία που γίνεται στις συνήθεις ασκήσεις ταξινόμησης δισδιάστατου είναι ότι χωρίς να διευκρινίζεται τίποτα θεωρούμε αυθαίρετα ότι η διάταξη των κελιών είναι α[1,1], α[1,2], … α[1,ν], α[2,1] … κλπ δηλαδή κατά γραμμή. Στους μονοδιάστατους τουλάχιστο τα κελιά έχουν τη φυσική διάταξη. Στους δισδιάστατους δεν έχουν τίποτα.

Εννοείται πως πέρα από αυτά θα πρέπει να υπάρχει και φυσικό νόημα σε ότι γίνεται, πράγμα που επιμελώς παρέκαμψα παραπάνω. Δίνω 2 παραδείγματα:

Παράδειγμα 1
Αν σε πίνακα 2 διαστάσεων οι γραμμές συμβολίζουν μαθητές και οι στήλες μαθήματα. Τότε δεν μπορεί να γίνει ταξινόμηση σε όλο το δισδιάστατο γιατί κάποιο στοιχείο που αλλάζει γραμμή και στήλη αλλάζει μαθητή και μάθημα και αυτό δεν έχει νόημα. Ούτε ταξινόμηση κάθε γραμμής χωριστά μπορεί να γίνει αφού για τους περισσότερους μαθητές θα χαθεί η αντιστοιχία με τα μαθήματα. Μπορούμε όμως να ταξινομήσουμε αλφαβητικά τα ονόματα αντιμεταθέτοντας ολόκληρες τις γραμμές.

Παράδειγμα 2.
Αν έχουμε σχολική παρέλαση μαθητών βάζουμε τον πιο ψηλό μπρος και αριστερά, τον δεύτερο δίπλα, μετά πας στη δεύτερη γραμμή κλπ Εδώ είναι σα να έχεις μονοδιάστατο αποθηκευμένο σε δισδιάστατο. Δεν έχει κάποια ειδική σημασία η στήλη ή η γραμμή. Μόνο το ύψος μετράει. Έχεις εσωτερική δομή μονοδιάστατου και το φυσικό πρόβλημα σου επιβάλει πίνακα 2 διαστάσεων αφού δε γίνεται οι μαθητές να κάνουν παρέλαση ο ένας πίσω από τον άλλον.

Για μένα τα κρίσιμα σημεία είναι 2:

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

Το δεύτερο είναι ότι η ταξινόμηση είναι μονοδιάστατο πρόβλημα αφού οι αποθηκευτικοί χώροι (και φυσικά και τα στοιχεία προς ταξινόμηση) πρέπει να μπουν σε σειρά.   

Δεν πλατειάζω άλλο για την ώρα. Έχω ετοιμάσει και παράδειγμα ταξινόμησης μονοδιάστατου με ordering function αλλά φυσική διάταξη κελιών, με διάταξη κελιών διαφορετική της φυσικής αλλά ordering function την f(x)=x και τέλος την πιο σύνθετη περίπτωση με  ordering function κάποια τυχαία f(x)και διάταξη κελιών διαφορετική της φυσικής και ορισμένη μέσω του πίνακα διάταξη_κελιών ή κάποια αλγεβρική g(i). Μάλλον σε επόμενο μήνυμα.

[alkisg]

Γιώργο συμφωνώ σε όλα, εκτός από αυτό:

Ο μόνος τρόπος να μη χρησιμοποιηθεί η φυσική διάταξη του μονοδιάστατου είναι να ταξινομήσουμε χωρίς εντολή επανάληψης (αλλά με διαδοχικές Αν… τότε αντιμετάθεσε… όσες φορές χρειαστεί.

Μπορώ κάλλιστα να χρησιμοποιήσω συνάρτηση διάταξης (εννοώ για τη σειρά τοποθέτησης των στοιχείων, όχι τη συνάρτηση ταξινόμησης). Στο παράδειγμα με τα ονόματα και τα τηλέφωνα,
https://alkisg.mysch.gr/steki/index.php?topic=1240.
η συνάρτηση διάταξης είναι 2*i - 1.
(συμφωνώ κι εγώ όμως ότι θα έπρεπε να χρησιμοποιηθεί δισδιάστατος σ' αυτήν την περίπτωση).

Επίσης θα μπορούσα να χρησιμοποιήσω οποιαδήποτε ένα-προς-ένα και επί συνάρτηση από το [1..Ν] στο [1..Ν], όσα δηλαδή είναι τα στοιχεία του πίνακα.

Φυσικά όλα αυτά όταν το υπαγορεύει το πρόβλημα, όχι αυθαίρετα.

Αλλά ακόμα και μονοδιάστατο-ευρετήριο να χρησιμοποιήσουμε, πάλι ένα-προς-ένα και επί συνάρτηση είναι. Ένας σοβαρός λόγος να χρησιμοποιηθεί αυτή η τεχνική είναι αν τα δεδομένα μας είναι πολύ μεγάλα, και δεν θέλουμε να τα κάνουμε συνεχώς swap, οπότε κάνουμε swap τα στοιχεία του ευρετηρίου.
Π.χ. θέλω να ταξινομήσω ένα μονοδιάστατο από εγγραφές, που έχουν πεδία
όνομα
εικόνα 10Mb

Είναι πολύ πιο λογικό να χρησιμοποιηθεί ευρετήριο (εφόσον δεν έχουμε δυναμικές δομές δεδομένων, δηλαδή η εικόνα να είναι pointer).

Anyway, λεπτομέρεια είναι. Go on!

[sstergou]

Αυτό το οποίο κωδικοποίησα είναι ταξινόμηση δισδιάστατου πίνακα; (όχι δισδιάστατη ταξινόμηση)
Αν όχι τι είναι ;
Δεν λέω πως είναι, απλα ρωτάω τη γνώμη σας.

Δείτε λίγο αν έχετε χρόνο, και μην βαρέσετε για τυχόν bugs  , έγινε αρκετά βιαστικά.

Υπάρχει και το αρχείο εισόδου, δεν θα χρειαστεί να γράψετε τίποτε!

http://users.sch.gr/sstergou/sort2d.glo

edit:Περίεργο σε εμένα κατέβαινε.
Έψαξα λίγο δεν μπόρεσα να βρω πως μπαίνει attachment. Τεσπα, τώρα μάλλον διορθώθηκε

[alkisg]

Στάθη δεν κατεβαίνει το αρχείο, πιθανώς επειδή έχει ελληνική επέκταση και οι browsers δεν τα πάνε και πολύ καλά με τα ελληνικά URL.

Δοκίμασε να το ανεβάσεις εδώ σαν συνημμένο, το SMF το στέλνει με διαφορετικό τρόπο (όχι με URL αλλά σαν http attachment) ή άλλαξέ του την επέκταση σε .glo

edit: απλά πατάς το "Πρόσθετες επιλογές" για να επισυνάψεις αρχείο. Σχετικό θέμα.
Στο ανέβασα εγώ, άμα δεν το θες το σβήνεις.

[pgrontas]

Γιώργο τα έγραψες πολύ σωστά με τρόπο που κανείς δεν μπορεί να διαφωνήσει.

Ιδιαίτερη σημασία για μένα έχει το παράδειγμα 1. Αυτό κυρίως είχα στο μυαλό μου όταν έλεγα ότι η ταξινόμηση σε δισδιάστατο δεν έχει νόημα. Και νομίζω ότι πλέον έχουμε συμφωνήσει σε αυτό.

Μπορούμε όμως να ταξινομήσουμε αλφαβητικά τα ονόματα αντιμεταθέτοντας ολόκληρες τις γραμμές.

To παραπάνω όμως δεν είναι ταξινόμηση των στοιχείων του δισδιάστατου, γιατί η συνάρτηση διάταξης ορίζεται σε στοιχεία εξωτερικά του πίνακα (Υποθέτω ότι ο πίνακας περιέχει βαθμούς και τα ονόματα είναι σε εξωτερικό). Είναι απλά αντιμετάθεση τους για να συμβαδίζουν με την σειρά των δεδομένων που ταξινομούνται.

Το παράδειγμα 2 εγώ το βλέπω λίγο διαφορετικά. Βλέπω μόνο την μονοδιάστατη δομή των υψών που συγκρίνονται. Η διάταξη της παρέλασης, δεν είναι αυτοσκοπός, αλλά προκύπτει αν πάρεις τα ταξινομημένα ύψη και τα χωρίσεις σε 5 άδες πχ. (σε ν-αδες). Η διάταξη σε γραμμές και στήλες προκύπτει ως αποτέλεσμα αυτού του χωρισμού (δεν είναι ο πρωταρχικός μας στοχος). Το ίδιο ισχύει και στο παράδειγμα με τα γάλατα που έφερε ο Άλκης το ΣΚ. Νομίζω όμως οι απόψεις μας είναι ισοδύναμες - και παραδέχομαι ότι αυτό μπορεί να θεωρηθεί ταξινόμηση δισδιάστατου αν ορίσεις την διάταξη των θέσεων του δισδιάστατου, όπως πολύ σωστά έγραψες.

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

[gpapargi]

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

Υπάρχουν 2 διαφορετικά πράγματα. Σχηματικά, το ένα είναι η καμπύλη που διατρέχει τα στοιχεία με τη σειρά. Το άλλο είναι το σχήμα που σχηματίζουν οι αποθηκευτικοί χώροι. Μια που είμαστε σε προγραμματιστικά περιβάλλοντα φανταζόμαστε πίνακες που «έχουν σχήμα» ευθύγραμμου τμήματος (μονοδιάστατοι), ορθογωνίου παραλληλογράμμου (δισδιάστατοι), ορθογωνίου παραλληλεπιπέδου (τρισδιάστατοι) και αυτό κάπως περιορίζει τη φαντασία μας σε «τετραγωνισμένα» σχήματα. Μπορούμε να φανταστούμε τους πίνακες να διαλύονται και να απλώνονται τα κελιά τους σε τυχαίες θέσεις. Αυτομάτως γίνεται κατανοητό ότι η ταξινόμηση αφορά τη μονοδιάστατη καμπύλη που διατρέχει τα στοιχεία και όχι το σχήμα που φτιάχνουν οι αποθηκευτικοί χώροι. Ένα παραστατικό παράδειγμα της καμπύλης που σκέφτηκα είναι το ακροβατικό αεροπλάνο που αφήνει καπνό πίσω του. Η καμπύλη που σχηματίζει ο καπνός του είναι μονοδιάστατη, αλλά είναι «embedded» (δε βρήκα καλύτερη λέξη)  μέσα στον τρισδιάστατο χώρο.

Λόγω του ότι είμαστε σε προγραμματιστικό περιβάλλον θα πρέπει να προσγειώσουμε την κουβέντα στους πίνακες με τα «κολλημένα» κελιά τους και τις «ορθές» γωνίες τους. Για μένα λοιπόν για να έχουμε ταξινόμηση σε πίνακα θα πρέπει εκτός από την ordering function (κριτήριο με βάση το οποίο κάνουμε τις συγκρίσεις) να έχουμε και μια διάταξη στα κελιά μας. Σε πίνακα 2 διαστάσεων που θέλουμε να ταξινομήσουμε στη σειρά α[1,1], α[1,2]… α[1,ν], α[2,1] κλπ φαντάζομαι την καμπύλη να ενώνει τα στοιχεία της πρώτης γραμμής και μετά να πηγαίνει από κάτω ενώνοντας το α[1,ν] με το α[2,1]. Εναλλακτικά μπορούμε να φανταστούμε τον πίνακα να αποσυναρμολογείται και να ξανασυναρμολογείται έτσι ώστε η δεύτερη γραμμή να κολλήσει δίπλα στην πρώτη φτιάχνοντας τελικά ένα μονοδιάστατο πίνακα. Δηλαδή από μαθηματική άποψη το θέμα είναι τοπολογικό (τι συνδέεται με τι αδιαφορώντας για ακριβές σχήμα και αποστάσεις στην καμπύλη) και όχι γεωμετρικό (όπου μας νοιάζει το ακριβές σχήμα και οι αποστάσεις)
Σε ταξινόμηση κάθε στήλης χωριστά, έχουμε πολλές διαφορετικές καμπύλες, μια ανά στήλη.

Φυσικά τα παραπάνω αφορούν μόνο τα αφηρημένα μοντέλα. Εννοείται πως η φυσική πραγματικότητα καθορίζει αν κάτι έχει νόημα ή όχι.

Νομίζω πως στην ουσία συμφωνούμε.

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

Φυσικά συμφωνώ στο ότι μια τέτοια συνάρτηση διάταξης κελιών είναι 1 προς 1 και επί από το [1..Ν] στο [1..Ν].  Και μάλιστα είναι ακολουθία (περιορισμός της στο [1..Ν]) αφού παίζουμε με ακεραίους.

[alkisg]

Επομένως συμφωνούμε όλοι ότι εφόσον οριστούν
α) Μια σειρά προσπέλασης των στοιχείων ενός δισδιάστατου πίνακα, και
β) Μια συνάρτηση ταξινόμησης (ordering function) f(A[i,j])
τότε ορίζεται και η ταξινόμηση δισδιάστατου πίνακα;

Πολύ θετικό αυτό, αυτός εξάλλου είναι και ο σκοπός που ξεκίνησε το θέμα.



Γιώργο συνεχίζουμε να διαφωνούμε σχετικά με τη διάταξη κελιών σε μονοδιάστατο, αλλά δεν αξίζει τον κόπο καν να το συζητήσουμε, είναι ...φιλοσοφικό! Εγώ θεωρώ ότι σε ένα ευρετήριο "χρησιμοποιούμε" τη φυσική διάταξη των κελιών του ευρετηρίου όσο και τη φυσική διάταξη των ακεραίων σε ένα μετρητή, δηλαδή χωρίς να είναι μέρος της ταξινόμησης: και ο μετρητής πάει από το 1 ως το Ν, και τα κελιά από το 1 ως το Ν.
Η "καμπύλη" που περνάει από όλα τα στοιχεία που μας ενδιαφέρει είναι αυτή η καμπύλη που περνάει από τον πίνακα των δεδομένων (=ονόματα, εικόνες κτλ), όχι αυτή που περνάει από το ευρετήριο. Αυτή είναι η σειρά της ταξινόμησης. Στο ευρετήριο και ζιγκ-ζαγκ να έκανε η καμπύλη δεν θα μας ενδιέφερε, αρκεί και μόνο στον πίνακα δεδομένων να πέρναγε από τα στοιχεία με τη σωστή σειρά ώστε να είναι ταξινομημένα
(και φυσικά αρκεί να καταφέρναμε και τον μετρητή i να κάνει τα ίδια ζιγκ-ζαγκ)!

[gpapargi]

Σα γρήγορη απάντηση θα έδινα το «Ναι» αλλά καλό είναι να το απαντήσω αναλυτικά γιατί μου φαίνεται ότι η κουβέντα πήρε μεγάλη έκταση κυρίως γιατί δεν είχαμε ξεκαθαρίσει τις έννοιες.

Υπάρχουν 2 πράγματα: ο ένα είναι το φυσικό μοντέλο και το δεύτερο είναι η αφηρημένη δομή δεδομένων του δισδιάστατου πίνακα.
Για το φυσικό μοντέλο τα πάντα εξαρτώνται καθαρά από το φυσικό πρόβλημα. Πχ αν σε πίνακα οι γραμμές συμβολίζουν μαθητές και οι στήλες μαθήματα τότε δεν έχει νόημα να γίνει ταξινόμηση. Η φυσική περιγραφή θα καθορίσει αν κάτι έχει νόημα.

Εγώ θεωρώ ότι η κουβέντα μας αφορά την αφηρημένη δομή δεδομένων του δισδιάστατου πίνακα απαλλαγμένη τελείως από οποιαδήποτε φυσική περιγραφή.
Αν οριστεί:
1) συνάρτηση ταξινόμησης (ordering function) f(A[i,j])
2) συνάρτηση διάταξης κελιών g(i,j) που είναι 1-1 και επί και της δίνεις συντεταγμένες του κελιού στον πίνακα 2 διαστάσεων και σου δίνει τη διάταξη του κελιού

Τότε ΝΑΙ μπορεί να οριστεί η ταξινόμηση πάνω στην ΑΔΔ του δισδιάστατου πίνακα.

Για την υλοποίηση μπορεί να χρησιμοποιηθεί ένας αλγόριθμος ταξινόμησης μονοδιάστατου πίνακα. Για να βρεθεί η θέση του στοιχείου του πίνακα 2 διαστάσεων που θα μπει πχ στον αλγόριθμο φυσαλίδας θα χρειαστεί η αντίστροφη συνάρτηση της g, η g^-1, που της δίνεις αριθμό και σου επιστρέφει το ζεύγος συντεταγμένων του δισδιάστατου πίνακα. (Επειδή είναι 1-1 και επί υπάρχει η g^-1 ).

Για να απαντήσουμε και στην bookitsa… δεν είναι σωστό να λέμε «ταξινομήστε τον δισδιάστατο πίνακα». Θα πρέπει να ορίσουμε σε ποια θέση του δισδιάστατου πίνακα θα μπει το πρώτο στοιχείο, σε ποια το δεύτερο κλπ. Δεν είναι δεδομένο ότι η ταξινόμηση θα γίνει κατά γραμμές. Μπορεί να γίνει κατά στήλες, ή ζιγκ ζαγκ ή σπειροειδώς ή τελείως τυχαία μέσω μιας οποιασδήποτε διάταξης των κελιών του δισδιάστατου. Εννοείται πως το να ταξινομηθεί κάθε στήλη χωριστά σε πίνακα α[ν,μ] δεν είναι μια ταξινόμηση αλλά μ διαφορετικές ταξινομήσεις. Σε ένα πίνακα α[ν,μ] (που έχει δηλαδή ν*μ στοιχεία) υπάρχουν (ν*μ)! (δηλαδή ν επί μ παραγοντικό = 1*2*3*.. * … ν*μ) διαφορετικές διατάξεις κελιών… όσες είναι όλες οι διαφορετικές μεταθέσεις που γίνονται σε ν*μ στοιχεία. Το να κάνουμε ταξινόμηση κατά γραμμή (επειδή έτσι διαβάζει ο άνθρωπος ένα βιβλίο) λύνουμε μια πολύ ειδική και... κυρίως... μια πολύ πολύ βολική περίπτωση του προβλήματος.

Το τελευταίο θέμα που συζητάμε 2 μας Άλκη (η λεπτομέρεια) και σχετίζεται με αυτά είναι το εξής:
Για να ταξινομήσουμε μονοδιάστατο πίνακα πρέπει να ορίσουμε και εκεί διάταξη κελιών; Αυθαιρετούμε αν δεχτούμε τη φυσική σειρά; Όντως είναι λεπτομέρεια… δε μας χαλάσει τη συνταγή στα παραπάνω. Πιστεύω πως δεν αυθαιρετούμε γιατί η διάταξη των κελιών ενός μονοδιάστατου είναι ορισμένη όπως ακριβώς είναι ορισμένη και διάταξη στους ακεραίους. Η φυσική διάταξη είναι συνυφασμένη με τη δομή του μονοδιάστατου. Αδύνατον να γίνει χρήση επαναληπτικής εντολής χωρίς αυτή. Αν το θεωρήσουμε αυθαίρετο, τότε είναι αδύνατο να έχουμε ένα καλώς ορισμένο πρόβλημα σε όλα τα επίπεδα, αφού θα αυθαιρετήσουμε στο ευρετήριο. Για να έχουμε καλώς ορισμένο πρόβλημα θα πρέπει να έχουμε μια άποψη/γνώμη που να μας δίνει τρόπο να ορίσουμε ένα πρόβλημα «καλώς» σε όλα τα επίπεδα. Και στη συνάρτηση διάταξης των κελιών του δισδιάστατου κάναμε χρήση της φυσικής διάταξης του μονοδιάστατου. Ίσως φανεί λίγο περίεργο αυτό που θα πω αλλά θεωρώ πως στον μονοδιάστατο πίνακα το α[1] είναι πριν το α[2], ενώ στο δισδιάστατο το α[1,1] δεν είναι πριν το α[1,2]. Το ίδιο ακριβώς συμβαίνει και στους αριθμούς: Στην ευθεία των πραγματικών το 1 είναι πριν το 2, αλλά στο επίπεδο το (1,0) δεν είναι πριν το (2,0).

Πολύ θετικό αυτό, αυτός εξάλλου είναι και ο σκοπός που ξεκίνησε το θέμα.

Πράγματι... αισθάνομαι και εγώ ότι μετά από πολύ κόπο φτάσαμε σε μια άποψη που εμένα τουλάχιστο με ικανοποιεί.

[pgrontas]

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

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

[gpapargi]

Πάντως αν δούμε εντελώς αφηρημένα τον δισδιάτατο πίνακα, σίγουρα είναι δυνατή η ταξινόμηση του μέσω της συνάρτησης διάταξης των κελιών.

Αυτό συζητάμε. Την ταξινόμηση στην αφηρημένη δομή δεδομένων του δισδιάστατου πίνακα

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

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

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

Είμαι υπέρ του να συνδυάζουμε και τα 2 και κακίζω με κάθε ευκαιρία τους μαθηματικούς στην Ελλάδα που έχουν αποκόψει τα μαθηματικά από τα φυσικά προβλήματα στα οποία αναδεικνύονται.
Προσοχή όμως. Είναι 2 διαφορετικά πράγματα. Και είναι πολύ βολικό να ξέρουμε πιο ακριβώς είναι το αφηρημένο μαθηματικό μοντέλο (εδώ η επεξεργασία της αφηρημένης δομής δεδομένων) που κρύβεται πίσω από το φυσικό μας πρόβλημα. Αυτό μας οδηγεί στο να μπορούμε να λύνουμε μονομιάς πολλά προβλήματα που αν και δείχνουν διαφορετικά (στη φυσική περιγραφή) έχουν ακριβώς το ίδιο αφηρημένο μαθηματικό μοντέλο από πίσω τους.

Πχ ας φανταστούμε ότι σε πίνακα 2 διαστάσεων έχουμε αποθηκευμένους τους βαθμούς μαθητών. Στις γραμμές είναι μαθητές και στις στήλες μαθήματα. Έστω ότι ζητάμε να βρεθεί ο μέσος όρος κάθε μαθητή σε όλα τα μαθήματα.

Ας φανταστούμε τώρα ότι σε πίνακα 2 διαστάσεων έχουμε αποθηκευμένες τις θερμοκρασίες σε διάφορες πόλεις. Στις γραμμές είναι πόλεις και στις στήλες ημέρες του μήνα. Έστω ότι ζητάμε να βρεθεί τη μέση θερμοκρασία κάθε πόλης για όλες τις μέρες του μήνα.

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

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

Στη φυσική αυτό είναι πολύ συχνό φαινόμενο. Βλέπεις 2 τελείως διαφορετικά φαινόμενα που... παραδόξως... περιγράφονται από την ίδια διαφορική εξίσωση (πχ ταλαντώσεις και κυκλώματα RLC αν θυμάμαι καλά). Τρομερά χρήσιμο ως προς τις κρυμμένες ιδιότητες του συστήματος. 

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

[alkisg]

Γιώργο συνέχισα στο παλιό μας θέμα
https://alkisg.mysch.gr/steki/index.php?topic=794.msg8414#msg8414
απλά για το χαβαλέ, αν έχεις όρεξη το συζητάμε εκεί...

Δεν ήθελα να χαλάσουμε το παρόν θέμα, το οποίο έχει πιο άμεση σχέση με το μάθημα.

[pgrontas]

Γιώργο, κανένας δεν είναι ενάντια στην χρήση αφηρημένων μοντέλων.

Το πρόβλημα είναι ότι μπορούν να μας μπερδέψουν κάποιες φορές, αν χάσουμε την επαφή με την πραγματικότητα. Στο παράδειγμα μας, το αφαιρετικό μοντέλο του δισδιάστατου πίνακα ταξινομείται, αλλά δεν συμβαίνει το ίδιο με όλους τους δισδιάστατους πίνακες που μπορεί να συναντήσεις στα διάφορα προβλήματα (πχ. μαθητές -  μαθήματα - βαθμοί).

Στην περίπτωση αυτή μπορεί να θεωρηθεί ότι το μοντέλο παρουσιάζει 'διαρροή' (o όρος είναι δανεισμένος από αυτό το πολύ γλαφυρό άρθρο   http://www.joelonsoftware.com/articles/LeakyAbstractions.html)

Νομίζω ότι μία τέτοια περίπτωση έχουμε και στην περίπτωση της ταξινόμησης των δισδιάστατων. Η λύση είναι,  όπως σωστά είπες, να μπορείς να πηδάς από την μία θεώρηση στην άλλη.