Paper Info
Title
Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)
Abstract
Recently, many results on the computational complexity of sorting algorithms were obtained using Kolmogorov complexity (the incompressibility method). Especially, the usually hard average-case analysis is ammenable to this method. Here we survey such results about Bubblesort, Heapsort, Shellsort, Dobosiewiczsort, Shakersort, and sorting with stacks and queues in sequential or parallel mode. Especially in the case of Shellsort the uses of Kolmogorov complexity surprisingly easily resolved problems that had stayed open for a long time despite strenuous attacks.
Year
DOI
Venue
2009
10.1007/978-3-540-32777-6_9
Computing Research Repository
Keywords
DocType
Volume
sorting algorithm,computational complexity,data structure
Journal
abs/0905.4452
Citations 
PageRank 
References 
1
0.43
17
Authors
1
Name
Order
Citations
PageRank
Paul Vitányi12130287.76