ταξινομήσεις

Ξεκίνησε από epsilonXi, 12 Μαΐου 2019, 05:49:45 ΜΜ

« προηγούμενο - επόμενο »

epsilonXi

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

Η ταξινόμηση με επιλογή θα ταίριαζε κατά τη γνώμη μου καλύτερα από διδακτικής απόψεως, γιατί μπορεί ο καθηγητής να την παρουσιάσει σαν μια επέκταση/γενίκευση της μεθοδολογίας εντοπισμού μεγίστου/ελαχίστου, που σίγουρα θα την είχε διδάξει νωρίτερα από την ταξινόμηση... και σκεφτόμουν ότι μάλλον προτιμήθηκε η φυσαλίδα επειδή απλά η λογική της συμπυκνώνεται σε 4 γραμμές κώδικα και είναι ο συντομότερος στο γράψιμο αλγόριθμος...

Ώσπου πρόσφατα διάβασα εδώ μέσα έναν συνάδελφο -συγχωρέστε με, δε θυμάμαι ούτε ποιός ούτε σε ποιο thread- να λέει ότι επικράτησε η φυσαλίδα διότι μπορούσε να βελτιωθεί, ώστε να πάρουμε την έκδοση της «έξυπνης φυσαλίδας» που κατά μέσο όρο θα είναι αποδοτικότερη, ενώ δε γινόταν κάτι αντίστοιχο με μια «έξυπνη selection sort»... οπότε σκέφτηκα από μέσα μου, «οκ, αφού είναι έτσι, τότε καλά κάνανε, δεν το κάνανε για να διευκολύνουνε την παπαγαλία»...

...
και φτάνουμε στο χθεσινό βράδι που μου περνά η ακόλουθη σκέψη... αν πάρω την παραδοσιακή μορφή:

Κώδικας: bash
για χ από 1 μέχρι Ν-1
    θέση <-- χ
    για ψ από χ+1 μέχρι Ν
      αν Α[ψ] < Α[θέση] τότε
         θέση <-- ψ
      τέλος_αν
    τέλος_επανάληψης
    αντιμετάθεσε Α[χ],Α[θέση]
τέλος_επανάληψης


και στη θέση του εμφωλευμένου loop που ψάχνει για το minimum, ψάχνω για minimum με την αντίστροφη σειρά, πάλι ταξινόμηση με επιλογή δε θα το λέγαμε; (αν και το πώς θα το λέγαμε δεν έχει σημασία)

Κώδικας: bash
για χ από 1 μέχρι Ν-1
    θέση <-- Ν
    για ψ από Ν-1 μέχρι χ με βήμα -1
      αν Α[ψ] < Α[θέση] τότε
         θέση <-- ψ
      τέλος_αν
    τέλος_επανάληψης
    αντιμετάθεσε Α[χ],Α[θέση]
τέλος_επανάληψης


τώρα λοιπόν βάζω κι έναν μετρητή που να μετράει πόσες φορές αλλάζει το minimum:

Κώδικας: bash
για χ από 1 μέχρι Ν-1
    θέση <-- Ν
    φορές <-- 0
    για ψ από Ν-1 μέχρι χ με βήμα -1
      αν Α[ψ] < Α[θέση] τότε
         θέση <-- ψ
         φορές <-- φορές + 1
      τέλος_αν
    τέλος_επανάληψης
    αντιμετάθεσε Α[χ],Α[θέση]
τέλος_επανάληψης


και τώρα σκέφτομαι ότι αν ο μετρητής βγει ίσος με Ν-χ, σημαίνει ότι άλλαξε σε όλες τις επαναλήψεις που εκτελέστηκαν, άρα ο πίνακας είναι ταξινομημένος σε αύξουσα σειρά, άρα μπορούμε να έχουμε και μια «έξυπνη ταξινόμηση με επιλογή»

Κώδικας: bash
χ <-- 0
αρχή_επανάληψης
    χ <-- χ + 1
    θέση <-- Ν
    φορές <-- 0
    για ψ από Ν-1 μέχρι χ με βήμα -1
      αν Α[ψ] < Α[θέση] τότε
         θέση <-- ψ
         φορές <-- φορές + 1
      τέλος_αν
    τέλος_επανάληψης
    αντιμετάθεσε Α[χ],Α[θέση]  
μέχρις_ότου χ = Ν-1 ή φορές = Ν-χ


διορθώστε με αν κάνω κάπου λάθος, ή αν λέω κάτι που έχει ξαναειπωθεί

και επανέρχεται η αρχική απορία...
γιατί φυσαλίδα;

evry

Οι αλγόριθμοι που θα σκεφτεί κάποιος άνθρωπος για να ταξινομήσει μια σειρά από αντικείμενα είναι δυο , ο αλγόριθμος εισαγωγής και αυτός της επιλογής. Με βάση έρευνες που έχω κάνει και επιβεβαιώσει με άλλες στη βιβλιογραφία οι δυο αυτοί αλγόριθμοι είναι οι επικρατέστεροι αφού προκύπτουν με την κοινή λογική.
Η ταξινόμηση με επιλογή έχει και το πλεονέκτημα που αναφέρεις ότι μπορεί να χτιστεί πάνω στον αλγόριθμο υπολογισμού της μέγιστης/ελάχιστης τιμής.
Δες την παρακάτω εργασία
https://www.etpe.gr/custom/pdf/etpe2383.pdf

και εδώ στη σελίδα 110.
https://drive.google.com/file/d/1ZW2Vrko60l8HagS3frLHuASBmH39519j/view

Αν και λογικά η απάντηση που ψάχνεις είναι στη γνωστή εργασία του Astrachan:
Bubble Sort: An Archaeological Algorithmic Analysis

Ότι δηλαδή η bubble sort επιλέχθηκε όχι μόνο στο δικό μας μάθημα αλλά και στα περισσότερα εισαγωγικά μαθήματα προγραμματισμού διεθνώς επειδή έχει το χαρακτηριστικό που ανέφερες. Απομνημονεύεται εύκολα. ;)

ΥΓ. Ο συνάδελφος που λες μάλλον είναι ο Γιώργος ο Παπαργύρης.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

gpapargi

#2
Πιθανόν να είμαι εγώ  :)
Αυτό που θα πρέπει να είπα (αν θυμάμαι καλά) είναι ότι η φυσαλίδα έχει λόγο ύπαρξης λόγω της έξυπνης version. Επίσης αν θυμάμαι καλά θα πρέπει να έχω γράψει ότι δεν έχει νόημα να διδάσκουμε την απλή φυσαλίδα και να μένουμε σε αυτή χωρίς να καταλήγουμε στην έξυπνη version. Αν είναι να κάνεις απλή φυσαλίδα και να μένεις σε αυτή, καλύτερα θα ήταν να κάναμε επιλογή.
Επίσης θα πρέπει να έγραψα σχετικά πρόσφατα ότι η φυσαλίδα θα πρέπει να προέκυψε από «φυσαλιδοποίηση» της επιλογής. Δηλαδή ένα κομμάτι το έγραψες από μόνος σου φτιάχνοντας μια έξυπνη επιλογή που εντοπίζει την πρόωρη ταξινόμηση. Ένα ακόμα βήμα είναι να σκεφτείς να ελέγχεις πότε 2 στοιχεία είναι σε αντεστραμμένη σειρά από αυτή που θέλουμε. Και τέλος, κάθε φορά που βλέπεις 2 στοιχεία σε αντεστραμμένη σειρά να τα αντιμεταθέτεις μήπως φτάσεις πιο γρήγορα στην πρόωρη ταξινόμηση σε κάποιο επόμενο βήμα.  Κάπως έτσι καταλήγεις τη φυσαλίδα.

epsilonXi

Παράθεση από: evry στις 12 Μαΐου 2019, 09:04:17 ΜΜ
Δες την παρακάτω εργασία
https://www.etpe.gr/custom/pdf/etpe2383.pdf

και εδώ στη σελίδα 110.
https://drive.google.com/file/d/1ZW2Vrko60l8HagS3frLHuASBmH39519j/view

Αν και λογικά η απάντηση που ψάχνεις είναι στη γνωστή εργασία του Astrachan:
Bubble Sort: An Archaeological Algorithmic Analysis

πολύ ενδιαφέρουσες οι παραπομπές, ευχαριστώ!