Wednesday, March 05, 2008

[TECH] Sorting partially sorted sequences.

Partially Sorted Sequence: A sequence k1,k2, of n keys such that any key kj differs from its sorted position by atmost d as an example for d=3 we have 3,5,6,1,2,4 I came across this problem recently, turns out that we can solve this problem in several ways in O(nlog(d)) time. I found an interesting and simple way to solve this problem, a simple observation reveals that the smallest element in the entire sequence of n keys exists in the first d keys.

/*Build a heap(min) H with first d elements
 *in O(d) time
    DeleteMin(H); /*output this key*/
/*Note the Heap will have atmost d keys in it
at any time so the Insert and Delete can be done in 
O(log(d)) worst case.

(n-d)log(d) = O(nlog(d))

No comments: