3 ms·
I 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?
by Ono-Sendai 11y ago
I 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.