0
$\begingroup$

I have this first task:
You have a set of numbers $S =\{ \dots \}$ of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 < k < n$

Your task is to write an algorithm (pseudo-code) that splits $S$ into $k$ sets (which have the same length each): $S_1 , S_2 , \dots, S_k$ such that all the numbers in $S_i$ are smaller than all the numbers in $S_{i+1}$ for all $1 \leq i \leq k-1$ in time complexity of $O(n \cdot k)$ (end of task 1)

The second (another question, but related to the first one) task is the same, but suggesting a faster algorithm - psuedo-code (time complexity -wise)

For example:

For $S = \{11,5,2,7,1,13,15,16 \}$ and $k = 4$ I would return (right to left):
$\{16, 15 \} , \{13, 11 \} , \{5, 7 \} , \{1, 2\}$
notice the order of the numbers inside these sets does not have to be in any particular order.

My go:
What have I not tried.. god:

  1. I thought of doing a bucket sort.

  2. Maybe choose a random pivot and do a select for each group.

  3. Make $k$ empty sets of length $\frac{n}{k}$ each ("in advance") and then choose the $k$-th smaller elements each iteration.

  4. make $k$ empty sets of length $\frac{n}{k}$ "in advance" and then putting each number in the first one, and once we come across a bigger number we move the smallest of them to the next set like this for the example above (explicit details below):

This is the algorithm I have so far (number 4):

First we have an empty $k=4$ sets of length $\frac{n}{k} = \frac{8}{4} = 2$ and then comes $11$, then $5$ :
$\{11 , 5 \}, \{ , \}, \{ , \}, \{ , \}$ and then $2$ comes but it's smaller than $5$ or $11$ so $\{11 , 5 \}, \{2 , \}, \{ , \}, \{ , \}$ then comes $7$ and it is larger than $5$ so it replaces it and moves the $5$ to the next set:
$\{11 , 7 \}, \{2 , 5\}, \{ , \}, \{ , \}$ etc...

it should work but I am not sure what is the running complexity. For each set ($k$ times) I have to run $\frac{n}{k}$ iterations (the length of each subset)

Nothing works if I understand it correctly. Nothing here gives me time complexity of $O(n \cdot k)$ ...
I did not even start thinking about the second solution.. because I can't get pass the first one..

I would appreciate your help!

$\endgroup$
1
$\begingroup$

Your second idea seems to be close. Here is the actual algorithm (no random pivot is required):

  1. Find the $i{n\over k}$'th order statistic for every $1\le i\le k$. This will take $O(n)$ each time for $k$ values: $O(nk)$.
  2. For every such $i$, put all elements with values between the $i{n\over k}$'th and the $(i+1){n\over k}$'th order statistics in the $i$'th bucket. For each $i$ it would cost $O(n)$ and there are $k$ different values for $i$, thus total of $O(nk)$.

Both steps take $O(nk)$ and therefore the entire algorithm runs in $O(nk)$ as required

Hint for the second question: think how you can combine this algorithm with a coarse version of quicksort

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ My second idea has nothing to do with buckets... what are these buckets your algorithm talks about can you please elaborate? $\endgroup$ – StackOMeow Jun 25 at 12:21
  • $\begingroup$ The sets you want to split the numbers to, as in the question $\endgroup$ – nir shahar Jun 25 at 12:24
  • $\begingroup$ Hey, I think I finished the first solution, but could not find any ideas for the second solution.. what I have so far for the second: find the median using select in O(n) (selection problem - order statistic) and then do a quicksort choosing the pivot to be the median. what do you think? if that is not what you meant, can you please elaborate on the second solution? thank you so much $\endgroup$ – StackOMeow Jun 25 at 13:38
  • $\begingroup$ Yes, find the median and split the big set $S$ into two smaller sets $S_1$, $S_2$ (just like with the pivot in the quicksort). Now recursively run the algorithm on each set (with a new $k$ value) $\endgroup$ – nir shahar Jun 25 at 18:12
  • $\begingroup$ Toda raba! ;) thank you! $\endgroup$ – StackOMeow Jun 25 at 23:02

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.