1
$\begingroup$

I have a set of elements $x_1,...,x_N$, they take values $x_i \in \{0,...,N\} $ for all $i \in \{1,...,N\}$; I need to sort them. I think I can do that with complexity $\mathcal{O}(N)$, where I can create a matrix of $N\times N+1$ where the colomns represent the sorted values of the range, i.e., $\{0,1,2,...,N\}$, and the rows are the elements. So my questions are:

Is this correct?

Is there a better way to do that?

What if I changed the values of some of these numbers afterwards (after sorting), but all still comply with the initial rule, can I do better than linear sorting to maintain the order?

$\endgroup$
  • $\begingroup$ Are you saying you have all integers in the range 0..N? Because if so, you can "sort" them in O(1). $\endgroup$ – Turksarama Apr 9 '18 at 1:01
  • $\begingroup$ yes, not unique though. How $\mathcal{O}(1)$, sorry it is not my area, but do not we need at least to go over them and place them in order? $\endgroup$ – MrX Apr 9 '18 at 1:03
  • $\begingroup$ Oh I see now. A matrix would work, but if you care about space efficiency then creating a vector with the count at each index works better. If you don't require fast lookup, then a list of tuples (x, count(x)) is even more space efficient if you have many holes. $\endgroup$ – Turksarama Apr 9 '18 at 1:09
  • $\begingroup$ en.wikipedia.org/wiki/Counting_sort $\endgroup$ – D.W. Apr 9 '18 at 7:09
1
$\begingroup$

Since you have a bound on your set of elements you can radix-sort them.

Formally let consider the following procedure:

    // Read the whole table and store the number of occurrences
    T <- Table[N] // Suppose initialized at 0
    for i = 0 to N do
        T[x[i]] <- T[x[i]]+1
    done
    // Unpack the elements
    c = 0
    for i = 0 to N do
        for j = 0 to T[i]-1 do
            x[c] <- i 
            c <- c+1
        done
    done

The soundness of the algorithm is evident. It's time complexity is in $\mathcal{O}(N)$ and its space complexity in $\mathcal{O}(N)$, estimated in arithmetic complexity (I mean by that the reading and writing complexities for your integers is independent of their bitsize).

The (bit) time complexity is in worst case a $\mathcal{O}(N\log N)$ since you might have to read $N+1$ bit strings of length $\Theta(log(N))$.

Notice that in any case, the algorithm is always linear in the size of its input.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.