Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)

Details Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey) Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey)

2009-05-27

arxiv.org/abs/0905.4452v1

Pp.209--232 in: In: Entropy, Search, Complexity, Bolyai Society Mathematical Studies, 16, I. Csiszar, G.O.H. Katona, G. Tardos

Computer Science

Data Structures and Algorithms

18 Pages, 2 figures, LaTeX

Scientific paper

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 problems that had stayed open for a long time despite strenuous attacks.

Affiliated with

Also associated with

No associations

Rating

Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of Sorting Algorithms by Kolmogorov Complexity (A Survey) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527868