Name for sorting algorithm "while not sorted, swap the FIRST unordered pair"

Question

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.

Answer 1

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-sort_opt, bozo-sort_opt, 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.