[CST-2] Kolmogorov complexity - cost of sorting

[Jonny Graham]

I'm a bit confused as to what this O(n) algorithm is doing then.
You wrote
"It now makes sense, but you can also reverse the sorting with O(n) (in
fact, precisely n) integers: just record the original position of each
value in the output. To reverse, copy each value back to its original
position: O(n) "unsorting" using O(n) space and time."

I understand this as meaning that the O(n) algorithm isn't capable of 
sorting unless it has some additional information - "record the original 
position of each value in the output". So this is different from an 
algorithm which takes as input *only* a list of integers (or whatever) 
and outputs them in sorted form. Is that right?

Sanity check: The best we can do for sorting in the general case is 
nlogn, isn't it?

Jonny

James Sutherland wrote:
> On Fri, 31 May 2002, Jonny Graham wrote:
> 
> 
>>But this O(n) algorithm isn't 'sorting' it's just rearranging by a fixed
>>  list of swaps.
> 
> 
> Nope. It's **NOT** a fixed list of anything. It runs through the input
> some constant number of times, building progressively "more sorted" and
> smaller subsets of the input, until they are all fully sorted. (The
> constant number of times is determined by the size of input; e.g. using
> 256 way splits on 32 bit integers gives 4 passes.)
> 
> 
>>If instead of 'cheating' with a list of swaps to do to
>>sort I 'cheated' by passing it a list of the same numbers sorted, I
>>could 'sort' in O(1) time by just returning the sorted version;-)
> 
> 
> This algorithm *does* operate on arbitrary input, without prior knowledge
> of the values, their order or anything else. It takes a list of integers
> (or whatever you're sorting - strings, floats...) and returns that list,
> sorted. That's it.
> 
> 
> James.
> 
> 
> 
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2


-- 
Jonny Graham
01223 565 373
07753 841 971

Selwyn College
Grange Road
Cambridge
CB3 9DQ

--My email account will cease to exist on 15/7/02--
--My new email address is jonnygraham@cantab.net --