15
$\begingroup$

I’ve just been playing around with some numbers and stumbled across this sorting algorithm: Take a set of integers $\{2,2,5,1,1\}$. Count how many numbers you can subtract 1 from (without going negative) - (5)

Same for subtracting 2 - (3)

Same for subtracting 3 - (1)

Same for subtracting 4 - (1)

Finally for subtracting 5 - (1)

This creates a new ordered set $\{5,3,1,1,1\}$ Perform the exact same algorithm with this new set of numbers and it will produce $\{5,2,2,1,1\}$ which is the original set in descending order.

I’m fairly confident the time complexity is $O(n^2)$ (for inputs that are integers smaller than the set size). I can draw a diagram confirming that it works too. Just wondering if it already has a name? Thanks in advance

$\endgroup$
  • 3
    $\begingroup$ In a broader sense, this is reminiscent of inverting a Ferrer's diagram, to give at least something to Google on. But I've never heard of sorting based on inverting the diagram twice. Fun idea! $\endgroup$ – Matthew Daly Jan 11 at 11:27
  • $\begingroup$ @Matthew Daly that’s the diagram I created too. $\endgroup$ – Ben Crossley Jan 11 at 11:31
  • 1
    $\begingroup$ The first step looks like the Layer Cake Representation. It also looks like you’re taking the conjugate Ferrer’s diagram in the second step. I don’t know a name for this algorithm, however. $\endgroup$ – Michael Burr Jan 11 at 11:48
  • 1
    $\begingroup$ You can go from the second list to the final list in O(n) time, using the fact that the second list is already in descending order. $\endgroup$ – Alex Meiburg Jan 11 at 20:05
  • 1
    $\begingroup$ So, my guess is, when there lots of repeating small inputs is really fast. Which makes it quite cool +1 $\endgroup$ – miraunpajaro Jan 11 at 22:49
3
$\begingroup$

This algorithm is essentially counting sort

https://en.m.wikipedia.org/wiki/Counting_sort?fbclid=IwAR1XKmg3EuxUBqJOfTm4HTo8YuOXgP_ZDHy6qIBDR_4cTUqr70DTeT9wiRw

This algorithm can be computed in a single step when there is a diagonal symmetry in the Ferrer diagram

E.g permutations of 5,3,2,1,1

Or permutations of 4,3,2,1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.