Γενικό Λύκειο > Ταξινόμηση

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

(1/5) > >>

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:
Συνάδελφοι η ταξινόμηση όλου του δισδιάστατου πίνακα είναι μέσα στην ύλη?
Άλλο το σύμφωνα με μια στήλη αντιμεταθέτεις και τις υπόλοιπες (κάτι σαν ταξινόμηση σε παράλληλους)

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση