Cycle Sort

http://corte.si/posts/code/cyclesort/index.html

by suraj • 16 years ago

55 16 16 years ago

It's nice to say this algorithm is virtually O(n) in practice, but that's about the "cycling" mechanism only. It needs to prepare a dictionary with offsets, which has to loop over all the keys, perform an O (log n) insert operation on all the keys, and allocate memory on the heap. This already makes it (almost) O (n log n), without even doing the actual sorting.

It's a nice idea, but it's not O(n).

jemfinch3• 16 years ago

> It needs to prepare a dictionary with offsets, which has to loop over all the keys, perform an O (log n) insert operation on all the keys

Surely you've heard of hash tables.

Deestan• 16 years ago

As with all other dictionary/map implementations, hash tables are O(log n) in the general case.

stingraycharles3• 16 years ago

Hash tables still are O (n) worst-case scenario for each insert operation. Besides, that doesn't solve the heap allocation issue, which usually are O(log n) (for tree-based allocators).

JoachimSchipper2• 16 years ago

It doesn't necessarily have to prepare that dictionary (e.g. when sorting n tuples that contain a unique number 0..n).

Also consider the case of sorting n tuples that contain a non-unique number 0..k, with k << n: you can now create your dictionary in O(n) time by using a multidimensional array (k arrays of length n plus some counters; smarter solutions are probably possible) and "serializing" to a normal array.

jsharpe• 16 years ago

There are much simpler sorts in those cases though, like just outputting (0, 1, 2, ..., n) or (0, 1, 2, ..., k). Those are O(n) without any shenanigans. ;)

mise• 16 years ago

Nice use of Slovenia's TLD.

mfukar• 16 years ago

I believe that the author is referring to the case when the array to be sorted contains only duplicates of a small number of items, where a perfect hash function can speed up insertion; this turns cycle sort's time complexity into Θ(n+k), with k being the number of hashes. In such a case, k is not negligible compared to n, so I wouldn't feel comfortable saying cycle sort is O(n), as he does.

In the general case, cycle sort is Θ(n^2) with a total space complexity of Θ(n).

edit:typos.

kingkilr• 16 years ago

This doesn't sound remotely right. If n is the number of elements, k is the number of distinct elements, and its O(n + k) as the author describes, k is trivially bounded by n (you can't have more distinct elements than you do elements). Resulting in O(n) complexity, how did you get O(n^2)?

ancymon• 16 years ago

I wonder how it sounds ;)

tsewlliw• 16 years ago

If you must restrict the input to permutations of [0,...,N], you already know the result! Finding cycles is neat, but this works for the same data, minus having bounds:

(define (trivialsort vals) (lambda (i) i))

Cycle Sort

Related Stories