Θέμα: Νεοι αλγοριθμοι ταξινομησης

[tsak]

Καλησπερα σε ολους. Θεωρειτε οτι υπαρχει περιπτωση να ζητηθεί με κάποιον τρόπο συγκεκριμένος αλγόριθμος ταξινομησης σε άσκηση ?  Σε μια άσκηση που απαιτείται ταξινόμηση δεν εχει την ελευθερία ο μαθητής να επιλέξει όποιον αλγόριθμο ταξινομησης επιθυμεί?

[itt]

Εαν ζητηθεί αλγόριθμος ταξινόμησης με συγκεκριμένη πολυπλοκότητα τότε θα πρέπει να επιλέξει από αυτούς που την παρουσιάζουν.

[petrosp13]

Μα στην νέα ύλη ορίζεται οτι ο μαθητής δεν θα ασχολείται με υπολογισμό πολυπλοκότητας

[itt]

Θυμόμουν που το ανέφερες σε ένα ποστ σου σε άλλο thread και υπέθεσα ότι είναι στην ύλη. Λάθος κατάλαβα τότε.

[gthal]

Πλην της quicksort, οι άλλοι 3 αλγόριθμοι που (ακόμα υποθέτουμε ότι) θα "μάθουμε" είναι O(n²) , σωστά ?
Θα μπορούσαμε να πούμε λοιπόν ότι είναι το ίδιο αποδοτικοί ή όχι αποδοτικοί.
Παρόλα αυτά η φυσαλίδα είναι σημαντικά πιο αργή από τους δύο άλλους.
Πώς θα μπορούσε αυτό να το εκτιμήσει κανείς apriori, αν όχι μέσω του υπολογισμού της τάξης τους? ? ?
(Τελικά αυτός ο big-O συμβολισμός δε μου έχει κάτσει καθόλου. Ή κάτι δεν έχω καταλάβει ή βγαίνει έξω από τα όρια του ντετερμινισμού για το δικό μου αισθητήριο... )

[evry]

Και η quicksort Ο(n²) είναι  .
https://en.wikipedia.org/wiki/Quicksort. Απλά αυτό είναι πολύ σπάνιο να συμβεί, που σημαίνει ότι πρακτικά είναι πολύ γρήγορη, θεωρητικά όμως .... στα ίδια
 Όταν μιλάμε για πολυπλοκότητα χωρίς να διευκρινίζουμε εννοούμε την πολυπλοκότητα στην χειρότερη περίπτωση.
Στη μέση περίπτωση είναι O(nlogn) ενώ για παράδειγμα η πολυπλοκότητα της MergeSort είναι O(nlogn) στην χειρότερη περιπτωση.

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

Η συγκριτική ταξινόμηση.... ταξινομήσεων λοιπόν πρέπει να μείνει έξω από την ενότητα της απόδοσης αλγορίθμων.
Καλύτερα να δείχνουμε στα παιδιά κραυγαλέα παραδείγματα όπως
σειριακή / δυαδική
άθροισμα στοιχείων κυρίας διαγωνίου με διπλή και μονή (Α[ι,ι]) επανάληψη
Υπολογισμό αθροίσματος των πρώτων ν αριθμών με επανάληψη και με τον τύπο κλπ

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

[iomil]

Καλησπέρα! Να πω κι εγώ τον πόνο μου;;
Στις νέες μεθόδους ταξινόμησης θα πρέπει να ασχοληθούμε και με την περίπτωση που έχουμε παράλληλους πίνακες με μη μοναδικά στοιχεία;;