Αποστολέας Θέμα: Ταξινόμηση με απευθείας Εισαγωγή  (Αναγνώστηκε 5363 φορές)

olga_ath

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 64
Ταξινόμηση με απευθείας Εισαγωγή
« στις: 31 Ιαν 2011, 04:19:15 μμ »
Σε σχέση με την παρακάτω εκφώνηση "Να γίνει αλγόριθμος πoυ να διαβάζει έναν πίνακα 5 ακεραίων και να τοποθετει τα στοιχεία με τέτοιον τρόπο στο πίνακα ωστε ο πίνακας που θα προκείπτει να είναι ταξινομημένος σε αυξουσα σειρά δλδ να μην χρειάζεται ταξινόμηση"

προσπάθησα να τρέξω αυτό αλλα έχει λάθος. Εχεις κπ καμιά καλύτερη ιδέα;:

Αλγόριθμος Ταξινόμηση2
Για ι απο 1 μεχρι 5
   διάβασε τεμπ
   Αν ι>1 τοτε
      Για κ απο 1 μέχρι ι-1
         !αυξουσα ταξινόμηση θέλω
         δεικτης← 1
         σημείο ← 1
         Οσο τεμπ >= Α [κ] και σημείο <= ι επαναλαβε
            δεικτης← δεικτης + 1
            σημείο← σημείο +1
         Τέλος_Επανάληψης
         ! ολα τα στοιχεία μια θέση δεξιά
         Αν δεικτης < ι τότε
            Για λ απο δεικτης μεχρι 4
               Α[λ+1]← Α[λ]
            Τελος_Επαναληψης
         Τελος_αν
            Α[δεικτης] ← τεμπ
         Τέλος_Επαναληψης
   Αλλιώς
      Α[1] ← τεμπ
   Τέλος_αν
Τελος_Επαναληψης
Για ι από 1 μέχρι 5
   Γράψε Α[ι]
Τέλος_Επαναληψης
Τέλος Ταξινόμηση2

Ευχαριστώ!
Doubt everyone and first of all yourself

lykos

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 143
  • Καλύτερα ταξιδάκια, παρά project
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #1 στις: 31 Ιαν 2011, 05:34:49 μμ »
Κώδικας: [Επιλογή]
Διάβασε Π[1]
Για ι από 2 μέχρι 5
  Διάβασε Π[ι]
  Για τ από ι μέχρι 2 με βήμα -1
    Αν Π[τ]<Π[τ-1] τότε
  τεμπ <- Π[τ]
  Π[τ] <- Π[τ-1]
  Π[τ-1] <- τεμπ
Τέλος_Αν
  Τέλος_Επανάληψης
Τέλος_Επανάληψης
Κάτι τέτοιο?

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 801
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #2 στις: 31 Ιαν 2011, 07:57:47 μμ »
Πολύ πιό αποτελεσματικός ο κώδικας του Βασίλη.

Αν θέλεις να αποφύγεις περιττές επαναλήψεις, νομίζω μπορείς να δοκιμάσεις και:
Κώδικας: [Επιλογή]
Διάβασε Π[1]
Για ι από 2 μέχρι 5
  Διάβασε Π[ι]
  τ <- ι
  Οσο τ >= 2 και Π[τ] < Π[τ-1] επανάλαβε
  τεμπ <- Π[τ]
  Π[τ] <- Π[τ-1]
  Π[τ-1] <- τεμπ
  ι <- ι - 1
  Τέλος_Επανάληψης
Τέλος_Επανάληψης
Κάτι τέτοιο?
Στο δικό σου, νομίζω ότι το λάθος είναι πως, εκεί που "προχωράς τα στοιχεία", πάς από τη θέση που θέλεις - προς το τέλος, οπότε χαλάς τα επόμενα..

Αν προσέξεις, στον κώδικα του Βασίλη (lycos) το περπάτημα γίνεται "ανάποδα" οπότε δεν χαλάνε τα στοιχεία..

Θα το κοιτάξω και πιό προσεκτικά το βράδυ
« Τελευταία τροποποίηση: 01 Φεβ 2011, 09:15:01 μμ από Sergio »
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

olga_ath

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 64
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #3 στις: 01 Φεβ 2011, 06:15:59 μμ »
Ευχαριστώ και τους δυο!

Αυτό που ηθελα να κάνω εγώ είναι να βρίσκω τη θέση του πίνακα που πρέπει να εισαχθεί το στοιχείο και μετά να μετακινώ ανάλογα προς τα δεξια τα υπόλοιπα στοιχεία. Θα προσπαθήσω ξανα όταν βρω λιγάκι χρόνο !
Doubt everyone and first of all yourself

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 801
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #4 στις: 01 Φεβ 2011, 08:01:16 μμ »
Όλγα,

σωστά το σκέφτεσαι.. Η σκέψη η δική σου είναι πιό "προσγειωμένη" από του Βασίλη (lycos).  Του Βασίλη όμως, αν και πιό δύσκολη στη "σύλληψη" και κατανόηση, είναι πιό εύκολη στην υλοποίηση.

Τι κάνει ο Βασίλης;  Βάζει το νέο στοιχείο στην επόμενη θέση του πίνακα (θέση i) και στη συνέχεια το "βάζει στη σωστή του θέση" με τον εξής συλλογισμό (εσωτερικός βρόχος με τη βοήθεια του τ): συγκρίνει αυτό που είναι στη θέση τ με το προηγούμενό και αν είναι μικρότερο από το προηγούμενο (δηλαδή όχι στη σωστή σειρά), τα αντιμεταθέτει, μειώνει το τ κατά 1 και ανεβαίνει, συνεχίζοντας τον έλεγχο του "ανεβασμένου" (κατά μία θέση στοιχείου) .. Αν όμως δεν είναι (μικρότερο από το προηγούμενη) σταματάει.. Είναι πλέον στη σωστή θέση !!

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

Δες το..
« Τελευταία τροποποίηση: 01 Φεβ 2011, 09:13:45 μμ από Sergio »
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 801
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #5 στις: 01 Φεβ 2011, 09:49:09 μμ »
Ευχαριστώ και τους δυο!

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

Η σκέψη που περιγράφεις, μπορεί να αποδωθεί νομίζω ως:

Κώδικας: [Επιλογή]
Αλγόριθμος Εισαγωγή_με_Ταξινόμηση
Δεδομένα //Ν//

ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ Ν
  ΔΙΑΒΑΣΕ χ

! εύρεση της σωστής θέσης (θ) του νέου στοιχείου στον πίνακα
  κ <- 1
  βρέθηκε <- ΨΕΥΔΗΣ
  ΟΣΟ κ <= ι-1 ΚΑΙ βρέθηκε = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
    ΑΝ χ < Π[κ] ΤΟΤΕ
      βρέθηκε <- ΑΛΗΘΗΣ
      θ <- κ
    ΑΛΛΙΩΣ
      κ <- κ + 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΝ βρέθηκε = ΨΕΥΔΗΣ ΤΟΤΕ
    Π[ι] <- Χ
  Αλλιώς

! Μετακίνηση των στοιχείων προς τα δεξιά
    ΓΙΑ κ ΑΠΟ ι-1 ΜΕΧΡΙ θ ΜΕ_ΒΗΜΑ -1
      Π[κ+1] <- Π[κ]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! Εισαγωγή του στοιχείου στη σωστή θέση
    Π[θ] <- χ
  Τέλος_αν
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Αποτελέσματα //Π//
Τέλος Εισαγωγή_με_Ταξινόμηση

Δοκίμασέ το, πρέπει να δουλεύει..

Βέβαια ο κώδικας εύρεσης της θέσης μπορεί να γίνει και πιό σφιχτός, όπως:

Κώδικας: [Επιλογή]
! εύρεση της σωστής θέσης (θ) του νέου στοιχείου στον πίνακα
  θ <- 1
  ΟΣΟ θ <= ι-1 ΚΑΙ χ > Π[θ] ΕΠΑΝΑΛΑΒΕ
    θ <- θ + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

όμως δεν είναι τόσο κατανοητός από μαθητές άρα σε πρώτη φάση διδακτικά ακατάλληλος, άσε που έχουμε και πρόβλημα με τη μερική αποτίμηση συνθηκών οπότε προτείνω τον πιό περιγραφικό..
« Τελευταία τροποποίηση: 01 Φεβ 2011, 10:38:08 μμ από Sergio »
Απ τη μια η θητεία μου σε σχολικές αίθουσες: να φλυαρώ - να ελπίζω πως κατι κατάλαβαν - να εξερευνώ - να μαθαίνω. Απ την άλλη, σχεδόν συνομήλικη, η Διδακτική της Πληροφορικής: ερευνά διαδικασίες μάθησης - φλερτάρει με την Ψυχολογία - με καλεί να αφήσω το βλέμμα του Πληροφορικού και να δω με τα μάτια του δασκάλου. Τέκνα των 2, οι απόψεις μου.. (προσαρμοσμένο από τον πρόλογο του βιβλίου "Το μακρόν Φυσική προ του βραχέως διδάσκω" του Ανδρέα Κασσέτα)

olga_ath

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 64
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #6 στις: 02 Φεβ 2011, 10:46:41 πμ »
Πραγματικά πολλά πολλα ευχαριστώ και στους δύο για ένα θέμα που ομολογώ με παίδεψε  σαββατοκυριακο :-)

@sergio ακριβώς αυτό που γράφεις έγινε. Εγκλωβίστηκα στην ιδέα του insertion δλδ Βρίσκω που πρέπει να μπει και μετά πάω και μετακινω όλα τα στοιχεία μια θέση δεξιά. Αυτό όμως στην υλοποίηση αποδείχτηκε αρκετά δυσκολο!!

Και πάλι ευχαριστώ και τους δύο!
Doubt everyone and first of all yourself

Sergio

  • Αστέριος Φανίκος, Καθηγητής Πληροφορικής, fanikosaATschDOTgr
  • Δεινόσαυρος
  • *****
  • Μηνύματα: 801
  • Κάλλιο γνώση, παρά γρόσι.. (ΛΑΪΚΗ ΠΑΡΟΙΜΙΑ)
    • Προσωπική Σελίδα
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #7 στις: 02 Φεβ 2011, 01:29:52 μμ »
Δεν υπάρχει κάποιο πρόβλημα με τη σκέψη σου..

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

Για παράδειγμα, έστω ότι μας απασχολεί η εισαγωγή του Ζ στον παρακάτω πίνακα:
Δ Η Κ Ν Σ _ _ _
Η αναζήτηση της θέσης μας δίνει αποκαλύπτει πως πρέπει να μπει στη θέση 2.  Ξεκινώντας από τον αρχικό πίνακα (εικόνα 1 παρακάτω), γίνονται 4 τραβήγματα (εικόνες 2 - 5) και στο τέλος το στοιχείο μπαίνει στη σωστή θέση (εικόνα 6).  Στις εικόνες, με παχιά γραφή (bold) ο μετακινούμενος, και με πλάγια (italics) οι τακτοποιημένοι:
1. Δ Η Κ Ν Σ _ _ _
2. Δ Η Κ Ν Σ Σ _ _
3. Δ Η Κ Ν Ν Σ _ _
4. Δ Η Κ Κ Ν Σ _ _
5. Δ Η Η Κ Ν Σ _ _
6. Δ Ζ Η Κ Ν Σ _ _

Το ίδιο μπορεί να γίνει ΚΑΙ με «σπρώξιμο», όμως θα πρέπει να χειριστείς τη «ζάρα» που δημιουργείται κατά το σπρώξιμο.. Θέλω να πω, πως μετά από κάθε σπρώξιμο, ΕΝΑ στοιχείο θα είναι "στον αέρα".  Αρχικά στον αέρα είναι το νέο στοιχείο.. Καραδοκεί πάνω από τη θέση του, για να φύγει αυτό που «κάθεται εκεί».. Μόλις σηκωθεί, του παίρνει τη θέση.  Οπότε έχουμε ουσιαστικά «αντιμετάθεση» αυτού που είναι στον αέρα, με αυτό που κάθεται στη θέση του.  Συνεχίζοντας προς τα δεξιά, (ή κάτω.. όπως το βλέπει ο καθένας) μέχρι και την τελευταία θέση, το πράμα πάει έτσι.. Σήκω συ να κάτσω γω :D   Τελευταίο μένει στον αέρα αυτό που ήταν στη θέση (ι-1).  Ε.. αυτό, βρίσκει δίπλα άδεια θέση και «κάθεται».  Πάλι αυτό μπορεί να φανεί στις 6 εικόνες.. Αυτός που είναι "στον αέρα" εποφθαλμιά τη θέση του "από κάτω του" (με παχιά γραφή (bold) οι αντίδικοι, και με πλάγια (italics) οι τακτοποιημένοι):
       Ζ
1. Δ Η Κ Ν Σ _ _ _
          Η
2. Δ Ζ Κ Ν Σ _ _ _
             Κ
3. Δ Ζ Η Ν Σ _ _ _
                Ν
4. Δ Ζ Η Κ Σ _ _ _
                   Σ
5. Δ Ζ Η Κ Ν _ _ _

6. Δ Ζ Η Κ Ν Σ _ _

Μπορείς να το δοκιμάσεις στην τάξη με «μπαμπούσκες» (αυτές τις ρώσσικες ξύλινες κούκλες που μπαίνουν η μία μέσα στην άλλη).  Εγώ έτσι τους το παρουσιάζω. Και μετά τους λέω να κάνουν τον αλγόριθμο, που προκύπτει ως:

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

olga_ath

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 64
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #8 στις: 06 Φεβ 2011, 05:41:14 μμ »
Πολλα πολλα ευχαριστώ που μπήκες στον κόπο (γιατι ξερω πως απαιτει πολύ χρόνο) να μοιραστείς αυτόν τον πολύ όμορφο τροπο  :angel:

Θα τον χρησιμοποιησω και εγώ !!!
Doubt everyone and first of all yourself

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #9 στις: 08 Φεβ 2011, 03:45:38 πμ »
Να προτείνω κι εγώ έναν τρόπο:
ουσιαστικά είναι ο 1ος τρόπος που προτείνει ο Σέργιος, με την τροποποίηση ότι καθώς αναζητάμε τη θέση που θα μπει ο Χ, ταυτόχρονα κάνουμε και το "τράβηγμα" των στοιχείων προς τα κάτω. Τον περιγράφω:

αρχικά ο Χ είναι "υποψήφιος" να μπει στη θέση i (που είναι κενή)
Αν όμως ο Χ είναι μικρότερος από το στοιχείο που βρίσκεται "από πάνω" (το Α[i-1]), τότε αυτό το στοιχείο το "κατεβάζουμε" στη θέση i κι έτσι ο Χ τώρα είναι υποψήφιος για να μπει στη θέση i-1
Ομοίως, εξετάζουμε αν ο Χ είναι μικρότερος από το στοιχείο "από πάνω" (το Α[i-2]) κι αν είναι, αυτό το "κατεβάζουμε" στη θέση i-1 ενώ ο Χ είναι πλέον υποψήφιος για τη θέση i-2
Συνεχίζουμε με τον ίδιο τρόπο μέχρι που να βρούμε μια θέση όπου ο X δεν είναι μεγαλύτερος από την "από πάνω", κι εκεί ακριβώς εκχωρούμε τον Χ
Αυτό βέβαια θα γίνει μέχρι και τη θέση 2 (αφού η θέση 1 δεν έχει "από πάνω")
Αν όμως διαπιστώσουμε ότι ο Χ δεν έχει μπει πουθενά μέχρι και τη θέση 2, τότε δικαιωματικά κερδίζει τη θέση 1 !!!

Κώδικας: [Επιλογή]
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
    ΔΙΑΒΑΣΕ x
    k ← i
    μπήκε ← ΨΕΥΔΗΣ
    ΟΣΟ k > 1 ΚΑΙ ΟΧΙ μπήκε ΕΠΑΝΑΛΑΒΕ
      ΑΝ x < A[k - 1] ΤΟΤΕ
        A[k] ← A[k - 1]
        k ← k - 1
      ΑΛΛΙΩΣ
        A[k] ← x
        μπήκε ← ΑΛΗΘΗΣ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΑΝ ΟΧΙ μπήκε ΤΟΤΕ
      A[k] ← x
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Φιλικά,
Γιώργος Θαλασσινός

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #10 στις: 08 Φεβ 2011, 11:10:19 πμ »
Δεν μπορώ να μην παρατηρήσω ότι αν δεν γινόταν πλήρης αποτίμηση των λογικών εκφράσεων από τη ΓΛΩΣΣΑ, ο αλγόριθμος θα απλουστευόταν υπέροχα στο εξής:

Κώδικας: [Επιλογή]
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
    ΔΙΑΒΑΣΕ x
    k ← i
    ΟΣΟ k > 1 ΚΑΙ x < A[k - 1] ΕΠΑΝΑΛΑΒΕ
      A[k] ← A[k - 1]
      k ← k - 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    A[k] ← x
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

η οποία παρατήρηση με ωθεί να ανοίξω το εξής θέμα:
http://alkisg.mysch.gr/steki/index.php?topic=3679.new#new
Φιλικά,
Γιώργος Θαλασσινός

tom

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 488
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #11 στις: 12 Απρ 2011, 05:56:01 μμ »
Πήγα και εγώ να "τρέξω" τον παρακάτω αλγόριθμο στο "pseudoglossa"  και διαπίστωσα ότι δεν "τρέχει":

Κώδικας: [Επιλογή]
αλγόριθμος inserstionSort
    δεδομένα //a,n//
    για j από 2 μέχρι n
        key← a[j]
        i← j-1
        όσο i>0 και a[i]>key επανάλαβε
            a[i+1]← a[i]
            i← i-1
        τέλος_επανάληψης
        a[i+1]← key
    τέλος_επανάληψης
   αποτελέσματα //a//
τέλος inserstionSort

Στο διερμηνευτή της ΓΛΩΣΣΑΣ "τρέχει" αν επιλέξεις να γίνεται μερική αποτίμηση...
Είναι  παράλογο κάτι που είναι πιο απλό και κατανοητό να μην μπορεί να εκτελεστεί.
Αυτό που πρότεινες με το "μπήκε" είναι σπαζοκεφαλιά. Γιατί να το μπερδέψουμε τόσο?
Θωμάς Σκυλογιάννης

- Ζήσε σα να' ταν να πεθάνεις αύριο. Μάθε σα να' ταν να ζεις για πάντα.
                                                                                     Μαχάτμα Γκάντι

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 539
  • There can be only one...may it be AEPP.
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #12 στις: 23 Απρ 2013, 11:50:28 πμ »
 :'( :'( :'(
Γιατί δεν παίζει;;;!!;; Γιατί;
Κώδικας: [Επιλογή]
Αλγόριθμος Ταξινόμηση_με_Εισαγωγή

Για i από 1 μέχρι 6
  Διάβασε Π[i]
Τέλος_επανάληψης

Για i από 2 μέχρι 6
  τεμπ ← Π[i]
  θεση ← i
  Όσο θεση > 1 και τεμπ < Π[θεση - 1] επανάλαβε
    Π[θεση] ← Π[θεση - 1]
    θεση ← θεση - 1
  Τέλος_επανάληψης
  Π[θεση] ← τεμπ
Τέλος_επανάληψης

Για i από 1 μέχρι 6
  Εμφάνισε Π[i]
Τέλος_επανάληψης

Τέλος Ταξινόμηση_με_Εισαγωγή
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 539
  • There can be only one...may it be AEPP.
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #13 στις: 24 Απρ 2013, 10:30:43 πμ »
Ξετσεκάρισα το "Να γίνεται πλήρης αποτίμηση των λογικών εκφράσεων" στο Διερμηνευτή και στη συνέχεια έτρεξε κανονικά. Μετά απο μια ματιά στο forum παρατήρησα πως μόνο η Γλώσσα λόγω του περιορισμού των τελεστών της "υποχρεώνει" αυτή τη λειτουργία.
Με αυτό σα δεδομένο, τότε πως θα γινόταν η ταξινόμηση με επιλογή στη Γλώσσα; ???
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 539
  • There can be only one...may it be AEPP.
Απ: Ταξινόμηση με απευθείας Εισαγωγή
« Απάντηση #14 στις: 21 Αύγ 2015, 09:08:30 μμ »
Γεια σε όλους.
Κάτι τέτοιο παίζει;
Παράθεση
"Ταξινόµηση παρεµβολής µε φθίνοντα διαστήµατα (Shell sort)"
Η ταξινόµηση shellsort είναι µια απλή επέκταση της ταξινόµησης µε εισαγωγή η οποία κερδίζει σε ταχύτητα επιτρέποντας αντιµεταθέσεις µεταξύ στοιχείων τα οποία µπορεί να βρίσκονται µακριά το ένα από το άλλο. Για την εφαρµογή αυτής της µεθόδου ταξινοµούνται σε ένα πρώτο πέρασµα τα στοιχεία που απέχουν ένα διάστηµα h1 µεταξύ τους. Στη συνέχεια ταξινοµούνται όλα τα στοιχεία αυτά που απέχουν µεταξύ τους διάστηµα h2. Μετά όλα τα στοιχεία που απέχουν µεταξύ τους διάστηµα h3 κ.ο.κ. µέχρι το ht να γίνει ίσο µε 1. Οποιοδήποτε διάστηµα είναι καλό αρκεί το τελευταίο να είναι το h=1. Σύµφωνα µε τον Knuth, καλές ακολουθίες είναι 1,4,13,40,121... ή 1,4,15,31....... Επίσης έχει αποδειχθεί (Knuth) ότι η
ακολουθία διαστηµάτων που είναι δυνάµεις του 2 (1,2,4...) δεν είναι η καλύτερη αλλά δεν είναι και λανθασµένη. Στο παράδειγµα που ακολουθεί
ορίζω h3=4, h2=2, h1=1.

ΠΑΡΑ∆ΕΙΓΜΑ
Εάν έχω ένα πίνακα 8 θέσεων και ορίσω το h1=4 πρώτα θα ταξινοµηθούν τα στοιχεία που απέχουν µεταξύ τους 4 θέσεις. Έπειτα αυτά που απέχουν 2 θέσεις και στο τρίτο πέρασµα αυτά που απέχουν 1 θέση.
Από http://delab.csd.auth.gr/courses/c_ds/ αντιγραφή...

Ειλικρινά δεν έχω ιδέα πως θα μπορούσε να γίνει αυτή η ταξινόμηση.
Θα μπορούσε κανείς να γράψει έναν κώδικα και να εξηγήσει κάτι περισσότερο; :-X
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής