2
$\begingroup$

A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass.

For a toy problem, we have a variant that just performs the first available swap in each iteration and repeats until sorted. It does not continue from the position of the last swap.

Is there a standard name for this sort? It seems so trivial that it must have a name, but we were surprised not to find it on any obvious lists. It's just like, a raw comparison sort.

Bubble

4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
3, 2, 1, 4 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

Variant

4, 3, 2, 1
3, 4, 2, 1
3, 2, 4, 1
2, 3, 4, 1 <- Different
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4

Don't worry, this is not meant to be a good sorting algorithm, just for a fun thing.

$\endgroup$
  • 1
    $\begingroup$ Feel like maybe somebody's gonna say this is close enough to just call a bubble sort? It does produce different intermediate states, though. $\endgroup$ – user115773 Feb 17 at 13:29
  • 1
    $\begingroup$ There are many more ideas than there are standard "names". The great thing about language is that we can describe our ideas even if they don't have a "name". What's the motivation for asking for a "name"? What would you do with an answer? If your goal is to use the "name" to do something, perhaps it would be better to ask how to do that something; then people could help you with that even if there isn't a standard "name". $\endgroup$ – D.W. Feb 17 at 17:19
  • 1
    $\begingroup$ @D.W. Our question was asked competently, all due respect but we don't need the premise questioned. That's one of the more annoying habits of StackExchange sites. This algorithm is being used in a pen-and-paper maths-puzzle, and we're just interested in a name because it might inspire a name for the puzzle, and because we were a little surprised to find that it wasn't in the standard lists of sorting algorithms, despite being essentially the simplest form of comparison sort imaginable. $\endgroup$ – user115773 Feb 18 at 0:48
  • $\begingroup$ My first response was this is a variant of insertion sort, definitely not bubble sort. I neglected to consider the fact that it may sweep repeatedly from the left to find the leftmost inversion, making this an $O(n^3)$ sort. I think you are safe to christen this sort however you like. $\endgroup$ – Daniel M Gessel Feb 20 at 18:13
2
$\begingroup$

In more detail, this variant of bubble sort finds the leftmost pair of adjacent items that are in the wrong order. Then it swaps those two items. This operation of "find and swap" is repeated until the given list is sorted. In other words, this variant of bubble sort swaps the items in the leftmost inversion of the given list repeatedly until the given list is sorted. (Note the two items in the leftmost inversion must be adjacent).

There is no standard or popular name for this variant of bubble sort, or so I believe.

I would call it left-bubble sort, a name that captures its conceptual intention. We could also have right-bubble sort, which swaps the items in the rightmost inversion repeatedly until sorted. We could also have random-bubble sort, which swaps two randomly-selected adjacent items that are in the wrong order repeatedly until sorted. If we do not even require the two items to be adjacent, we can have random-swap sort. Depending on how the inversion is selected randomly, "random-swap sort" can become bogo-sortopt, bozo-sortopt, and bozo-sort+opt that appear in this article.

The above description of left-bubble sort does not specify how to find the leftmost inversion in each iteration. A naive implementation may always comparing the first two items, then the next two items and so on until it finds the first inversion or stops. We can observe that the initial part of the list during the left-bubble sort is sorted. Since there cannot be any inversion in the initial part of the list, we can optimize the implementation by just comparing the item that was just moved to the left with the item right before it without comparing the initial adjacent items.

Whether we use the naive implementation or the optimized implementation above, left-bubble sort behaves exactly the same as the simplest insertion sort, in terms of the states the given list goes through until sorted. The simplest insert sort here corresponds to the first pseudocode at this Wikipedia page, which is implemented in Programming Pearls (2000) by Jon Bentley.

Here is an illustration of the states produced by left-bubble sort.

4, 3, 2, 1    <- 4 is considered inserted into the expected place.
3, 4, 2, 1    <- 3 is inserted into the expected place
3, 2, 4, 1
2, 3, 4, 1    <- 2 is inserted into the expected place
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4    <- 1 is inserted into the expected place

In particular, left-bubble sort builds the final sorted array (or list) one item at a time, which is the defining characteristic of "insertion sort" according to that Wikipedia page. We can thus treat (the optimized version of) left-bubble sort as another name for the simplest insertion sort.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Appreciate the effort, but don't really feel that this is a correct answer. The relation to insertion sort is interesting (though we already knew it) but it's still a variant, so doesn't really get us any closer than bubble sort. The algorithm specifically needs to be defined in terms of swaps, and insertion sort is not. $\endgroup$ – user115773 Feb 18 at 1:03
  • $\begingroup$ It may well be that it just doesn't have a name. That just seems a little surprising given that "while the list is not sorted, swap the first unordered pair" is essentially the simplest comparison sort imaginable. You'd think that would have a name, even if it's just "naive sort" or something. It seems odd that bubble-variants like cocktail have a name, but nobody has ever named this. $\endgroup$ – user115773 Feb 18 at 1:10
  • 1
    $\begingroup$ Please take a look at the pseudocode for the insertion sort at Wikipedia. It is also defined in terms of swap. $\endgroup$ – John L. Feb 18 at 2:42
  • 1
    $\begingroup$ Hmm, we''ll give it to you because you make a good case from the equivalence, although it's not particularly useful for us as insertion sort conceptually describes a different way of understanding the process. We really wanted something that communicates the swap-the-first-one idea of the algorithm. It seems like the name we're looking for just doesn't exist, so your answer is as close as we'll get. $\endgroup$ – user115773 Feb 18 at 3:00
  • 1
    $\begingroup$ I would agree that pseudocode for insertion sort can be called the slow insertion sort. $\endgroup$ – John L. Feb 18 at 3:15

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.