Ταξινόμηση μονοδιάστατου πίνακα

[gpapargi]

Όπως τα λέει ο Ευριπίδης. Να το πω και εγώ με δικά μου λόγια και να προσθέσω και ένα δυο πράγματα.

Όταν πάει κάποιος να κάνει ταξινόμηση, το πρώτο πράγμα που θα κάνει αυθόρμητα είναι το εξής:
Σαρώνει από την πρώτη θέση μέχρι την τελευταία, βρίσκει το μεγαλύτερο στοιχείο και το βάζει στην πρώτη  θέση. Μετά σαρώνει από τη δεύτερη θέση μέχρι την τελευταία, βρίσκει το δεύτερο μεγαλύτερο (το πρώτο μεγαλύτερο εκτός από το στοιχείο της πρώτης θέσης που είναι ήδη το μέγιστο) και το βάζει στη δεύτερη θέση κλπ.

Στο τυχαίο  βήμα ι αυτής της διαδικασίας θα ψάξει από τη θέση ι μέχρι τη ν, θα βρεί το μεγαλύτερο (από εκεί και κάτω) και θα το βάλει στη ι θέση. Αυτό γίνεται εύκολα ως εξής:

max_pos<-i                             
Για j από i+1 μέχρι ν
   Αν α[j] > α[max_pos] τότε
        max_pos <- j                 ! κρατάμε τη θέση του μεγίστου
   Τέλος_αν
Τέλος_επανάληψης   
Αντιμετάθεσε α[max_pos], α[ι]

Επειδή το παραπάνω πρέπει να γίνει για κάθε ι από 1 μέχρι ν-1 αγκαλιάζουμε το παραπάνω κομμάτι κώδικα με μια Για ι από 1 μέχρι ν-1 και τελειώσαμε. Αυτή είναι η ταξινόμηση επιλογής. Η πρώτη σκέψη για ταξινόμηση που κάνει ένας άνθρωπος.

Το ερώτημα που γεννιέται είναι το εξής:

Αφού αυτό είναι πιο απλό γιατί να πάμε στην ανώμαλη σκέψη της φυσαλίδας; Γιατί δεν διδάσκουμε ταξινόμηση επιλογής αφού αναδύεται αυθόρμητα στην ανθρώπινη σκέψη;

Η απάντηση που δίνω εγώ είναι ότι η φυσαλίδα έχει το γρήγορο version (τετράδιο μαθητή κεφάλαιο 3 ΔΤ2). Επειδή συγκρίνει τα διαδοχικά στοιχεία μπορείς να καταλάβεις πότε η λίστα είναι ήδη ταξινομημένη και έτσι να κόψεις πρόωρα την ταξινόμηση κερδίζοντας σε χρόνο. (Στο συνέδριο της Πάτρας, 2 από τους συμμετέχοντες αυτής της κουβέντας μαζί με άλλον έναν κουβεντιάσαμε το θέμα αλλά λόγω ώρας δεν ολοκληρώσαμε την κουβέντα).

Μια σκέψη είναι η εξής: Πιθανόν αφού είχε δημιουργηθεί η ταξινόμηση της επιλογής, κάποιος θα θέλησε να την κάνει πιο γρήγορα. Έτσι θα έβαλε και ένα έλεγχο στο μέσα βρόχο της επιλογής που να ελέγχει αν από τη θέση ι και κάτω είναι όλα τα στοιχεία ταξινομημένα. Ουσιαστικά αυτό είναι (ας μου επιτραπεί η έκφραση) «φυσαλιδοποίηση» της επιλογής αφού μπαίνουμε στη λογική της σύγκρισης διαδοχικών στοιχείων. Η επόμενη λογική σκέψη είναι η εξής: «Γιατί να βρίσκουμε το μέγιστο από τη θέση ι και μετά αλλά ΚΑΙ  να ελέγχουμε και αν είναι ήδη ταξινομημένα τα στοιχεία και να μη μείνουμε μόνο στον δεύτερο έλεγχο αφού θα γίνει έτσι κι αλλιώς; Αν είναι έτσι, απλά θα κάνουμε τις αντιμεταθέσεις κάθε φορά που βρίσκουμε ζεύγος εκτός θέσης. Κάπως έτσι φαντάζομαι ότι ξεκίνησε η ιδέα της φυσαλίδας.

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

Η μόνη απάντηση που έχω είναι ότι αυτοί που καθορίζουν την ύλη δεν έχουν τη φιλοσοφία του να ξέρουμε γιατί κάνουμε κάτι. Είναι πάγια θέση μου ότι πρέπει να ξέρουμε τι διδάσκουμε και γιατί το διδάσκουμε έτσι ώστε να βγαίνει κάποιο νόημα για τα παιδιά και για μας. Δυστυχώς έχω και άλλα παραδείγματα που δείχνουν κάτι τέτοιο.
Πχ ταξινόμηση κάνεις για να μπορέσεις μετά να κάνεις γρήγορη αναζήτηση. Δεν έχει νόημα να ταξινομήσεις κάτι και μετά να ψάχνεις ένα ένα με τη σειρά για να βρεις αυτό που θέλεις.
Τι νόημα έχει λοιπόν να διδάσκουμε ταξινόμηση και να έχουμε εκτός ύλης τη δυαδική αναζήτηση (που είναι πολύ απλή); Τι νόημα θα μπορούσε να βγάλει για όλα αυτά ένας μαθητής; Και πως θα μπορούσαμε εμείς να εξηγήσουμε ότι αυτά που διδάσκουμε έχουν νόημα και δένουν αρμονικά μεταξύ τους;

[pgrontas]

Συμφωνώ απόλυτα με τις παρατηρήσεις σας για την ταξινομήση ευθείας επιλογής και φυσαλίδας.
Να προσθέσω και μερικές δικές μου:
-Η ταξινόμηση ευθείας επιλογής έρχεται ως φυσική συνέχεια όσων έχουν διδαχθεί οι μαθητές προηγουμένως για την εύρεση ελάχιστου (ή μεγιστου) πίνακα. Αντί να χρησιμοποιηθεί αυτό το γεγονός για να υπάρχει συνέχεια στο διδακτικό πακέτο και να διαπιστώσουν οι μαθητές ότι αυτά που μαθαίνουν έχουν ουσιαστική χρησιμότητα (δεν είναι ασκήσεις επί χάρτου), έρχεται η φυσαλίδα από το πουθενά.
-Ο συνδυασμός εύρεσης ελαχίστου και ταξινόμησης μπορεί να χρησιμοποιηθεί ως μια εισαγωγή στην έννοια της αφαίρεσης που επιτυγχάνεται με τα υποπρογράμματα (με εύρεση της θέσης όπως πρότεινε ο ευρυπίδης ή της ελάχιστης τιμής).

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

[mmsoft]

  Ο αλγόριθμος που δίνεις είναι ουσιαστικά η ταξινόμηση με επιλογή. Δηλαδή σε κάθε βήμα βρίσκεις το μέγιστο και το ανταλλάσεις με το Ι στοιχείο.
Αν αυτό που ζητάς είναι η απλότητα θα μπορούσες να γράψεις κάτι σαν το παρακάτω

Κώδικας: ΓΛΩΣΣΑ

ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν-1
    μ <-- ΘέσηΜεγίστου(Ι,Α)
   Τ <- Α[Ι]
   Α[Ι] <- Α[μ]
   Α[μ] <- Τ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

όπου η συνάρτηση ΘέσηΜεγίστου(Ι, Α) επιστρέφει τη θέση του μέγιστου στοιχείου του υποπίνακα Α[Ι+1....Ν]

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

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

[evry]

  Ο αλγόριθμος που δίνεις είναι ουσιαστικά η ταξινόμηση με επιλογή. Δηλαδή σε κάθε βήμα βρίσκεις το μέγιστο και το ανταλλάσεις με το Ι στοιχείο.
Αν αυτό που ζητάς είναι η απλότητα θα μπορούσες να γράψεις κάτι σαν το παρακάτω

Κώδικας: ΓΛΩΣΣΑ

ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν-1
    μ <-- ΘέσηΜεγίστου(Ι,Α)
   Τ <- Α[Ι]
   Α[Ι] <- Α[μ]
   Α[μ] <- Τ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

όπου η συνάρτηση ΘέσηΜεγίστου(Ι, Α) επιστρέφει τη θέση του μέγιστου στοιχείου του υποπίνακα Α[Ι+1....Ν]

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

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

Μα δεν θα το μετακινήσει αφού για I=1 αν το μέγιστο είναι στην πρώτη θέση τότε μ=1 άρα η μετακίνηση δεν θα έχει κανένα αποτέλεσμα.
Τώρα όσον αφορά την απλότητα πιστεύω ότι ο παραπάνω αλγόριθμος είναι πολύ πιο απλός για τον μαθητή γιατί έχει μόνο μια επανάληψη και είναι φανερό ότι κάθε φορά υπολογίζει το μέγιστο. Η απλότητα προκύπτει από τη χρήση της συνάρτησης.