Γρήγορη ταξινόμηση
From Wikipedia, the free encyclopedia
Στην επιστήμη των υπολογιστών, η γρήγορη ταξινόμηση (αγγλικά: Quick-sort ή ως partition-exchange sort) είναι ένας αλγόριθμος ταξινόμησης, ο οποίος αναπτύχθηκε από τον Τόνι Χορ, που κατά μέσο όρο κάνει O(nlogn) συγκρίσεις για να ταξινομήσει n στοιχεία.[1] Στην χειρότερη -σπάνια- περίπτωση, κάνει O(n2) συγκρίσεις. Ο αλγόριθμος γρήγορης ταξινόμησης συχνά είναι γρηγορότερος από αντίστοιχους άλλους O(nlogn) αλγορίθμους και κατατάσσεται στους αλγορίθμους διαίρει και βασίλευε (όπου το πρόβλημα διασπάται σε μικρότερα προβλήματα και λύνεται το κάθε πρόβλημα ξεχωριστά).[2] Ο αλγόριθμος αυτός μπορεί να υλοποιηθεί με αναδρομική συνάρτηση.[3]