Sort first n integers in linear time and constant space

views:

168

answers:

+3 Q:

Sort first n integers in linear time and constant space

I'm looking for a non-comparison or comparison based algorithm that can sort an array containing any permutation of the first n positive integers, which should be O(n) time complexity and O(1) space complexity.

Is there an existing algorithm that fits these specifications?

+2 A:

if you have an array of size N with all integers from say 1 to N present, you can use the following O(n) algorithm (Note: arrays are 1 based for the sake of this pseudocode so as not to introduce unnecessary complexity in explaining the algorithm):

Start at the first array element.
If it's array index matches it's value, go to the next one.
If not, swap it with the value at the array index corresponding to its value.
Repeat step 3, until no more swaps are necessary.
If not at the end of the array, go to the next array element, otherwise go to step 7
Go to step 2.
Done

Michael Goldshteyn 2010-10-20 15:17:20

@Michael Goldshteyn: if you have an array of length N which contains all the integers from 1 to N, why would you sort it at all when you could just write the integers in order into the array ?

High Performance Mark 2010-10-20 15:19:54

@Mark, Perhaps he is considering the case where the integers are merely keys for the records. Here, just writing the integers in order won't help put the associated records in sorted order.

Kedar Soparkar 2010-10-20 15:27:11

yes, I am considering the case where the integers are keys, sorry for not mentioning that

fmunshi 2010-10-20 15:55:25

@Michael Goldshteyn the algorithm you described, does it have a name, is it "in place MSD Radix sort as Kedar Soparkar mentioned.

fmunshi 2010-10-20 15:56:54

The MSD Radix sort is a completely different bit based algorithm. To be perfectly honest, the algorithm I described probably has a name, but I just came up with it off of the top of my head, because for an experienced developer it just seems like an obvious approach.

Michael Goldshteyn 2010-10-20 16:25:06

@fmunshi: His algorithm is a counting sort optimized for your conditions.

Eric Towers 2010-10-20 16:45:32

+2 A:

In-place MSD radix sort

Kedar Soparkar 2010-10-20 15:17:27

That algorithm is beautiful in its simplicity. I'll have to find an excuse to use it some day.

Mark Ransom 2010-10-20 15:54:13

ansaurus

tags:

views:

answers:

Sort first n integers in linear time and constant space

related questions