ENGLISH

Probabilistic analysis of some searching and sorting algorithms

By Lent J.

Book information

Year
1996
Language
english
Format
DJVU
Filesize
1 MB (1502877 bytes)
Edition
Dissertation
Pages
112\112
Library
Kolxo3
DPI
300
Time added
2009-07-20 03:45:11

Description

We use binary trees to analyze two algorithms, insertion sort and multiple quckselect. In each case, we consider the number of comparisons consumed as a measure of performance. We assume that the ranks of the n data values being searched or sorted form a random permutation of the integers {l,...,n}. For insertion sort, we consider the limiting distribution of the number of comparisons consumed in the process of sorting the n keys. We present an average-case analysis of the number of comparisons multiple qukkselect (MQS) requires for simultaneously finding several order statistics in the data set.

Similar books