Timeline for What is the fastest way to sort numbers lexicographically?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 2, 2015 at 16:46 | comment | added | Userbejian29 | It is not from a programming competition. I am solving problems from SPOJ, UVA, CodeForces etc. and recently I've been doing task that required fast algorithm for comparing sequences lexicographically. Solution with quicksort was fast enough, because data wasn't big, but I wondered if there exist algorithm that could do it faster. | |
| Nov 2, 2015 at 16:05 | comment | added | Douglas Zare | @Adam P. Goucher: It does look like it might be too easy, but there are a lot of programming competitions which start with trivial problems and then include tougher questions. In addition, there are usually tests that are of a size so that poor algorithms will time out, and it sounds like that happened. This user has posted other harder problems with the same style. It could be homework instead, though. | |
| Nov 2, 2015 at 15:51 | comment | added | Adam P. Goucher | @DouglasZare It seems far too basic for that to be the case. | |
| Nov 2, 2015 at 15:12 | comment | added | Douglas Zare | This looks like it is from a programming competition. | |
| S Nov 2, 2015 at 13:35 | history | suggested | CommunityBot |
Added tag. Admittedly, ot ideal.
|
|
| Nov 2, 2015 at 13:09 | review | Suggested edits | |||
| S Nov 2, 2015 at 13:35 | |||||
| Nov 2, 2015 at 11:22 | vote | accept | Userbejian29 | ||
| Nov 2, 2015 at 10:11 | answer | added | Adam P. Goucher | timeline score: 1 | |
| Nov 2, 2015 at 9:56 | comment | added | user13113 | @Brendan: And even if they aren't, you could still effect a radix sort by using a comparison-based sorting routine on each digit rather than a bucket sort. | |
| Nov 2, 2015 at 9:26 | comment | added | Brendan McKay | Are all the integers quite small? If so, a version of radix sort for mixed-length strings will take time proportional to the total length of the strings. | |
| Nov 2, 2015 at 9:20 | comment | added | Stefan Kohl♦ | Does it happen often that long initial sequences of two of your sequences are equal? | |
| Nov 2, 2015 at 8:49 | comment | added | Wojowu | Since you are assuming that $K\leq 10^6$, you don't need to include it in the big O. | |
| Nov 2, 2015 at 8:47 | comment | added | Userbejian29 | It is the length of the longest sequence. In example above K = 3, because length of the longest sequence is 3. | |
| Nov 2, 2015 at 8:33 | review | First posts | |||
| Nov 2, 2015 at 9:20 | |||||
| Nov 2, 2015 at 8:32 | comment | added | Wojowu | What is $K$ in your big O? | |
| Nov 2, 2015 at 8:26 | history | asked | Userbejian29 | CC BY-SA 3.0 |