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

[che]

Καλησπέρα.
Θα ήθελα την γνώμη σας για το παρακάτω θέμα:
Δίνεται πίνακας 4Χ4

  6     7    8    5
100  -1    2    6
  9    90  12   22
  7     8    1    0

Πως μπορεί να ταξινομηθεί με αύξουσα σειρά έτσι ώστε να πάρει την μορφή του παρακάτω:

-1    0    1    2
2    5    6    7
7    8    8    9
12  22  90 100

Αυτό που σκέφτηκα είναι να μεταφέρω τα στοιχεία του μη ταξινομημένου σε έναν μονοδιάστατο πίνακα 16 θέσεων, να εφαρμόσω φυσαλίδα και μετά να αντιγράψω τον ταξινομημένο μονοδιάστατο σε δισδιάστατο 4Χ4. Υπάρχει κάποιος πιο σύντομος τρόπος?

Ευχαριστώ πολύ

[alkisg]

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

Η μετάφραση συντεταγμένων από τον μονοδιάστατο στο διασδιάστατο λοιπόν γίνεται ως εξής:
γραμμή = ι div 4
στήλη = ι mod 4
όπου ι η αντίστοιχη συντεταγμένη του μονοδιάστατου. Ο παραπάνω τύπος όμως θα ίσχυε αν οι συντεταγμένες ξεκινούσαν από 0, στη ΓΛΩΣΣΑ που ξεκινάνε από 1 οι τύποι είναι
γραμμή = (ι-1) div 4 + 1
στήλη = (ι-1) mod 4 + 1

Επομένως γράφεις κανονικά τον αλγόριθμο της φυσαλίδας (με Ν=16) και όπου βλέπεις Α[κάτι] το αντικαθιστάς με Α[γραμμή, στήλη] σύμφωνα με τον παραπάνω τύπο.

[che]

Σ'ευχαριστώ πολύ Άλκη.

[parantop]

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

ΠΡΟΓΡΑΜΜΑ ταξινομηση
ΣΤΑΘΕΡΕΣ
  ν = 2
  μ = 3
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: κ, λ, βημα
  ΠΡΑΓΜΑΤΙΚΕΣ: π[ν,μ], τεμπ
  ΛΟΓΙΚΕΣ: ταξινομημενος
ΑΡΧΗ
  βημα <- 0
  ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ ν
    ΓΙΑ λ ΑΠΟ 1 ΜΕΧΡΙ μ
      ΔΙΑΒΑΣΕ π[κ,λ]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ταξινομημενος <- ΑΛΗΘΗΣ
    ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ ν
      ΓΙΑ λ ΑΠΟ 1 ΜΕΧΡΙ μ
        ΑΝ λ <> μ ΚΑΙ π[κ,λ+1] > π[κ,λ] ΤΟΤΕ
          τεμπ <- π[κ,λ]
          π[κ,λ] <- π[κ,λ+1]
          π[κ,λ+1] <- τεμπ
          ταξινομημενος <- ΨΕΥΔΗΣ
        ΑΛΛΙΩΣ_ΑΝ κ <> ν ΚΑΙ π[κ+1,1] > π[κ,λ] ΤΟΤΕ
          τεμπ <- π[κ,λ]
          π[κ,λ] <- π[κ+1,1]
          π[κ+1,1] <- τεμπ
          ταξινομημενος <- ΨΕΥΔΗΣ
        ΤΕΛΟΣ_ΑΝ
        βημα <- βημα + 1
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΜΕΧΡΙΣ_ΟΤΟΥ ταξινομημενος = ΑΛΗΘΗΣ
 
  ΓΙΑ κ ΑΠΟ 1 ΜΕΧΡΙ ν
    ΓΙΑ λ ΑΠΟ 1 ΜΕΧΡΙ μ
      ΓΡΑΨΕ π[κ,λ]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
 
  ΓΡΑΨΕ "Έκανες ", βημα, " βηματα"

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

[EleniK]

Συνάδελφοι η ταξινόμηση όλου του δισδιάστατου πίνακα είναι μέσα στην ύλη?
Άλλο το σύμφωνα με μια στήλη αντιμεταθέτεις και τις υπόλοιπες (κάτι σαν ταξινόμηση σε παράλληλους)

[andreas_p]

Ελένη, καλημέρα.
Με τη στενή έννοια ΔΕΝ είναι. 
Αλλά δεν αποκλείεται να ζητηθεί ,αρκεί να σου δίνει τους τύπους μετατροπής και να δουλέψεις τη φυσαλίδα αντί για Α[κάτι] με το Α[γραμμή, στήλη]

Ανδρέας

[EleniK]

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

[andreas_p]

Ελένη,  ΔΕΝ υπάρχει.

Ανδρέας

[EleniK]

οκ και ανησύχησα! :-)

[gpapargi]

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

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

Μπορούμε να δούμε συναφή παραδείγματα σε άλλους χώρους. Πχ έστω 2 μιγαδικοί αριθμοί, ο 2+6ι και 3+4ι. Ποιος είναι μεγαλύτερος;

Το ερώτημα δεν έχει νόημα γιατί η διάταξη δεν ορίζεται στους μιγαδικούς.

Άλλο σχετικό θέμα είναι το να δώσεις 2 σημεία σε ένα καρτεσιανό σύστημα συντεταγμένων πχ το Α (2,6) και το Β (3,4) και να ρωτήσεις πιο προηγείται του άλλου.
Ως προς τι όμως; Να συγκρίνεις τεταγμένες, να συγκρίνεις τετμημένες, να συγκρίνεις αποστάσεις από την αρχή των αξόνων. Τι να συγκρίνεις; Δεν είναι καλώς ορισμένα τέτοια ερωτήματα.

Στο ερώτημα της ταξινόμησης 2Δ πινάκων υποσυνείδητα γίνεται μια παραδοχή. Ότι το στοιχείο α[1,2] προηγείται του στοιχείου α[2,1] δηλαδή ότι η διάταξη είναι οριζόντια. Αν δηλώσεις ρητά ότι πρόκειται για παραδοχή (όπως ο ʼλκης παραπάνω) τότε εντάξει. Αλλιώς πρόκειται για αυθαιρεσία. Γιατί να οριστεί η διάταξη κατά γραμμές και όχι κατά στήλες; Γιατί να μην οριστεί σπειροειδώς από έξω προς τα μέσα; (όπως κουλουριάζεται το φίδι). Γιατί να μην οριστεί ως προς την απόσταση από το σημείο α[1,1];

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

Για να φανεί το ότι η ανάγνωση είναι αυτή που μας παρασύρει στην αυθαίρετη διάταξη κατά γραμμές, ας αναλογιστούμε πως θα «ταξινομούσαμε» ένα πίνακα 3 διαστάσεων. Δεν διαβάζουμε στο χώρο και το πράγμα δυσκολεύει. Πως θα «ταξινομούσαμε» ένα πίνακα 4, 5, 6 διαστάσεων; Εδώ δεν έχουμε καν εποπτεία. Η γνωστή εικόνα της ανάγνωσης κατά γραμμές δεν εφαρμόζεται και έτσι η ασάφεια του προβλήματος φαίνεται. Δεν είναι καλώς ορισμένο το πρόβλημα.

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

Ένας τελευταίος προβληματισμός που θέλω να θέσω είναι το ποια η φυσική σημασία μιας ταξινόμησης 2Δ πίνακα. Ας υποθέσουμε ότι στις γραμμές ενός πίνακα 2Δ αντιστοιχούν μαθητές και στις στήλες αντιστοιχούν μαθήματα. Στη θέση β[i,j] βρίσκεται ο βαθμός το i μαθητή στο j μάθημα. Τι φυσικό νόημα έχει να γίνει ταξινόμηση; Ας πούμε ότι θέλουμε να ταξινομήσουμε τις επιδόσεις (βαθμούς) ανεξαρτήτου μαθητή και μαθήματος.
ΑΛΛΑ
Αλλάζοντας θέση στον 2Δ πίνακα δεν μπορείς να αλλάξεις και τους αντίστοιχους μονοδιάστατους που περιέχουν τους μαθητές και τα μαθήματα για να μη χάσεις την πληροφορία. Για ένα πίνακα 2Δ μεγέθους ν επί μ, οι διπλανοί μονοδιάστατοι έχουν ν+μ θέσεις μαζί , ενώ τα κελιά που χρειαζόμαστε για όλη την πληροφορία είναι ν * μ. Για να κάνεις τη δουλειά θέλεις άλλους 2 παράλληλους μονοδιάστατους (που να περιέχουν τη γραμμή και τη στήλη του περιεχομένου στον αρχικό πίνακα) με ν * μ μέγεθος. Το πρόβλημα είναι αδύνατο να λυθεί χωρίς να χαθεί πληροφορία μαθητή/μαθήματος για κάθε βαθμό.

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

ΥΓ
Μόλις αδειάσω λίγο θα γράψω 2 λόγια και για την ταξινόμηση κατά στήλη. 

[alkisg]

Ένα παράδειγμα που "στέκει" λίγο καλύτερα η ταξινόμηση σε δισδιάστατο είναι π.χ. η ταξινόμηση διευθύνσεων IP.
ΑΚΕΡΑΙΕΣ: IPs[100, 4]

Αν θεωρήσουμε ότι μια γραμμή εκφράζει μία ip αλλά χωρίς τις τελείες, π.χ.
Γραμμή 1 => 10.1.130.54 => Α[1,1] = 10, Α[1,2] = 1, Α[1, 3] = 130, Α[1, 4] = 54
Γραμμή 2 => 10.1.129.256 => ...

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

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

Αλλά συμφωνώ με το Γιώργο (και τους υπόλοιπους) ότι τέτοια θέματα είναι παρατραβηγμένα!

[gpapargi]

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

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

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

Αντίθετα, αν και προχωρημένο, μου αρέσει το θέμα της ταξινόμησης με βάση κάποια στήλη. Έχει πολλές εφαρμογές (το κάνει και το Excel) έχει και φυσική σημασία. Είναι ευθεία γενίκευση της ταξινόμησης παραλλήλων πινάκων με βάση κάποιον από αυτούς (υπό την προϋπόθεση ότι όλα τα στοιχεία είναι του ίδιου τύπου). Δίνει και ένα πολύ καλό πλεονέκτημα στη χρήση 2Δ αντί για πολλούς παράλληλους (που είχε συζητηθεί πρόσφατα). Αν έχει πχ 50 παράλληλους πίνακες ακεραίων δεν μπορείς να τους ταξινομήσεις ως προς κάποιον από αυτούς. Με 2Δ γίνεται!

Τώρα στο θέμα της δυσκολίας :- )

Αν και δείχνει δύσκολο πρόγραμμα, δεν είναι και τόσο … αν του «ξηγηθείς» τμηματικό προγραμματισμό.

Ας πούμε πχ ότι θέλουμε να ταξινομήσουμε μόνο τη στήλη 3 αφήνοντας αμετάβλητες τις υπόλοιπες. Χρησιμοποιώ ΓΛΩΣΣΑ λόγω τμηματικού προγραμματισμού.

ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ ν
   ΓΙΑ j ΑΠΟ ν ΜΕΧΡΙ ι ΜΕ ΒΗΜΑ -1
       ΑΝ πίνακας [j,3] < πίνακας[j-1,3] TOTE
           ΚΑΛΕΣΕ Αντιμετάθεσε (πίνακας[j,3],  πίνακας[j-1,3])
        ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


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

Τώρα εύκολα περνάμε σε στην αντιμετάθεση όλης της γραμμής j με τη γραμμή j-1 με μια διαδικασία που κάνει αυτή τη δουλειά κρύβοντας της έξτρα δυσκολία που προσθέτει η νέα επαναληπτική εντολή. Η κλήση θα είναι

ΚΑΛΕΣΕ Αντιμετάθεσε (πίνακας, j, j-1)

αντί για αυτή που έγραψα παραπάνω
Η νέα ενισχυμένη διαδικασία «Αντιμετάθεσε» δέχεται σαν όρισμα τον 2Δ πίνακα καθώς και 2 γραμμές και αντιμεταθέτει τα στοιχεία τους. Χάρη στον τμηματικό προγραμματισμό, ένα δύσκολο πρόβλημα ανάγεται σε 2 ανεξάρτητα που ξέρεις ήδη να λύνεις. 

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

[alkisg]

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

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

Γιώργο διαφωνούμε!
ΟΚ, παράδειγμα που έχει φυσική έννοια και χρειάζεται πλήρη ελευθερία ταξινόμησης σε τρισδιάστατο πίνακα:
Πάλι τελάρα και φορτηγό. Δεν μας ενδιαφέρει τι έχουν τα τελάρα, είναι κλειστά κουτιά. Το φορτηγό χωράει 6x6x6 τελάρα, οπότε θέλουμε τρισδιάστατο πίνακα.
Κάθε τελάρο περιγράφεται από:
1) Έναν σειριακό αριθμό τελάρου,
2) Το βάρος του. Θέλουμε κατά το δυνατόν τα ελαφρύτερα να είναι ψηλά.
3) Το σε ποιον παραλήπτη θα κατέβει (π.χ. μοιράζουμε κούτες τσιγάρα σε διαφορετικά μαγαζιά).

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

Και επειδή στη ΓΛΩΣΣΑ δεν υπάρχουν records, αυτό για να λυθεί χρειάζεται (με έναν από τους πιθανούς τρόπους) 3 παράλληλους τρισδιάστατους πίνακες. 

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

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

[alkisg]

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

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

1	2	3
4	5	6
7	8	9

2η παραλλαγή: Για να μην μπατάρει το φορτηγό προς τα δεξιά, τα βάζουν βουστροφηδόν:

1	2	3
6	5	4
7	8	9

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

4	5	3
6	9	7
2	8	1

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

[gpapargi]

Πολύ καλύτερα Άλκη με αυτά τα δισδιάστατα παραδείγματα γιατί με τα άλλα μπλέκει το πράγμα. Καλύτερα να ασχοληθούμε με το πρώτο που είναι ξεκάθαρο.

(Μικρή παρένθεση που δεν άντεχα να μην την κάνω μια που τα κακά ελαττώματα δεν κόβονται εύκολα   

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

Μας κάνει δηλαδή το μαγικό τετράγωνο 3 Χ 3 που με βάση τον ορισμό του λύνει το πρόβλημα
2 7 6
9 5 1
4 3 8

Τέλος παρένθεσης)


Στο θέμα μας τώρα.
Νομίζω ότι εντόπισα που ακριβώς εστιάζεται η διαφωνία. Είναι στον τρόπο με τον οποίο φανταζόμαστε τον δισδιάστατο πίνακα.

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

Έτσι όπως διατυπώνεις το παράδειγμα, έχεις ένα πρόβλημα με εσωτερική δομή μονοδιάστατου. Έχεις όμως και ένα φυσικό περιορισμό που σε αναγκάζει να το αποθηκεύσεις σε δισδιάστατο. Δηλαδή σαν να λες: «Καλές οι θεωρίες για τις εσωτερικές δομές αλλά στην πράξη έχουμε ένα φορτηγό για το κουβάλημα που καλώς ή κακώς έχει ένα συγκεκριμένο σχήμα.» Το πρόβλημα σε υποχρεώνει να αποθηκεύσεις τα δεδομένα σε πίνακα δισδιάστατο ανεξάρτητα από το τι θα χρησιμοποιούσες για να το λύσεις αν δεν είχες το φυσικό περιορισμό. Σαφώς έχεις αυτό το δικαίωμα. Οι ενστάσεις που ανέφερα ως προς τη φυσική σημασία αφορούν προβλήματα που η εσωτερική δομή τους είναι δισδιάστατη και όχι προβλήματα με εσωτερική δομή μονοδιάστατη που όμως υποχρεωνόμαστε να τα αποθηκεύσουμε σε δισδιάστατο πίνακα. Νομίζω ότι τώρα δε διαφωνούμε.

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

[alkisg]

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

[Πουγαρίδης Απόστολος]

Θα συμφωνήσω απόλυτα με αυτά που γράφει ο Γιώργος χωρίς να προχωρήσω στην δικιά μου θεωρητική ανάλυση για το αν εφαρμόζεται η ταξινόμηση σε δισδιάστατο πίνακα. Πρέπει να καταλάβουμε όλοι οι καθηγητές πληροφορικής, ότι σχολιάζουμε και δίνουμε πιθανές λύσεις σε αλγοριθμικές δομές για τις οποίες δεν υπάρχει τίποτα στο σχολικό. Το τι κάνουν τα φροντιστήρια και ο καθένας είναι δικό του θέμα. Εμείς οφείλουμε να εφαρμόζουμε τη μεθοδολογία του βιβλίου χωρίς να αποπροσανατολίζουμε τα παιδία σε μονοπάτια δικών μας σκέψεων για διάφορα θέματα και ότι άλλο μας κατέβει. Ακόμα και αν έμπαινε ως θέμα θα έπρεπε να δοθούν αντίστοιχες διευκρινήσεις για το πώς,τί και γιατί (ανά στήλη, ανά γραμμή, ανά διαγώνιο, κτλ). ΘΕΤΩ ΤΟ ΕΞΗΣ ΕΡΩΤΗΜΑ ΓΙΑ ΝΑ ΣΚΕΦΤΟΥΜΕ  ΛΟΓΙΚΑ : ΣΕ 2 ΠΙΝΑΚΕΣ, ΕΝΑΝ ΜΟΝΟΔΙΑΣΤΑΤΟ ΜΕ ΟΝΟΜΑΤΑ ΚΑΙ ΕΝΑΝ ΔΙΣΔΙΑΣΤΑΤΟ ΜΕ ΑΠΟΔΟΧΕΣ ΑΝΑ ΜΗΝΑ,ΟΙ ΟΠΟΙΟΙ ΕΙΝΑΙ ΣΥΝΔΕΔΕΜΕΝΟΙ ΠΙΝΑΚΕΣ, ΤΙ ΝΟΗΜΑ ΘΑ ΕΙΧΕ Η ΤΑΞΙΝΟΜΗΣΗ ΣΤΟΝ ΔΙΣΔΙΑΣΤΑΤΟ ΠΙΝΑΚΑ

Πουγαρίδης Απόστολος
Καθηγητής Πληροφορικής ΠΕ19
http://users.sch.gr/pougaridis
www.edutorials.gr

[despoina]

H ταξινόμηση ανά γραμμή ή ανά στήλη σε δισδιάσταο πώς γίνεται; Μπορεί κάποιος να γράψει τους αλγόριθμους;

[petrosp13]

Βλέπεις κάθε γραμμή σαν μονοδιάστατο πίνακα

Για κ από 1 μέχρι Ν ! Για κάθε γραμμή   
    Για ι από 2 μέχρι Μ ! Κλασική ταξινόμηση
         Για j από Μ μέχρι ι με_βήμα -1
               Αν (Α[κ,j-1] < A[κ,j]) τότε
                        Αντιμετάθεσε Α[κ,j-1], A[κ,j]
               Τέλος_Αν
         Τέλος_Επανάληψης
    Τέλος_Επανάληψης
Τέλος_Επανάληψης
     
Για κ από 1 μέχρι Μ ! Για κάθε στήλη
    Για ι από 2 μέχρι Ν ! Κλασική ταξινόμηση
         Για j από Ν μέχρι ι με_βήμα -1
               Αν (Α[j-1,κ] < A[j,κ]) τότε
                        Αντιμετάθεσε Α[j-1,κ] , A[j,κ]
               Τέλος_Αν
         Τέλος_Επανάληψης
    Τέλος_Επανάληψης
Τέλος_Επανάληψης

[despoina]

Ν είναι το πλήθος των γραμμών και Μ το πλήθος των στηλών; Μήπως υπάρχει τρόπος και μη χρήση μονοδιάστατου/των;

[petrosp13]

Ναι, ΝΧΜ

Μπορείς να αντιγράφεις κάθε γραμμή σε μονοδιάστατο και να ταξινομείς εκείνον

Για κ από 1 μέχρι Ν !Για κάθε γραμμή
    Για j από 1 μέχρι Μ
         Β[j] <-- Α[κ,j]
    Τέλος_Επανάληψης
   
    ... !Ταξινόμηση πίνακα Β με Μ στοιχεία
Τέλος_Επανάληψης

[despoina]

Καλύτερος ο πρώτος τρόπος! Ευχαριστώ πάρα πολύ!