3 ms·
Not sure I understand you algorithm - are you saying to append the items as you see them to the end of the list? Wouldn't that violate the no-additional memory
by AndrewGaspar 11y ago
Not sure I understand you algorithm - are you saying to append the items as you see them to the end of the list? Wouldn't that violate the no-additional memory requirement? That would also add a dependency on using iterators that support growing the underlying data structure without invalidating the existing iterators.
- Arnavion 11y agoSwap 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.