3 ms·
From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
by N3XT 7y ago
From the article:
"These operations do require doubling the memory overhead for the swap space."
It seems it is not in-place.
- metalliqaz 7y agoI'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
- davrosthedalek 7y agoYou technically do not need any swap space to swap two numbers. So algorithms which only use swaps could be implemented fully in place.
- utopcell 7y agowhile you can indeed swap in-place for PODs [1], this is not true for c++ objects. Also, in-place swapping is not sufficient for in-place sorting. [1] example: int a, b; a ^= b ^= a ^= b;
- cwzwarich 7y agoThe term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.
- deleted 7y ago[deleted]
- gpderetta 7y agotechnically quick sort needs O(log N) additional space and it is still considered in-place. I guess the threshold for in-place-ness would be less than linear additional space?
- utopcell 7y agoquicksort is not stable. the disadvantage of classic mergesort is that it needs to copy elements out of the input array, although there exist (slower) in-place variations.
- tedunangst 7y agoIn place kinda means the opposite of in swap space.
- Dylan16807 7y agoBut "swap space" without the "in" is pretty ambiguous. If it just holds 1 or 4 elements as you perform a single logical swap, you're still sorting in-place. (This sort does not use the term that way, but another sort could.)
- ummonk 7y agoIt looks like it is doubling the "swap space" used in a standard merge sort, not the "swap space" use in a quicksort.
- dpbriggs 7y agoSwap space is allocated here: https://github.com/scandum/quadsort/blob/c3bcf139c59eb296b28c94f6f72ec9b4d466cc78/quadsort.c#L764 https://github.com/scandum/quadsort/blob/c3bcf139c59eb296b28...
- ummonk 7y agoOkay, that looks like it is proportional to the size of the array, so definitely not in-place.