51–60 of 110 posts
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.
This Quicksort is almost twice as fast https://rextester.com/XHCGA23293
This reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a program that sorts an array of N elements optimally: the generated code has N! branches, one for each possible permutation. With some CSE help from the compiler, it can be really quite fast at the expense of code size. The author's explanation isn't entirely clea…
For five elements the lower bound from counting the permutations is ceil(log2(5!)) which says you cannot sort 5 elements in less than 7 comparisons.
An actual 7 comparison algorithm exists but it is not very easy to write it. For greater numbers it gets much much trickier - in general the log(#permutations) lower bound cannot be met.
I’ll read the article when I get the chance, but would this be in-place?
Earlier quoted context omitted.
Only in the random case. Already sorted in either direction and it's ~10x slower.
Who wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.
Earlier quoted context omitted.
Only in the random case. Already sorted in either direction and it's ~10x slower.
Who wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.
This reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a program that sorts an array of N elements optimally: the generated code has N! branches, one for each possible permutation. With some CSE help from the compiler, it can be really quite fast at the expense of code size. The author's explanation isn't entirely clea…
A truly optimal sorting for a given N is a nontrivial problem. By truly optimal I mean the actual absolute minimum in the number of comparisons, no O(...) approximation. For five elements the lower bound from counting the permutations is ceil(log2(5!)) which says you cannot sort 5 elements in less than 7 comparisons. An actual 7 comparison algorithm exists but it is not very easy to write it. For greater numbers it g…
Earlier quoted context omitted.
I'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
The term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.