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

Ας υποθέσουμε ότι μας δίνεται ένας πίνακας δύο διαστάσεων 3 γραμμών και 4 στηλών όπως ο επόμενος:

56817
-722153
181219

Ζητούμενο είναι η δημιουργία αλγορίθμου που θα ταξινομεί τα στοιχεία του, σε αύξουσα σειρά ώστε το μικρότερο να βρίσκεται στην θέση 1,1 και το μεγαλύτερο στην θέση 3,4. Δηλαδή τα στοιχεία να διατάσσονται γραμμή-προς-γραμμή από το μικρότερο στο μεγαλύτερο. Ο επόμενος πίνακας δείχνει την διάταξη των στοιχείων.
-7135
68915
17182122

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

Αλγόριθμος ταξινόμηση_διδιάστατου
   Δεδομένα // Α //
   ! αντιγραφή των στοιχείων σε πίνακα μιας διάστασης (Β)
   k <- 1
   Για i από 1 μέχρι 3
      Για j από 1 μέχρι 4
         B[k] <- A[i,j]
         k <- k + 1
      Τέλος_επανάληψης
   Τέλος_επανάληψης
 
   ! ταξινόμηση του Β
   Για i από 2 μέχρι 12
      Για j από 12 μέχρι i με_βήμα -1
         Αν B[j] < B[j-1] τότε
            αντιμετάθεσε B[j], B[j-1]
         Τέλος_αν
      Τέλος_επανάληψης
   Τέλος_επανάληψης
 
   ! επανατοποθέτηση των στοιχείων στον πίνακα A
   k <- 1
   Για i από 1 μέχρι 3
      Για j από 1 μέχρι 4
         A[i,j] <- B[k]
         k <- k + 1
      Τέλος_επανάληψης
   Τέλος_επανάληψης
 
Τέλος ταξινόμηση_διδιάστατου

2ος τρόπος
Εφαρμογή του αλγορίθμου ταξινόμησης για μονοδιάστατου πίνακα και απ’ ευθείας «μετάφραση» του εκάστοτε στοιχείου στις 2 διαστάσεις, έχοντας υπόψη την εξής παρατήρηση:
1ο στοιχείο = 1η γραμμή, 1η στήλη
2ο στοιχείο = 1η γραμμή, 2η στήλη
3ο στοιχείο = 1η γραμμή, 3η στήλη
4ο στοιχείο = 1η γραμμή, 4η στήλη
5ο στοιχείο = 2η γραμμή, 1η στήλη
……………………………………….
j στοιχείο = (j – 1) div 4 + 1 γραμμή, (j – 1) mod 4 + 1 στήλη

Αλγόριθμος ταξινόμηση_διδιάστατου
   Δεδομένα // Α //
   Για i από 2 μέχρι 12
      Για j από 12 μέχρι i με_βήμα -1
         ! πρέπει να βρούμε την γραμμή και την στήλη του j και j-1 στοιχείου
         γ1 <- (j - 1) div 4 + 1
         σ1 <- (j - 1) mod 4 + 1
         γ2 <- ((j - 1) - 1) div 4 + 1
         σ2 <- ((j - 1) - 1) mod 4 + 1
 
         Αν A[γ1, σ1] < A[γ2, σ2] τότε
            αντιμετάθεσε Α[γ1, σ1], Α[γ2, σ2]
         Τέλος_αν
      Τέλος_επανάληψης
   Τέλος_επανάληψης
Τέλος ταξινόμηση_διδιάστατου

7 σχόλια για το άρθρο “Ταξινόμηση δισδιάστατου πίνακα

  • 04/02/2012 at 04:22
    Permalink

    Θα μπορούσε να γίνει και με 4 συνεχόμενες Για δηλαδή:

    Για i από 1 μέχρι Ν-1
    Για j από 1 μέχρι Ν
    Για k από 1 μέχρι Ν-1
    Για m από 1 μέχρι Ν
    αν α[i,j]<a[k,m] τότε
    y<– α[i,j]
    α[i,j]<–α[k,m]
    α[k,m]<–y
    τελος_επανάληψης
    τέλος_επανάληψης
    τέλος_επανάληψης
    τέλος_επανάληψης

  • 04/02/2012 at 04:51
    Permalink

    Διόρθωση

    Για i από 1 μέχρι Ν
    Για j από 1 μέχρι Δ
    Για k από 1 μέχρι Ν
    Για m από 1 μέχρι Δ
    αν α[i,j]<a[k,m] τότε
    y<– α[i,j]
    α[i,j]<–α[k,m]
    α[k,m]<–y
    τελος_αν
    τελος_επανάληψης
    τέλος_επανάληψης
    τέλος_επανάληψης
    τέλος_επανάληψης

  • 04/02/2012 at 11:52
    Permalink

    @ΔΑΜΙΑΝΟΣ
    Ναι, αν και μου ήταν λίγο δύσκολο να καταλάβω το σκεπτικό, νομίζω ότι είναι σωστό.
    Το μόνο του μειονέκτημα κατ’εμέ είναι ότι χρησιμοποιεί μεγάλο αριθμό επαναλήψεων!

  • 28/11/2012 at 03:20
    Permalink

    στην ουσια για την ταξινομηση ενος δισδιαστατου πινακα «κοιταμε» τον πινακα σαν μονοδιαστατο .
    Περνουμε τα στοιχεια με την σειρα τα βαζουμε σε ενα μονοδιαστατο τα ταξινομουμε και επειτα τα ξαναβαζουμε στον δισδιαστατο με την σειρα. Σωστα?

  • 29/11/2012 at 10:03
    Permalink

    Σωστά!
    Το θέμα είναι πως σου ζητάνε να τον ταξινομήσεις. Αν πρέπει να τον ταξινομήσεις κατά γραμμές πρέπει ο μονοδιάστατος πίνακας να έχει τα στοιχεία του διδιάστατου κατά γραμμές. Ομοίως για τις στήλες!

  • 22/02/2013 at 21:00
    Permalink

    ΠΡΟΓΡΑΜΜΑ bubbleshort_σε_δισδιαστατο_πινακα
    ΜΕΤΑΒΛΗΤΕΣ
    ΑΚΕΡΑΙΕΣ: i, j, k, pin[10, 10], temp
    ΑΡΧΗ
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 10
    ΔΙΑΒΑΣΕ pin[i, j]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ΓΙΑ k ΑΠΟ 2 ΜΕΧΡΙ 10
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΙΑ j ΑΠΟ 10 ΜΕΧΡΙ k ΜΕ_ΒΗΜΑ -1
    ΑΝ pin[i, j] > pin[i, j – 1] ΤΟΤΕ
    temp <- pin[i, j]
    pin[i, j] <- pin[i, j – 1]
    pin[i, j – 1] <- temp
    ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΡΑΨΕ pin[i, j]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

  • 21/04/2013 at 12:44
    Permalink

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

    17 8 6 5
    22 15 3 -7
    21 18 9 1

Αφήστε μια απάντηση

Η ηλ. διεύθυνσή σας δεν δημοσιεύεται. Τα υποχρεωτικά πεδία σημειώνονται με *