Ταξινόμηση Επιλογής (selection sort)

ΤΑΞΙΝΟΜΗΣΗ

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

ΠΡΟΓΡΑΜΜΑ SELECTION_SORT_MONODIASTATOS
ΣΤΑΘΕΡΕΣ
  Μ = 3
  Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α[Μ*Ν], Κ, Θ, Ι
ΑΡΧΗ
  Α[1] <- 10
  Α[2] <- 7
  Α[3] <- 1
  Α[4] <- 9
  Α[5] <- 2
  Α[6] <- 4
  Α[7] <- 5
  Α[8] <- 8
  Α[9] <- 3

  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ*Ν
    ΓΡΑΨΕ Α[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ (Μ*Ν) - 1
    Θ <- Κ
    ΓΙΑ Ι ΑΠΟ Κ + 1 ΜΕΧΡΙ Μ*Ν
      ΑΝ Α[Ι] < Α[Θ] ΤΟΤΕ
        Θ <- Ι
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ΚΑΛΕΣΕ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α[Κ], Α[Θ]) 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ '***'
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ*Ν
    ΓΡΑΨΕ Α[Ι] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

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

ΔΙΑΔΙΚΑΣΙΑ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α, Β) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α, Β, TEMP
ΑΡΧΗ
  TEMP <- Α
  Α <- Β
  Β <- TEMP
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ</code class="language-javascript">

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

ΠΡΟΓΡΑΜΜΑ ΣΥΝΤΕΤΑΓΜΕΝΕΣ
ΣΤΑΘΕΡΕΣ
  Μ = 3
  Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α[Μ, Ν], Λ, Γ, Σ
ΑΡΧΗ
  Α[1, 1] <- 10
  Α[1, 2] <- 7
  Α[1, 3] <- 1
  Α[2, 1] <- 9
  Α[2, 2] <- 2
  Α[2, 3] <- 4
  Α[3, 1] <- 5
  Α[3, 2] <- 8
  Α[3, 3] <- 3
  ΓΙΑ Λ ΑΠΟ 1 ΜΕΧΡΙ Μ*Ν
    ΓΡΑΨΕ Λ
    ΑΝ Λ mod Ν = 0 ΤΟΤΕ
      ΑΝ Λ div Ν = 0 ΤΟΤΕ
        Γ <- 1
        Σ <- Ν
      ΑΛΛΙΩΣ
        Γ <- Λ div Ν
        Σ <- Ν
      ΤΕΛΟΣ_ΑΝ
    ΑΛΛΙΩΣ
      ΑΝ Λ div Ν = 0 ΤΟΤΕ
        Γ <- 1
        Σ <- Λ mod Ν
      ΑΛΛΙΩΣ
        Γ <- 1 + Λ div Ν
        Σ <- Λ mod Ν
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
    ΓΡΑΨΕ "Α[", Γ, ", ", Σ, "] = ", Α[Γ, Σ] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ</code class="language-javascript">

Συνδυάζοντας τους 2 αλγορίθμους, προκύπτει η selection sort για διδιάστατο πίνακα.

ΠΡΟΓΡΑΜΜΑ SELECTION_SORT_2ΔΙΑΣΤΑΤΟΣ
ΣΤΑΘΕΡΕΣ
  Μ = 3
  Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α[Μ, Ν], Κ, Θ, Ι, J, Γ1, Σ1, Γ2, Σ2
ΑΡΧΗ
  Α[1, 1] <- 10
  Α[1, 2] <- 7
  Α[1, 3] <- 1
  Α[2, 1] <- 9
  Α[2, 2] <- 2
  Α[2, 3] <- 4
  Α[3, 1] <- 5
  Α[3, 2] <- 8
  Α[3, 3] <- 3

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

  ΓΙΑ Κ ΑΠΟ 1 ΜΕΧΡΙ (Μ*Ν) - 1
    Θ <- Κ
    ΓΙΑ Ι ΑΠΟ Κ + 1 ΜΕΧΡΙ Μ*Ν
      ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Ι, Γ2, Σ2) 
      ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Θ, Γ1, Σ1) 
      ΑΝ Α[Γ2, Σ2] > Α[Γ1, Σ1] ΤΟΤΕ
        Θ <- Ι
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Κ, Γ1, Σ1) 
    ΚΑΛΕΣΕ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Θ, Γ2, Σ2) 
    ΚΑΛΕΣΕ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α[Γ1, Σ1], Α[Γ2, Σ2]) 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ '***'
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Μ
    ΓΙΑ J ΑΠΟ 1 ΜΕΧΡΙ Ν
      ΓΡΑΨΕ Α[Ι, J] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΔΙΑΔΙΚΑΣΙΑ ΣΥΝΤΕΤΑΓΜΕΝΕΣ(Λ, Γ, Σ) 
ΣΤΑΘΕΡΕΣ
  Μ = 3
  Ν = 3
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Λ, Γ, Σ
ΑΡΧΗ
  ΑΝ Λ mod Ν = 0 ΤΟΤΕ
    ΑΝ Λ div Ν = 0 ΤΟΤΕ
      Γ <- 1
      Σ <- Ν
    ΑΛΛΙΩΣ
      Γ <- Λ div Ν
      Σ <- Ν
    ΤΕΛΟΣ_ΑΝ
  ΑΛΛΙΩΣ
    ΑΝ Λ div Ν = 0 ΤΟΤΕ
      Γ <- 1
      Σ <- Λ mod Ν
    ΑΛΛΙΩΣ
      Γ <- 1 + Λ div Ν
      Σ <- Λ mod Ν
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

ΔΙΑΔΙΚΑΣΙΑ ΑΝΤΙΜΕΤΑΘΕΣΗ(Α, Β) 
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Α, Β, TEMP
ΑΡΧΗ
  TEMP <- Α
  Α <- Β
  Β <- TEMP
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ</code class="language-javascript">