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

[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