3 ms·
Swap with the element at the end of the list, not append, and move the swap point one position back each time. Otherwise why would I say you would need to read
by Arnavion 11y ago
Swap with the element at the end of the list, not append, and move the swap point one position back each time. Otherwise why would I say you would need to read them in reverse order?
- Ono-Sendai 11y agoI don't think that works. What if both the element to move, and the element at the end of the list, belong to the right of the partition?
- deleted 11y ago[deleted]
- dpark 11y agoI think that's what he's trying to address when he refers to moving the swap point. This is a standard algorithm (e.g. http://www.cplusplus.com/reference/algorithm/partition/ http://www.cplusplus.com/reference/algorithm/partition/), but it's not stable, which means it doesn't meet your requirements. Stable partition with constant storage is harder. I'm pretty sure it's not possible, but I'm not prepared to offer a proof of that. I believe it (at best) turns into NlgN moves (which is how stable_partition performs as well) no matter what exact approach you take.