Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Κ17.8 · Η πιο γρήγορη ταξινόμηση στη χειρότερη περίπτωση

Kahoot «Δυαδική Αναζήτηση και Ταξινόμηση» (διάλεξη 17) · Δυσκολία ★★★ · multiple-choice · 28% σωστές απαντήσεις (71 απαντήσεις στο αμφιθέατρο) · Κεφάλαια: 17, 18

Ποια μέθοδος ταξινόμησης είναι πιο γρήγορη στη χειρότερη περίπτωση;

• insertion sort
• selection sort
• quicksort
• bubblesort
• Καμία, όλες είναι O(n²)

Συχνή παρανόηση

Το 35% επέλεξε την quicksort, που είναι O(n log n) στη μέση περίπτωση αλλά O(n²) στη χειρότερη (κακή επιλογή pivot). Ένα 27% επέλεξε την bubblesort, ίσως επειδή τελειώνει γρήγορα σε ήδη ταξινομημένο πίνακα, που όμως είναι η καλύτερη και όχι η χειρότερη περίπτωση.

Υπόδειξη

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

Αριθμός στον οδηγό: Κ17.8 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: kahoot-sort-worst-case · Σύνδεσμος: https://progintro.github.io/study/questions/kahoot/kahoot-sort-worst-case.html · Markdown (GitHub)