16
$\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$
5
  • 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$
    – user694818
    Commented Jan 11, 2020 at 11:27
  • $\begingroup$ @Matthew Daly that’s the diagram I created too. $\endgroup$ Commented Jan 11, 2020 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$ Commented Jan 11, 2020 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$ Commented Jan 11, 2020 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$ Commented Jan 11, 2020 at 22:49

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .