Analysis of Sorting Algorithms by Kolmogorov Complexity

by: Survey P Vit

View FullText article

CiteSeer (at Penn State), CiteSeer (at MIT), CiteSeer (at Zurich), CiteSeer (at Singapore)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

scis0000001, AbnerCYH, neilc, CSBBGraphTheory (group)

Find related articles with these CiteULike tags

algorithm, algorithms, analysis, complexity, information, kolmogorov, kolmogorov-complexity, math

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, Dobosiewicz-sort, 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...

@misc{citeulike:849796, 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, Dobosiewicz-sort, 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...}, author = {Vit, Survey P. }, citeulike-article-id = {849796}, keywords = {complexity, kolmogorov}, posted-at = {2007-04-09 02:31:13}, priority = {2}, title = {Analysis of Sorting Algorithms by Kolmogorov Complexity}, url = {http://citeseer.ist.psu.edu/648660.html} }

RIS record

TY - GEN ID - citeulike:849796 L3 - citeulike-article-id:849796 TI - Analysis of Sorting Algorithms by Kolmogorov Complexity N2 - 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, Dobosiewicz-sort, 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... KW - complexity KW - kolmogorov AU - Vit, Survey UR - http://citeseer.ist.psu.edu/648660.html ER -

RIS BibTeX