Και η quicksort Ο(n
2) είναι

.
https://en.wikipedia.org/wiki/Quicksort. Απλά αυτό είναι πολύ σπάνιο να συμβεί, που σημαίνει ότι πρακτικά είναι πολύ γρήγορη, θεωρητικά όμως .... στα ίδια
Όταν μιλάμε για πολυπλοκότητα χωρίς να διευκρινίζουμε εννοούμε την πολυπλοκότητα στην χειρότερη περίπτωση.
Στη μέση περίπτωση είναι O(nlogn) ενώ για παράδειγμα η πολυπλοκότητα της MergeSort είναι O(nlogn) στην χειρότερη περιπτωση.
Δε νομίζω ότι είναι καλή ιδέα να συγκρίνουμε αλγόριθμους ταξινόμησης διότι δεν είναι απλό αφού έχουν σχεδόν όλοι έχουν την ίδια πολυπλοκότητα στην χειρότερη περίπτωση. Μιλάω μόνο για χειρότερη περίπτωση γιατί είναι κάτι που μπορείς αν θέλεις να το δείξεις στους μαθητές. Ο υπολογισμός της μέσης απόδοσης είναι πολύ δύσκολος.
Η συγκριτική ταξινόμηση.... ταξινομήσεων λοιπόν πρέπει να μείνει έξω από την ενότητα της απόδοσης αλγορίθμων.
Καλύτερα να δείχνουμε στα παιδιά κραυγαλέα παραδείγματα όπως
σειριακή / δυαδική
άθροισμα στοιχείων κυρίας διαγωνίου με διπλή και μονή (Α[ι,ι]) επανάληψη
Υπολογισμό αθροίσματος των πρώτων ν αριθμών με επανάληψη και με τον τύπο κλπ
Στις ταξινομήσεις για να εξηγήσεις τι συμβαίνει θα πρέπει να μελετήσεις τη συμπεριφορά των αλγορίθμων για διάφορες περιπτώσεις συνόλων δεδομένων, π.χ. σχεδόν ταξινομημένων πινάκων κλπ.
Για παράδειγμα η ταξινόμηση με επιλογή θα κάνει πάντα Ο(n
2) ενώ η φυσαλίδα για κάποια σύνολα μπορεί να κάνει Ο(n) .