An Analysis of the Application of Randomized Selection Algorithms in Solving Computational Problems
Fájlok
Dátum
Szerzők
Folyóirat címe
Folyóirat ISSN
Kötet címe (évfolyam száma)
Kiadó
Absztrakt
This study investigates the computational behavior of randomized selection algorithms in median finding and partial sorting, with a focus on time complexity, stability, and worst-case probability. Through mathematical analysis, it examines the performance of QuickSelect and Median-of-Medians across different data distributions, and quantifies the impact of random pivot selection. Experimental comparisons between Randomized QuickSort and deterministic HeapSort explore how input characteristics affect worst-case behavior. The findings aim to guide algorithm selection for large-scale data processing by clarifying the performance trade-offs of randomized methods.
Leírás
Kulcsszavak
randomized selection algorithms, randomized algorithms