Timeline for What is the most efficient constant-space sorting algorithm?
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 29, 2016 at 19:39 | comment | added | MaiaVictor | Yup, things got progressively more clear after I asked the question and people kept commenting. | |
| Mar 29, 2016 at 13:07 | comment | added | Steve Jessop | @svrm: yeah, then with unlimited RAM and the ability to copy the tape into RAM and do arbitrary computation on it for free, the algorithm "try everything and apply the best" is optimal in terms of number of moves of the tape. Unlikely to be practical, but that's because in practice the runtime would be squillions of years, not 0 ;-) If it costs N moves to copy a tape of length N into RAM, then naive brute force might not be optimal but it's within N of optimal. But none of this is specific to your problem: many problems when stated this way could be solved "offline" using a bogus algorithm. | |
| Mar 29, 2016 at 12:46 | comment | added | MaiaVictor | No, I mean you can't use additional space for partitioning the elements, @SteveJessop. It was badly phrased. You can alloc memory for additional computation, you can't just magically split, make blocks and merge the elements because those are physical cards not bits. | |
| Mar 29, 2016 at 9:26 | comment | added | Steve Jessop | @svrm: in the question you say, "doesn't allocate any byte other than the size of the array", then in a comment you say, "can alloc the whole array and do heavy computation as 0 cost". Do you mean that we have RAM exactly equal to the size of the tape we're sorting, not a byte more or less? Because if we have somewhat more RAM than tape (I'm not sure how much more, but some polynomial), then a naive approach would be to brute-force it. Try every possible sequence of swaps and moves (up to a bound of whatever bubble sort needs), find the best, then run that on the tape. | |
| Mar 29, 2016 at 0:26 | history | tweeted | twitter.com/StackCompSci/status/714609536544423937 | ||
| Mar 28, 2016 at 21:42 | comment | added | Stack Exchange Broke The Law | How can you sort anything without some kind of comparison instruction? | |
| Mar 28, 2016 at 20:37 | comment | added | Devsman | How could you even swap two elements without an int temp? | |
| Mar 28, 2016 at 20:08 | answer | added | zwol | timeline score: 15 | |
| Mar 28, 2016 at 16:30 | answer | added | Charles | timeline score: 4 | |
| Mar 28, 2016 at 15:29 | comment | added | MaiaVictor | @Darkhogg yep I can just record it once so it stays in sync with the tape on future runs. To be fair now I know what the answer is, just do an insertion of new cards. I'd thus still be interested in an answer without previous knowledge of the cards order. | |
| Mar 28, 2016 at 13:13 | comment | added | Raphael | I don't think there is such an algorithm. Without any extra memory, you'll have no way to store any control state. | |
| Mar 28, 2016 at 13:12 | history | edited | Raphael | edited tags | |
| Mar 28, 2016 at 13:01 | comment | added | Dani | Last question for clarification: Do you have access to the values of the elements of the list without having to move the tape to their position? (worst case scenario, we perform a frst pass to read them, but that takes time too!) | |
| Mar 28, 2016 at 12:49 | comment | added | MaiaVictor | Oh, sure. Of course. You can alloc some additional structures. You can even alloc the whole array and do a lot of really heavy computation and that counts as 0 cost. The only thing you need to minimize is the number of SWAP/MOVEs of the actual physical machine, because it is slow. Bubble sort is the best I could came up with, but I guessed there should be better options. | |
| Mar 28, 2016 at 12:46 | comment | added | Dani | So, when you say that you want an algorithm that doesn't allocate any byte other than the size of the array, I guess you refer only to element storage, right? I can still allocate counters and such? | |
| Mar 28, 2016 at 12:43 | comment | added | MaiaVictor | Not that strange, it is a physical machine which will sort a list of carts glued to a looong tape that is rolled up. The machine can only move the the tape forward or backward, and can only swap neighboring cards, of corse. In the real world you can't teleport around, so, those are the restrictions... | |
| Mar 28, 2016 at 12:41 | comment | added | Dani | Why those strange restrictions ?? | |
| Mar 28, 2016 at 12:33 | answer | added | Sarvottamananda | timeline score: 4 | |
| Mar 28, 2016 at 12:29 | history | edited | MaiaVictor | CC BY-SA 3.0 | added 212 characters in body |
| Mar 28, 2016 at 12:18 | history | asked | MaiaVictor | CC BY-SA 3.0 |