Timeline for Modified counting sort algorithm?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2015 at 0:15 | comment | added | Yuval Filmus | See my answer for an improvement. | |
| Nov 24, 2015 at 15:08 | comment | added | greybeard | Given an array $A$, almost sorted with CountingSort, with the only exception that element of $A$ at a known index $j$ was reduced, how do you get $A$ sorted in $O(k)$ time, even with the counts still around? As in: what operations on $A$ take constant time, and how is their count bounded in growth by $O(k)$ with increasing $n$ - whatever $k$ may be? Or: How does knowing the modification index make this an $O(k)$ task? | |
| Nov 24, 2015 at 15:03 | comment | added | Konstantin Yovkov | I don't. The question is "How can I now sort the modified array in O(k)?" | |
| Nov 24, 2015 at 15:00 | comment | added | greybeard | Given an array A, almost sorted with CountingSort, and an index $j$ where an element of A was reduced, how do you get A sorted in $O(k)$ time? | |
| Nov 24, 2015 at 14:47 | review | First posts | |||
| Nov 24, 2015 at 15:21 | |||||
| Nov 24, 2015 at 14:42 | history | answered | Konstantin Yovkov | CC BY-SA 3.0 |