Sorting in Linear Time

Question

I need to write an algorithm of sorting the array of size [0..N-1], that is filled with the values of the range [0..N-1]. Values in the array can not be repeated. The sorting should work in a linear time, and I allowed to use only some additional variable.

plz comment the code i wrote. As far as I guess the worst time is 2*N. Is is still a linear time? Is it possible to make is faster?

public int sort(){
    int i  = 0;             
    while (i < n){
        if (a[i] != i)      
            switchElements(a[i], a[a[i]]);                  
        else
            i++;                    
    }
    return count;
}

additional 1 I really need to sort the array, cause sorting is only the part of the task. The full task is to find is there a duplicate values in array, in a linear time, and no additional variables.

You might need to reword parts of your question, as you state "Values in the array can not be repeated", but then later "The full task is to find is there a duplicate values in array". Either there are duplicates or not, you can't have both... Outside of that, though, I think that the trick might be to realize that an array of `N` elements in the range `[0, N-1]` with no duplicates means each number in the range appears exactly once, and so the sorted result is simply the sequence `0 ... N-1`. — twalberg, Nov 12 '12 at 19:30
The task is to find the duplicate keys. So, i'm gonna sort the array, considering there is no duplicate values. But before switching the elements, i'm gonna check if in the cell is already the correct value and throw the message in that case — a3dsfcv, Nov 12 '12 at 19:43
@user1448906 Looks fine then. I don't think there is a more efficient way to do that. — Anirudh Ramanathan, Nov 12 '12 at 20:14

Anirudh Ramanathan · Answer 1 · 2012-11-12T20:24:07.703

5

Answer to original question:

Array with elements [0..N-1], containing non-repeated elements [0..N-1]

Why even sort? The sorted array is already known and is [0..N-1].

Considering your additional 1: Your algorithm looks fine, you are looking at each element once, and have to look at each one atleast once, so it can't get better. Also 2*N is also O(N).

edited Nov 12 '12 at 20:24

answered Nov 12 '12 at 19:10

Anirudh Ramanathan

46,179
22
132
191

It's not `O(1)` but the question still applies: Why even sort? – John Dvorak Nov 12 '12 at 19:12
the only thing i can come up with is some values might be not be present; i.e. null values. – hvgotcodes Nov 12 '12 at 19:13
@hvgotcodes `int`s can't be `null`. Still a good point if `NaN`s of any form may be present and repeated – John Dvorak Nov 12 '12 at 19:15
@hvgotcodes in that case, `switchElements(a[i], a[a[i]]);` in the OP's code would fail, if it was some invalid number. – Anirudh Ramanathan Nov 12 '12 at 19:17
if this is a Java question you should tag it as such. Else this is language agnostic. – hvgotcodes Nov 12 '12 at 19:22
that's language agnostic for sure – a3dsfcv Nov 12 '12 at 19:29

score 1 · Accepted Answer · edited May 23 '17 at 12:27

1

In order to detect duplicates you can extend that logic further, forcing the values into their respective spots.

public int sort(){
    int i  = 0;             
    while (i < n){
        while (a[i] != a[a[i]])      
            switchElements(a[i], a[a[i]]);                  
        ++i;                    
    }
    return count;
}

and in the end, if for any i, i and A[i] do not match that would indicate a repetition!
Overall it would be still O(N) procedure.

For more details refer to following post:
Finding duplicates in O(n) time and O(1) space

edited May 23 '17 at 12:27

Community

1
1

answered Nov 12 '12 at 19:39

srbhkmr

2,074
1
14
19

I've solved that task, and deliberately changed the code, and didnt firstly write about duplications to make it more clear for u. The question was if it is possible to make it faster ;) – a3dsfcv Nov 12 '12 at 19:47
P.S. according to ur link - the answer is no. I wrote that by myself and didnt know such algo is already exists – a3dsfcv Nov 12 '12 at 20:20

Sorting in Linear Time

2 Answers2