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

[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 που παίζαμε μικροί,


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