Υλοποίηση πιθανοτικού "Quicksort" με έμφαση στην κλιμάκωση και στην κατανομή των δεδομένων εισόδου
Loading...
Date
2024-07-17
Authors
Γεωργιόπουλος, Σπυρίδων
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Οι αλγόριθμοι ταξινόμησης κατέχουν έναν θεμελιώδη ρόλο στην επιστήμη των υπολογιστών και είναι απαραίτητοι για την οργάνωση και ταξινόμηση δεδομένων σε πολλές εφαρμογές της πληροφορικής. Ανά τα έτη, η επιστημονική κοινότητα έχει αναπτύξει διάφορους αλγόριθμους, καθένας από τους οποίους διαθέτει τα μειονεκτήματα και τα πλεονεκτήματά του έναντι των υπολοίπων. Ανάμεσα σε αυτούς τους αλγορίθμους, ξεχωρίζει ο αλγόριθμος Quicksort.
Σε αυτή τη διπλωματική εργασία μελετούμε μια νέα προσέγγιση για να ενισχύσουμε την αποδοτικότητα του αλγορίθμου με την ενσωμάτωση πιθανοτικών τεχνικών στην υλοποίησή του. Η έρευνά μας επικεντρώνεται στην αξιοποίηση της ενσωματωμένης τυχαιότητας μέσα στον Quicksort για να βελτιώσουμε περαιτέρω την απόδοσή του.
Συγκεκριμένα, γίνονται μετρήσεις για τα μεγέθη της λοξότητας και της κυρτότητας που
ακολουθούν οι διαμερίσεις των υποπινάκων. Πραγματοποιήσαμε εκτενείς δοκιμές με διαφορετικά μεγέθη δεδομένων, τα οποία δημιουργήσαμε τυχαία και ακολουθούν τέσσερις κατανομές
τις poisson, uniform,geometrical, Binomial. Οι μετρήσεις αυτές μας επέτρεψαν να αξιολογήσουμε την αποδοτικότητα και την προσαρμοστικότητα του πιθανοτικού Quicksort σε
διάφορες συνθήκες, παρέχοντας πολύτιμα ευρήματα για τη βελτιστοποίηση του αλγορίθμου σε
διαφορετικά περιβάλλοντα και εφαρμογές.
Description
Keywords
Λοξότητα, Διωνυμική κατανομή, Αλγόριθμος, Ομοιόμορφη κατανομή