Springe direkt zu Inhalt

Jiale Cheng:

An experimental evaluation of selection algorithms


Selection problem has been studied intensively over the last decades, and many diffe- rent algorithms are known. These algorithms have different performance in the ave- rage case, worst case,and best case. In my thesis, I mainly introduce some famous algorithms, compare their performance through experiment.

At the beginning of the thesis, I first introduce the mathematical premises of based on the comparative selection model, followed by the well-known selection problem, for which I focus on these algorithms Quickselect, BFPRT , Selecting using a random sample, and Heapsort, present the procedure, the pseudo-code, and the proof of the time complexity of these algorithms, and give an example of every algorithm. Then I put up python code of every algorithm, and in the final experiment I randomly ge- nerated 10,000 numbers and executed it 1,000 times to compare the time required by each algorithm to find the k-th samllest number in a unsorted array, and make final conclusions.

Bachelor of Science (B.Sc.)