An Analysis of the Application of Randomized Selection Algorithms in Solving Computational Problems

Abstract

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.