Ταξινόμηση με απευθείας Εισαγωγή

[olga_ath]

Σε σχέση με την παρακάτω εκφώνηση "Να γίνει αλγόριθμος πoυ να διαβάζει έναν πίνακα 5 ακεραίων και να τοποθετει τα στοιχεία με τέτοιον τρόπο στο πίνακα ωστε ο πίνακας που θα προκείπτει να είναι ταξινομημένος σε αυξουσα σειρά δλδ να μην χρειάζεται ταξινόμηση"

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

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

Ευχαριστώ!

[lykos]

Διάβασε Π[1]
Για ι από 2 μέχρι 5
  Διάβασε Π[ι]
  Για τ από ι μέχρι 2 με βήμα -1
    Αν Π[τ]<Π[τ-1] τότε
	  τεμπ <- Π[τ]
	  Π[τ] <- Π[τ-1]
	  Π[τ-1] <- τεμπ
	Τέλος_Αν
  Τέλος_Επανάληψης
Τέλος_Επανάληψης

Κάτι τέτοιο?

[Sergio]

Πολύ πιό αποτελεσματικός ο κώδικας του Βασίλη.

Αν θέλεις να αποφύγεις περιττές επαναλήψεις, νομίζω μπορείς να δοκιμάσεις και:

Διάβασε Π[1]
Για ι από 2 μέχρι 5
  Διάβασε Π[ι]
  τ <- ι
  Οσο τ >= 2 και Π[τ] < Π[τ-1] επανάλαβε
	  τεμπ <- Π[τ]
	  Π[τ] <- Π[τ-1]
	  Π[τ-1] <- τεμπ
	  ι <- ι - 1
  Τέλος_Επανάληψης
Τέλος_Επανάληψης

Κάτι τέτοιο?

Στο δικό σου, νομίζω ότι το λάθος είναι πως, εκεί που "προχωράς τα στοιχεία", πάς από τη θέση που θέλεις - προς το τέλος, οπότε χαλάς τα επόμενα..

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

Θα το κοιτάξω και πιό προσεκτικά το βράδυ

[olga_ath]

Ευχαριστώ και τους δυο!

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

[Sergio]

Όλγα,

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

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

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

Δες το..

[Sergio]

Ευχαριστώ και τους δυο!

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

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

Αλγόριθμος Εισαγωγή_με_Ταξινόμηση
Δεδομένα //Ν//

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

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

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

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

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

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

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

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

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

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

[olga_ath]

Πραγματικά πολλά πολλα ευχαριστώ και στους δύο για ένα θέμα που ομολογώ με παίδεψε  σαββατοκυριακο :-)

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

Και πάλι ευχαριστώ και τους δύο!

[Sergio]

Δεν υπάρχει κάποιο πρόβλημα με τη σκέψη σου..

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

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

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

6. Δ Ζ Η Κ Ν Σ _ _

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

στον_αέρα <- Χ
ΓΙΑ κ ΑΠΟ θ ΜΕΧΡΙ ι-1
   Αντιμετάθεσε Π[κ], στον_αέρα
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Π[ι] < στον_αέρα

[olga_ath]

Πολλα πολλα ευχαριστώ που μπήκες στον κόπο (γιατι ξερω πως απαιτει πολύ χρόνο) να μοιραστείς αυτόν τον πολύ όμορφο τροπο 

Θα τον χρησιμοποιησω και εγώ !!!

[gthal]

Να προτείνω κι εγώ έναν τρόπο:
ουσιαστικά είναι ο 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]

Δεν μπορώ να μην παρατηρήσω ότι αν δεν γινόταν πλήρης αποτίμηση των λογικών εκφράσεων από τη ΓΛΩΣΣΑ, ο αλγόριθμος θα απλουστευόταν υπέροχα στο εξής:

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
    ΔΙΑΒΑΣΕ x
    k ← i
    ΟΣΟ k > 1 ΚΑΙ x < A[k - 1] ΕΠΑΝΑΛΑΒΕ
      A[k] ← A[k - 1] 
      k ← k - 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    A[k] ← x
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

η οποία παρατήρηση με ωθεί να ανοίξω το εξής θέμα:
https://alkisg.mysch.gr/steki/index.php?topic=3679.new#new

[tom]

Πήγα και εγώ να "τρέξω" τον παρακάτω αλγόριθμο στο "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]

 
Γιατί δεν παίζει;;;!!;; Γιατί;

Αλγόριθμος Ταξινόμηση_με_Εισαγωγή

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

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

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

Τέλος Ταξινόμηση_με_Εισαγωγή

[nikolasmer]

Ξετσεκάρισα το "Να γίνεται πλήρης αποτίμηση των λογικών εκφράσεων" στο Διερμηνευτή και στη συνέχεια έτρεξε κανονικά. Μετά απο μια ματιά στο forum παρατήρησα πως μόνο η Γλώσσα λόγω του περιορισμού των τελεστών της "υποχρεώνει" αυτή τη λειτουργία.
Με αυτό σα δεδομένο, τότε πως θα γινόταν η ταξινόμηση με επιλογή στη Γλώσσα;

[nikolasmer]

Γεια σε όλους.
Κάτι τέτοιο παίζει;

"Ταξινόµηση παρεµβολής µε φθίνοντα διαστήµατα (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/ αντιγραφή...

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

[dpa2006]

Γεια σε όλους.
Κάτι τέτοιο παίζει;Από http://delab.csd.auth.gr/courses/c_ds/ αντιγραφή...

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

Σε Διερμηνευτή πάντοτε...;

Στην σελίδα:
http://delab.csd.auth.gr/courses/c_ds/sorting.pdf
υπάρχει σε μορφή ρουτίνας σελ 16
Σε πρόγραμμα Pascal
https://github.com/acmeism/RosettaCodeData/blob/master/Task/Sorting-algorithms-Shell-sort/Pascal/sorting-algorithms-shell-sort.pascal
Όλοι (?) οι αλγόριθμοι ταξινόμησης στο:
http://pascal-programming.info/articles/sorting.php

[nikolasmer]

Σε Διερμηνευτή πάντοτε...;

Στην σελίδα:
http://delab.csd.auth.gr/courses/c_ds/sorting.pdf
υπάρχει σε μορφή ρουτίνας σελ 16
Σε πρόγραμμα Pascal
https://github.com/acmeism/RosettaCodeData/blob/master/Task/Sorting-algorithms-Shell-sort/Pascal/sorting-algorithms-shell-sort.pascal
Όλοι (?) οι αλγόριθμοι ταξινόμησης στο:
http://pascal-programming.info/articles/sorting.php

Παναγία μου!!

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

Αλγόριθμος εισαγωγή
Για ι από 1 μέχρι 10
  Διάβασε Π[ι] 
Τέλος_επανάληψης

Για ι από 2 μέχρι 10
  x ← Π[ι] 
  είναι_οκ ← Ψευδής
  end ← ι - 1
  Όσο end ≥ 1 και είναι_οκ = Ψευδής επανάλαβε
    Αν x < Π[end] τότε
      Π[end + 1] ← Π[end] 
      Π[end] ← x
    αλλιώς
      είναι_οκ ← Αληθής
    Τέλος_αν
    end ← end - 1
  Τέλος_επανάληψης
Τέλος_επανάληψης

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

Τέλος εισαγωγή

Επίσης και για αυτή την τροποποίηση έχω επιφυλάξεις και πολύ τη φοβάμαι: Ταξινόμηση Δυαδικής εισαγωγής (binary
insertion sort)
Σε Pascal είναι η παρακάτω

PROCEDURE BinaryInsertion ;
VAR left,right,mid,i,j:index; x:item ;
BEGIN
FOR i:=2 TO n DO
BEGIN
x:=table[i]; left:=1 ; right:=i-1 ;
WHILE left<=right DO
BEGIN
mid:=(left+right) DIV 2;
IF x.key<table[mid].key THEN right:=mid-1
ELSE left:=mid+1
END;
FOR j:=i-1 DOWNTO left DO table[j+1]:=table[j];
table[left]:=x
END
END;

Μήπως προθυμοποιείται κανείς να τη γράψει σε ψευδογλώσσα και να αναλύσει τα βήματα που ακολουθούμε;
Ευχαριστώ.

[petrosp13]

Θα έχει εξαιρετικό ενδιαφέρον το πώς θα "βγει" η νέα ύλη φέτος στα σχολεία

[bugman]

Δες εδώ τα έχει όλα σε απλή vb6...Και εύκολα γίνονται σε Γλώσσα.

[nikolasmer]

Stable
A stable sorting algorithm is one that maintains relative order for duplicate keys. (This is only relevant for two-dimensional arrays.) As a conceptual example, let's say you were sorting the 365 days of the year by day-of month. In a stable algorithm, the first 12 elements in order will be: January 1, February 1, March 1, April 1, etc... An unstable algorithm will produce unpredictable results for identical keys, so the first twelve elements in order might be: October 1, March 1, June 1, etc...

Εδώ περιγράφει το ότι μια ταξινόμηση είναι "Σταθερή", αλλά δεν μπορώ να καταλάβω πως το εννοεί...

[bugman]

Η εξήγηση είναι απλή,ο αλγόριθμος όποιας ταξινόμησης κινείται βάσει συνθηκών και ανάλογα εκτελούνται αντιγραφές. Μάλιστα υπάρχουν περιπτώσεις που γίνονται οι λεγόμενες τζούφιες αλλαγές, δηλαδή αλλαγές που ουσιαστικά δεν έχουν νόημα. Τέτοιες περιπτώσεις δημιουργόνται όταν υπάρχουν ισότητες. Εδώ γράφει ξεκάθαρα στη περίπτωση που ο αλγόριθμος δουλεύει σε δύο διαστάσεων πίνακα και είναι ήδη ταξινομημένος τότε μια νέα ταξινόμηση θα δημιουργήσει ανακάτεμα. Σε έναν σταθερό αλγόριθμο αυτό δεν θα γίνει παρόλο που ΔΕΝ ελέγχει τη δεύτερη στήλη του πίνακα, δεν έχει δηλαδή δεύτερο κλειδί ταξινόμησης. Ουσιαστικά αυτό που μας ενδιαφέρει σε έναν αλγόριθμο είναι αν ανακατεύει στοιχεία με ίδιο κλειδί...Στο παράδειγμα όλοι οι μήνες έχουν το κλειδί 1. Το όνομα του μήνα είναι η δεύτερη στήλη. Αν ετοιμάζουμε προ ταξινομημένα το πίναακα...και προβούμε σε ταξινόμηση θα πάρουμε τη λίστα όπως ήταν ή όχι...Αν όχι ως ταξινόμηση θα είναι σωστή, 12 άσσοι στην αρχή όπως ήταν αλλά οι μήνες θα είναι σε άλλη σειρά...

[ether]

Εδώ περιγράφει το ότι μια ταξινόμηση είναι "Σταθερή", αλλά δεν μπορώ να καταλάβω πως το εννοεί...

Τρέξε το συνημμένο και δες τι συμβαίνει στα ονόματα με συγκεκριμένες υλοποιήσεις stable και unstable αλγορίθμων

[nikolasmer]

ether πάρα πολύ ωραίο.

Δηλαδή στην ταξινόμηση Φυσαλίδας όπως τα εισάγουμε τα στοιχεία, αν έχουμε ίδιες τιμές τότε ταξινομούνται με τον τρόπο που τα εισάγαμε - stable.
Ενώ στην Ταξινόμηση με Επιλογή επειδή τα ελέγχει όλα τα προηγούμενα στοιχεία, βάζει πρώτο, από τα ίδια, αυτό που βρίσκεται πλησιέστερα και επειδή στη συνέχεια αντιμετατίθενται τα στοιχεία αλλάζει το θέμα πάλι και γίνεται μακελειό-unstable! ...Αν κατάλαβα καλά.

Φυσικά δεν μπορώ να σκεφτώ κάποια χρησιμότητα του stable και του unstable στο μάθημα.
Εκτός...:

Σε έναν πρωτότυπο σχολικό διαγωνισμό οι μαθητές δίνουν ηλεκτρονικές εξετάσεις με Η/Υ στην ΑΕΠΠ. Τα άτομα που πέτυχαν τους 5 μεγαλύτερους διαφορετικούς βαθμούς θα εκπροσωπήσουν το σχολείο τους σε 5 διαφορετικούς πανελλαδικούς διαγωνισμούς Πληροφορικής, τον TURING1 όπου και θα πάρει μέρος ο μαθητής με τον μεγαλύτερο βαθμό, τον TURING2, όπου και θα πάρει μέρος ο μαθητής με τον αμέσως μικρότερο βαθμό και λοιπά, μέχρι τον TURING5 διαγωνισμό.
Όταν ένας μαθητής ολοκληρώσει την εξέτασή του, ο βαθμός του περνιέται ηλεκτρονικά σε έναν πίνακα με βαθμούς και το όνομά του σε έναν αντίστοιχο πίνακα με ονόματα. Αν υπάρχουν ισοβαθμίες τότε προηγείται ο μαθητής που τελείωσε πιο γρήγορα την εξέτασή του.
Να γίνει πρόγραμμα το οποίο θα εισάγει βαθμούς και ονόματα σε μονοδιάστατους παράλληλους πίνακες. Στη συνέχεια να ταξινομεί και να εμφανίζει τα ονόματα που θα εκπροσωπήσουν το σχολείο στους αντίστοιχους πανελλαδικούς διαγωνισμούς, σε φθίνουσα σειρά ταξινομημένα ως προς το βαθμό.

[ether]

ether πάρα πολύ ωραίο.

Δηλαδή στην ταξινόμηση Φυσαλίδας όπως τα εισάγουμε τα στοιχεία, αν έχουμε ίδιες τιμές τότε ταξινομούνται με τον τρόπο που τα εισάγαμε - stable.
Ενώ στην Ταξινόμηση με Επιλογή επειδή τα ελέγχει όλα τα προηγούμενα στοιχεία, βάζει πρώτο, από τα ίδια, αυτό που βρίσκεται πλησιέστερα και επειδή στη συνέχεια αντιμετατίθενται τα στοιχεία αλλάζει το θέμα πάλι και γίνεται μακελειό-unstable! ...Αν κατάλαβα καλά.

Φυσικά δεν μπορώ να σκεφτώ κάποια χρησιμότητα του stable και του unstable στο μάθημα.
Εκτός...:

Σε έναν πρωτότυπο σχολικό διαγωνισμό οι μαθητές δίνουν ηλεκτρονικές εξετάσεις με Η/Υ στην ΑΕΠΠ. Τα άτομα που πέτυχαν τους 5 μεγαλύτερους διαφορετικούς βαθμούς θα εκπροσωπήσουν το σχολείο τους σε 5 διαφορετικούς πανελλαδικούς διαγωνισμούς Πληροφορικής, τον TURING1 όπου και θα πάρει μέρος ο μαθητής με τον μεγαλύτερο βαθμό, τον TURING2, όπου και θα πάρει μέρος ο μαθητής με τον αμέσως μικρότερο βαθμό και λοιπά, μέχρι τον TURING5 διαγωνισμό.
Όταν ένας μαθητής ολοκληρώσει την εξέτασή του, ο βαθμός του περνιέται ηλεκτρονικά σε έναν πίνακα με βαθμούς και το όνομά του σε έναν αντίστοιχο πίνακα με ονόματα. Αν υπάρχουν ισοβαθμίες τότε προηγείται ο μαθητής που τελείωσε πιο γρήγορα την εξέτασή του.
Να γίνει πρόγραμμα το οποίο θα εισάγει βαθμούς και ονόματα σε μονοδιάστατους παράλληλους πίνακες. Στη συνέχεια να ταξινομεί και να εμφανίζει τα ονόματα που θα εκπροσωπήσουν το σχολείο στους αντίστοιχους πανελλαδικούς διαγωνισμούς, σε φθίνουσα σειρά ταξινομημένα ως προς το βαθμό.

Μια μέθοδος ταξινόμησης χαρακτηρίζεται ως stable όταν διατηρεί την αρχική σχετική διάταξη των εγγραφών με ίσα κλειδιά.

Η υλοποίηση της φυσαλίδας όπως είναι στο παράδειγμα που ανέφερα (και στο βιβλίο) είναι stable.

Η υλοποίηση της επιλογής όπως είναι στο παράδειγμα που ανέφερα δεν είναι stable.
Επειδή στην επιλογή μπορεί να συμβούν αυτές οι ανταλλαγές τιμών απομακρυσμένων (μη γειτονικών) στοιχείων, είναι πιθανόν να αλλάξει η αρχική σχετική διάταξη των εγγραφών με ίσα κλειδιά.
Έστω π.χ. ότι έχω να ταξινομήσω τις εγγραφές (10, Ελένη), (10, Χριστίνα), (15, Μαρία)  σε φθίνουσα με κλειδί το πρώτο πεδίο της εγγραφής. Στην πρώτη επανάληψη της επιλογής, θα γίνει αντιμετάθεση των (10, Ελένη), (15, Μαρία), οπότε το (10, Ελένη) θα βρεθεί μετά το (10, Χριστίνα).

[nikolasmer]

Βλέποντας κάποια site με βιβλία στο internet παρατήρησα πως υπάρχει ειδική μνεία στα best sellers. Η βάση προφανώς ενημερώνεται κάθε φορά που ένα βιβλίο αγοράζεται και έτσι υπάρχουν αλλαγές στη λίστα με τα best sellers τους. Αν είχαμε Ταξινομημένα τα βιβλία ενός καταστήματος με φθίνουσα σειρά με βάση τις πωλήσεις τους, κάθε φορά που γινόταν αλλαγή έπρεπε να τα ταξινομήσουμε εκ νέου; Αν ναι, ποιος από τους 3 εντός ύλης αλγόριθμους ταξινόμησης συμφέρει για αυτή τη λειτουργία; Αν δεν συμφέρει κανένας τους, γνωρίζουμε τον αλγόριθμο ταξινόμησης που χρησιμοποιούν; Αν δεν ισχύει και αυτό έχω λάθος στο συλλογισμό μου και δεν γίνεται ταξινόμηση καθόλου;!

[bugman]

Νομίζω ότι η άποψη του συμφέροντος αλγόριθμου...θα πρέπει να περιλαμβάνει ένα βασικό δεδομένο..."πόσα ταξινομούμε"; Αν δηλαδή ταξινομούμε μεγάλο αριθμό στοιχείων με διαφορετικά κλειδιά..τότε δεν υπάρχει άλλη καλύτερη από την quicksort. Γενικά όμως δεν έχει νόημα να πάει κανείς αλλού εκτός και αν έχουμε μια ταξινόμηση πέντε δέκα στοιχείων...

Αν σε ενδιαφέρουν οι αλγόριθμοι ρίξε μια ματιά εδώ όπου το ζήτημα δεν είναι το πώς κάνεις κάτι αλλά πόσο γρήγορα. Εγώ κατάφερα σε 1.3 δευτερόλεπτα 792367 λέξεις από τη βίβλο (στα αγγλικά), να βρω τις μοναδικές 13231 και να τις έχω ταξινομήσει. Διάβασε!

[nikolasmer]

Αν σε ενδιαφέρουν οι αλγόριθμοι ρίξε μια ματιά εδώ όπου το ζήτημα δεν είναι το πώς κάνεις κάτι αλλά πόσο γρήγορα. Εγώ κατάφερα σε 1.3 δευτερόλεπτα 792367 λέξεις από τη βίβλο (στα αγγλικά), να βρω τις μοναδικές 13231 και να τις έχω ταξινομήσει. Διάβασε!

Ευχαριστώ και πάλι για την απάντηση φίλε bugman. Το κοιτάω τώρα!!

[dpa2006]

Ευχαριστώ και πάλι για την απάντηση φίλε bugman. Το κοιτάω τώρα!!

Σταθετότητα Αλγορίθμων -αν και έχει απαντηθεί ήδη το αναφέρω χάριν πληρότητας.
Μια σχετική συζήτηση εδώ:
What does it mean for a sorting algorithm to be "stable"?

http://www.sorting-algorithms.com/
Σε animation

Sorting and Searching Algorithms (και σε VB)
Sorting Algorithms