0
$\begingroup$

Given that array has $k$ elements (all distributed uniformly).
Its length is exactly $3$ somewhere in $[0, k)$.

For example, if $k=100$ then, we have $100$ numbers and they can be in $[10,13)$, but they can also be at $[89,92)$

I need to offer a sorting algorithm, which is efficient.

Now, my idea was Bucket Sort, but why would I care the length of the interval is $3$ or $1000$ ? if the numbers are distributed uniformly, then it does not even matter because we could do just a "regular" bucket sort!

But there is a solution that instead of linked lists in each bucket, we use AVL trees. Why would that matter?! the elements still distributed so it is $O(1)$ in each AVL-Tree AND $O(1)$ in each linkedlist... I really don't get it!

Thanks for helping!

$\endgroup$
1

2 Answers 2

1
$\begingroup$

You can use a counting sort: if the first element of the array is $n$, then the values of the array are between $n-2$ and $n+2$. If you count the number of elements equal to each of these 5 values and reorder them, your data are sorted.

This can be done because numbers are in an interval of length 3, so you only have 5 different values to consider given the first one.

$\endgroup$
0
$\begingroup$

You don't need any fancy data structures at all, using counting sort.

Initialize three-element array $C$ to all $0$s and $x$ to infinity. Then loop over every element in $A[i]$ and:

  1. Increment $C[A[i] \bmod 3]$.
  2. If $A[i] < x$ set $x = A[i]$.

Finally, output an array consisting of $x$ repeated $C[x \bmod 3]$ times, followed by $x + 1$ repeated $C[(x+1)\bmod 3]$ times and finally $x + 2$ repeated $C[(x+2)\bmod 3]$ times.

$\endgroup$
2
  • $\begingroup$ But, why is the solution I wrote, your soution and Nathaniel's are the most optimized? I mean, one of them is the most efficient no? So how would I know how to answer here? In a simple analysis all three seem $O(n)$ which is really the same (both runtime and space I believe) $\endgroup$
    – CSch of x
    Feb 21, 2021 at 4:08
  • $\begingroup$ (Excruciatingly data space conscious;) $\endgroup$
    – greybeard
    Feb 21, 2021 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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