CODEWITHSUNDEEP
arraysalgorithmsorting
frytkii
frytkii

Reputation: 31

Is it possible to sort an array in O(n) if there are only elements from 1 to n?

Let's say the comparison of elements in array takes O(n), is it possible to sort the array in O(n) when it has elements starting from 1 to n?

We need to create an algorithm like that but don't know if it's even possible. I could think of one in O(n^2). I'm not asking for the algorithm, will take my time to create one but need to know if it's possible at all.

Upvotes: 2

Views: 284

Answers (3)

rcgldr
rcgldr

Reputation: 28911

It's not clear what is meant by "comparison of elements in array takes O(n)". If the size of an array is "s", then the number of possible comparisons is s things taken 2 at a time.

The sorts that can be performed in O(s) time don't compare elements, usually they count them or they use element values as indices.

This could possibly be a trick question, since the number of elements is not specified. Let s = size of array, then a counting sort could sort the array in O(s) time (not O(n) time).

Upvotes: 0

Guy haimovitz
Guy haimovitz

Reputation: 1625

Yes "Bucket sort": declare array of size n call it arr, set it to zeroes,

2.for each value in the given input array:

  add one in arr in the index that is equal to the value

declare new array out: declare int k =0

3.for i in input array

if arr[inputarray[i]>0 do:

    1.out[k]= arr[i]
    2.arr[inputarray[i] = arr[inputarray[i] -1
    3. k=k+1

return out

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477160

It is definitely possible to do so, you simply create an array with counters and count the number of times element i occurs, since the elements range from 1 to n, you know this counter has length n.

Next there is the generate step, where you simply generate ki elements i if you have encountered ki such elements.

Example code in Java:

int[] data = {5,1,2,4,5,1,2,3};

//assuming data contains only values from 1 to n (included) with n the length
public static int[] sort_int_limited (int[] data) {
    int n = data.length;
    int[] counters = new int[data.length];

    //counter phase
    for(int i = 0; i < n; i++) {
        counters[data[i]-1]++;
    }

    //generate phase
    int k = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < counters[i]; j++) {
            data[k++] = i+1;
        }
    }

    return data;
}

jDoodle demo

As @Aivaen says in his/her comment, this algorithm is called counting sort.

Upvotes: 2

Related Questions