21–30 of 110 posts
I’ll read the article when I get the chance, but would this be in-place?
From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
qsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort
Earlier quoted context omitted.
From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
I'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
Man, that's a good gif
There are several similar videos on YouTube demonstrating sorts. If that's a bit sterile for you, you can get a more human touch via the playlist https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7...
Earlier quoted context omitted.
From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
I'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
Earlier quoted context omitted.
> I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested The search space is infinite, so exhaustively exploring it is impossible.
Nit: it's possible that there is a finite number of Pareto optimal sorting algorithms, and it may be possible to enumerate those.
Procedures that enumerate Turing machines are generally very easy, or nigh impossible
Earlier quoted context omitted.
From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
I'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
I’ll read the article when I get the chance, but would this be in-place?
From the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
Man, that's a good gif
You may enjoy this: https://www.youtube.com/watch?v=kPRA0W1kECg There are several similar videos on YouTube demonstrating sorts. If that's a bit sterile for you, you can get a more human touch via the playlist https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7...
Interesting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested.
It isn't. Sorting networks ( https://en.wikipedia.org/wiki/Sorting_network ) provide the best possible in-place sorting combinations for N elements, where N is currently At lazy glance, it looks kind of like Quadsort has re-derived a variation of the 4-element sorting network.
In section 2 in that Wikipedia article, it links to many constructions that do exactly that.
A couple are O(n log(n)), but complicated and impractical. The algorithms people use are O(n log^2(n)) ones.
FWIW, sorting networks are data-independent. I.e. for any input, you always compare-and-swap the same elements.