Timeline for Algorithms for sorting under some restrictions
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23, 2023 at 2:57 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 1 character in body
|
| Apr 22, 2023 at 6:02 | comment | added | Varun Vejalla | Shoot sorry about that - I should've included the dependence on the number of lines you scroll originally. | |
| Apr 20, 2023 at 22:07 | history | edited | D.W.♦ | CC BY-SA 4.0 |
added 536 characters in body
|
| Apr 20, 2023 at 18:57 | comment | added | D.W.♦ | @VarunVejalla, this algorithm only does $O(n \log n)$ window moves. If we assume moving the window can be done in $O(1)$ time, that doesn't add to the total running time. If you have some other cost model in mind (e.g., the time to move the window is proportional to the distance you move it), it is important to specify that in the question. | |
| Apr 20, 2023 at 18:22 | comment | added | Varun Vejalla | @D.W. The way you read it is right - sorry for any ambiguity. Why wouldn't it be larger than $O(n\log n)$ (because of the window moves) though? | |
| Apr 20, 2023 at 7:55 | comment | added | D.W.♦ | @Pseudonym, if I understand the problem statement correctly, you can perform a comparison between $L[i]$ and $L[j]$ by looking at $L[i]$ to $L[i]$, copying it into memory, then looking at $L[j]$ to $L[j]$, comparing what is in memory to what you are looking at (the code is allowed to read both values), and then deciding whether to insert what's in memory just before $L[j]$ or just after based on the results of that comparison. | |
| Apr 20, 2023 at 4:11 | comment | added | Pseudonym♦ | Ah, wait, I think I misunderstood the constraint. This part threw me: "given a view of the list $L[i+1]$ to $L[i+k]$". If $k=1$, then the number of useful comparisons you can perform is exactly zero. But this is contradicted by the last part of the question. | |
| Apr 20, 2023 at 0:56 | comment | added | D.W.♦ | @Pseudonym, I don't understand your concern. I did notice that word "contiguous", and my scheme takes that into account. (Incidentally, when $k=1$ it makes no difference.) It sounds like you think there is something wrong with my answer -- might you be able to elaborate on what problem you are seeing? | |
| Apr 19, 2023 at 23:45 | comment | added | Pseudonym♦ | "can only see $k$ contiguous elements at a time" - I think that word "contiguous" might be important. | |
| Apr 19, 2023 at 23:01 | history | answered | D.W.♦ | CC BY-SA 4.0 |