Timeline for sort array with some of the elements in a known range
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2021 at 6:48 | answer | added | ErroR | timeline score: 0 | |
| May 17, 2021 at 4:52 | comment | added | D.W.♦ | cs.stackexchange.com/q/140046/755, cs.stackexchange.com/q/140385/755 | |
| May 14, 2021 at 0:12 | history | edited | John L. | CC BY-SA 4.0 |
Removed the answer from the question.
|
| May 6, 2021 at 14:49 | vote | accept | CforLinux | ||
| May 6, 2021 at 3:17 | comment | added | Evil | You can post your solution as answer and it is fine to do so, but editing question to provide solution yields dangling question, that is not good way to go at SE. | |
| May 4, 2021 at 21:11 | answer | added | CforLinux | timeline score: 0 | |
| May 4, 2021 at 17:36 | review | Close votes | |||
| May 14, 2021 at 0:12 | |||||
| May 4, 2021 at 17:17 | comment | added | Yuval Filmus | I’m voting to close this question because OP solved it on their own. | |
| May 4, 2021 at 15:19 | history | edited | CforLinux | CC BY-SA 4.0 |
possible solution
|
| May 4, 2021 at 14:38 | comment | added | jjohn | Yes, you are absolutely right! | |
| May 4, 2021 at 14:06 | comment | added | CforLinux | @jjohn but if each bucket have $k_i$ elements and subrange of $\sqrt n$ elements then the count of sort of each bucket is done in $O(k_i + \sqrt n)$ there are n - 1 buckets so $\sum_{i=1}^{n - 1} O(k_i + \sqrt n) = \sum_{i=1}^{n - 1} O(k_i) + O(n\sqrt n)$ | |
| May 4, 2021 at 13:43 | comment | added | jjohn | One thing that can work is to split the second parition into buckets such that bucket $B_i$ contains element between $i*\sqrt{n}$ and $(i+1)*\sqrt{n}$. Then you should be able to use counting sort in each bucket for an overall $O(n -\sqrt{n})$ cost by summing the individual sorting costs. P.S for efficient space to be in $O(n)$ and not $O(n\sqrt{n})$ you can note that each bucket has $\sqrt{n}$ different values you can simply 'renumber them' to be from $0,\ldots,\sqrt{n}-1$. | |
| May 4, 2021 at 12:21 | history | asked | CforLinux | CC BY-SA 4.0 |