How is this obscure sorting algorithm called

Question

I came up with an obscure sorting algorithm and given that it's so simple, it must have been invented and named before, so I was wondering what it's called.

It has a very rare constraint: It only works for inputs that have keys from 0 to n-1 (or equivalent). That's a very strong constraint that makes it useless in practice, but maybe one can construct some artificial settings in which it's useful. The algorithm basically swaps the element at a particular position with its final position until the array is sorted. Pseudocode:

def obscure_sort(array):
  sorted_until = 1
  while true
    if key(array[0]) != 0:
      # Swap the element at position 0 to its final position.
      swap(array, 0, key(array[0]))
    else:
      # Find the next element that isn't in its final position.
      while key(array[sorted_until]) == sorted_until:
        sorted_until++
        # If we happen to reach the end, we're done.
        if sorted_until == array.length:
          return
      # Swap the newfound first unsorted element to position 0
      swap(array, 0, sorted_until)

The algorithm actually runs in O(n). It's not completely trivial to see that and I'll leave out the analysis unless someone is really interested.

Does anyone know if this has a name?

I can see the similarity, but I don't really like this as the solution. Bucket sort isn't in place and doesn't have this part of looking for a new unsorted element. — Lykos
– Lykos, Commented Oct 27, 2021 at 21:17
The code is reminiscent of a cycle detection algorithm. Cycle detection uses two nested loops, where the outer loop finds the next unvisited element (i.e. an element not in its proper place), and the inner loop follows the cycle. — user3386109
– user3386109, Commented Oct 28, 2021 at 0:35
I think that makes sense. The accepted answer is also making use of that. — Lykos
– Lykos, Commented Nov 2, 2021 at 8:33

kcsquared · Accepted Answer · 2021-10-28 01:03:19Z

5

This is a slight variation of a restricted cycle sort, probably closest to the algorithm from section 3 of this paper.

Normally with cycle sort on the keys A = [0, 1,...(A.length-1)], you would loop through the array testing indices 0 to A.length-1 as a 'cycle start', looking for cycles to rotate. One 'rotation' is done by always holding a temporary variable 'temp' (initially our cycle start), and doing a swap(temp, A[temp]) until we are back at the start of the cycle (i.e., when temp == A[temp]).

Here, in contrast, we add 0 at the back of the cycle, and 'A[0]' takes the place of 'temp'. We use the operation swap(A[0], A[A[0]]), so that in general, an element x that's moved takes a journey of A[old] -> A[0] -> A[x] rather than A[temp] -> temp -> A[x].

In the linear time algorithm described in the paper above, upon starting loop iteration i, all of the elements 0, 1, ..., i-1 are in place and never moved again. This algorithm is similar, except that if it were written with the same loop style, 0, 1, ..., i-1 are also in place at the start of iteration i but element 0 is not fixed, being moved constantly during an iteration.

As a small example:

Traditional Cycle Sort
Initially, A = [1, 3, 0, 2]

Step 1: A = [1, 3, 0, 2], temp = 1, with cycle_start = 0
Step 2: A = [1, 1, 0, 2], temp = 3
Step 3: A = [1, 1, 0, 3], temp = 2
Step 4: A = [2, 1, 2, 3], temp = 0
Step 5: A = [0, 1, 2, 3], temp = 2; stop since temp == A[temp]

Custom Cycle-like Sort
A = [1, 3, 0, 2]

Step 1: A = [1, 3, 0, 2]
Step 2: A = [3, 1, 0, 2]
Step 3: A = [2, 1, 0, 3]
Step 4: A = [0, 1, 2, 3]

Note that this new sort can take more steps than the normal cycle sort, since 'adding 0 at the back of the cycle' can add an additional swap operation per cycle. The total number of array swaps, though, is linear (and at most twice the array length).

answered Oct 28, 2021 at 1:03

kcsquared

5,4191 gold badge13 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

trincot Over a year ago

Nice and complete answer!

Lykos Over a year ago

Amazing thanks! Yes I am aware that swapping with position 0 to break into a new cycle is not efficient. But in the application where this comes from, the traditional cycle sort isn't really feasible as you can basically only swap position 0 with any other position.

Collectives™ on Stack Overflow

How is this obscure sorting algorithm called

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related