Ταξινόμηση Επιλογής (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
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Για την εφαρμογή της 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 Ν
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
    ΓΡΑΨΕ "Α[", Γ, ", ", Σ, "] = ", Α[Γ, Σ] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Συνδυάζοντας τους 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
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Θέμα Β, Ερώτημα 1, 2014, Ημερήσια

Για την ταξινόμηση, σε φθίνουσα σειρά, των στοιχείων ενός μονοδιάστατου πίνακα αριθμών Π[30] μπορεί να ακολουθηθεί η παρακάτω διαδικασία: Αρχικά, ο πίνακας σαρώνεται από την αρχή μέχρι το τέλος του, προκειμένου να βρεθεί το μεγαλύτερο στοιχείο του. Αυτό το στοιχείο τοποθετείται στην αρχή του πίνακα, ανταλλάσσοντας θέσεις με το στοιχείο της πρώτης θέσης του πίνακα. Η σάρωση του πίνακα επαναλαμβάνεται, ξεκινώντας τώρα από το δεύτερο στοιχείο του πίνακα. Το μεγαλύτερο από τα στοιχεία που απέμειναν ανταλλάσσει θέσεις με το στοιχείο της δεύτερης θέσης του πίνακα. Η σάρωση επαναλαμβάνεται, ξεκινώντας από το τρίτο στοιχείο του πίνακα, μετά από το τέταρτο στοιχείο του πίνακα κ.ο.κ.

Το παρακάτω ημιτελές τμήμα αλγορίθμου κωδικοποιεί την παραπάνω διαδικασία:

Για k από 1 μέχρι 29

θ <- .(1.).

Για i από k μέχρι 30

Αν Π[i] … Π[θ] τότε
θ<- .(3..)

Τέλος_αν

Τέλοςεπανάληψης
αντιμετάθεσε .(4.). , .(5..)
Τέλος
επανάληψης
Να γράψετε στο τετράδιό σας τους αριθμούς (1) έως (5), που αντιστοιχούν στα κενά του αλγορίθμου και, δίπλα σε κάθε αριθμό, ό,τι πρέπει να συμπληρωθεί, ώστε να γίνεται σωστά η ταξινόμηση.
Μονάδες 10

Τα θέματα σε pdf, 2014, Μαΐου-Ιουνίου, Ημερήσια