Performance Comparison of Sorting and BFPRT Algorithms for the

Selection Problem

The selection problem in computer science refers to the task of finding the $k^{th}$ smallest or largest element in a list or an array. The goal is to determine the item at a specific position in the sorted order of the elements. This problem has various algorithms and approaches to efficiently locate the $k^{th}$ element without fully sorting the entire list, which can be computationally expensive, especially for large datasets.

Consider an array of size $n$ and solve the selection problem using two methods: by sorting the array and by applying the Blum$-$Floyd$-$Pratt$-$Rivest$-$Tarjan $($BFPRT$)$ selection algorithm. Compare these two approaches under different conditions:

Use array sizes $n=100,1000,10000,100000,$ and $1000000.$

Test values of $k$ from $1$ up to $n($to find the $k^{th}$ smallest element$).$

Record and compare the actual runtime of both algorithms across these scenarios. Analyze the efficiency of each algorithm with respect to varying $n$ values and determine which approach performs better in specific cases. Provide a detailed analysis to support your findings.