Title :
Linear time sorting of skewed distributions
Author :
de Moura, Edleno Silva ; Navarro, Gonzalo ; Ziviani, Nivio
Author_Institution :
Dept. de Ciencia de Computacao, Univ. Fed. de Minas Gerais, Belo Horizonte, Brazil
Abstract :
The article presents an efficient linear average time algorithm to sort lists of integers that follow skewed distributions. It also studies a particular case where the list follows Zipf´s distribution, and presents an example application where the algorithm is used to reduce the time to build word-based Huffman codes
Keywords :
Huffman codes; computational complexity; probability; sorting; Zipf distribution; linear average time algorithm; linear time sorting; skewed distributions; word-based Huffman codes; Acceleration; Adaptive algorithm; Partitioning algorithms; Random sequences; Scholarships; Sorting;
Conference_Titel :
String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware
Conference_Location :
Cancun
Print_ISBN :
0-7695-0268-7
DOI :
10.1109/SPIRE.1999.796588
