How long to carry sort?

Question

Carry sort is an \$O(n)\$ "sorting" algorithm. Here's how it works. The algorithm moves left to right along a list. As it traverses a list it "carries" a single item, the largest item it has encountered so far. Once it encounters a larger item it picks up that item and drops the item it is already carrying in place. When it gets to the end it drops the item that it is carrying (the largest item in the list) at the end of the list.

Worked example

Here we are going to apply carry sort to the list [1,2,0,3,2,1,2,4,3]

[1,2,0,3,2,1,2,4,3]
^
[ 2,0,3,2,1,2,4,3]
 ^
 1
[ 1,0,3,2,1,2,4,3]
 ^
 2
[ 1,0,3,2,1,2,4,3]
 ^
 2
[ 1,0,2,2,1,2,4,3]
 ^
 3
[ 1,0,2,2,1,2,4,3]
 ^
 3
[ 1,0,2,2,1,2,4,3]
 ^
 3
[ 1,0,2,2,1,2,4,3]
 ^
 3
[ 1,0,2,2,1,2,3,3]
 ^
 4
[ 1,0,2,2,1,2,3,3]
 ^
 4
[ 1,0,2,2,1,2,3,3,4]
 ^

Here we can see that carry sort has definitely made the list more sorted than it was, but it's not perfectly sorted.

Task

If you repeatedly apply carry sort to a list it will eventually sort the list. Your task is to take a list of integers and determine the minimum number of passes required for carry sort to sort the input list in ascending order.

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

[] -> 0
[-2,3,9] -> 0
[4,1,2,3] -> 1
[1,3,2,4] -> 1
[4,3,2,1] -> 3
[0,-1,-2,-3,-4] -> 4
[1,2,0,3,2,1,2,4,3] -> 3

• Bbrk24: So carry sort is a single pass through bubble sort's loop?
• Wheat Wizard: @Bbrk24 Bubble sort IME is not a terribly specific term, so I avoided it in the question body, but I would call this a bubble sort.
• Neil: Grade up, if you have that builtin, will do a lot of the heavy lifting here.

Answer 1

R, (削除) 41 (削除ここまで) (削除) 40 (削除ここまで) 35 bytes

Edit: -1 byte thanks to @Giuseppe and -5 bytes thanks to @Dominic van Essen.

\(x)max(order(y<-c(x,Inf))-seq(!y))

Attempt This Online!

The idea is that we look how much to the right are the elements displaced in the input versus the sorted array, and take the maximum. This is because moving elements to the right is easy and to the left is hard (moving one space to the left requires exactly one pass).

Example:

x = 1 2 0 3 2 1 2 4 3
sort(x) = 0 1 1 2 2 2 3 3 4
order(x) = 3 1 6 2 5 7 4 9 8 # positions of the input in the sorted array (sort(x) === x[order(x)])
order(x)-seq(x) = 2 -1 3 -2 0 1 -3 1 -1 # how far to the right is input vs sorted
take max -> answer

• Dominic van Essen: This is beautiful, but I think you need seq(!x) to avoid problems with single-element lists with a negative value...?
• Dominic van Essen: (or \(x)`if`(a<-sum(x|1),max(order(x)-1:a),0)...?)
• pajonk: @DominicvanEssen thanks, I didn't think of one-element negative inputs.
• Giuseppe: \(x)'if'(any(x),max(order(x)-seq(!x)),0) for 40 bytes. If the list is empty or contains all zeros (falsey), it's already sorted.
• Dominic van Essen: 35 bytes?

Answer 2

JavaScript (ES6), 50 bytes

This is inspired by @pajonk's excellent answer. But instead of explicitly sorting the input array, we subtract from the position of each element the number of elements that are less than or equal to it.

a=>a.map(m=(v,i)=>a.map(V=>i-=V<=v)|m>++i?0:m=i)|m

Try it online!

Commented

a => // a[] = input array
a.map(m = // initialize m to a non-numeric value
(v, i) => // for each value v at position i in a[]:
 a.map(V => // for each value V in a[]:
 i -= // decrement i if
 V <= v // V is less than or equal to v
 ) | // end of inner map()
 m > ++i ? // increment i; if m is greater than i:
 0 // do nothing
 : // else:
 m = i // update m to i
) | m // end of outer map(); return m

---

JavaScript (ES6), 66 bytes

-1 if we return false for 0.

f=A=>([m,...a]=[...A,,],a=a.map(v=>v<m?v:m+![m=v]))==A+''?0:1+f(a)

Try it online!

Commented

f = A => // recursive function taking the input array A[]
( // split into:
 [ m, // m = first element
 ...a ] = // a[] = all remaining elements
 // the array defined as:
 [ ...A,, ], // A[] padded with a trailing undefined value
 a = a.map(v => // for each element v in a[]:
 v < m ? // if v is less than m:
 v // leave v unchanged
 : // else:
 m + ![m = v] // put m here and update m to v
 ) // end of map(); save the result in a[]
) == A + '' ? // if a[] is equal to A[]:
 0 // stop
: // else:
 1 + // increment the final result and do
 f(a) // a recursive call with the updated array

Answer 3

Charcoal, (削除) 53 (削除ここまで) (削除) 33 (削除ここまで) 31 bytes

≔⟦⟧ηW−θυ«⊞υ⌊ιF⌕Aθ⌊ι⊞η−κLη»I∨⌈η0

Try it online! Link is to verbose version of code. Explanation: Having written my comment, I finally got around to implementing a version using grade up.

≔⟦⟧η

Start with an empty list.

W−θυ«

Repeat until the list has been graded.

⊞υ⌊ι

Track the elements already graded.

F⌕Aθ⌊ι⊞η−κLη

Save the offsets of each matching element in the list.

»I∨⌈η0

Output the maximum, or 0 if the list was empty.

Answer 4

Excel (ms365), 137 bytes

Within the windows version one can create their own named function using the named manager. Here we will create a function named 'Z':

=LAMBDA(a,b,IF(AND(a=SORT(a)),b,Z(DROP(REDUCE({0;0},a,LAMBDA(c,d,LET(y,TAKE(c,-1),IF(d>y,VSTACK(c,d),VSTACK(DROP(c,-1),d,y))))),2),b+1)))

Now you can call 'Z' using:

=Z(<YourVerticalRange>,0)

For example:

enter image description here

---

If one would like to try this online, I tried to mimic this using Google Sheets:

=LAMBDA(a,b,IF(INDEX(AND(a=SORT(a))),b,Z(QUERY(REDUCE({0;0},a,LAMBDA(c,d,LET(y,INDEX(c,COUNT(c)),IF(d>y,VSTACK(c,d),VSTACK(QUERY(c,"limit "&COUNT(c)-1),d,y))))),"offset 2"),b+1)))(a,b)

enter image description here

Answer 5

Vyxal, 25 bytes

{:ÞṠ¬|÷^!(~<ß$‟)„$‟^W&›}\

Try it Online!

Count how many times the sweep is applied until it's sorted.

• The Thonnu: Get outgolfed lol :p
• lyxal: @TheThonnu you say that like it's something that doesn't happen on days that end in y :p

Answer 6

05AB1E, (削除) 19 (削除ここまで) 15 bytes

ΔZaćUεDX›iXsU]N

-4 bytes porting @Arnauld's JavaScript answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Original 19 bytes answer:

Δā<ü2vDyè©`›i®yRǝ]N

Try it online or verify all test cases.

Explanation:

Δ # Loop until the result no longer changes (aka, until it's sorted),
 # using the (implicit) input-list
 Z # Push the maximum of the list (without popping)
 a # Append this maximum to the list
 ć # Extract head; pop and push remainder-list and first item
 # separately to the stack
 U # Pop and store this first item in variable `X`
 ε # Map over the remainder-list:
 D # Duplicate the current integer
 X›i # Pop the copy, and if it's larger than `X`:
 X # Push `X`
 sU # Swap, pop, and store the current integer as new `X`
 # (implicit else: keep the current integer, hence the need for the
 # `D`uplicate before the if-statement)
] # Close the if-statement; map; and changes-loop
 N # Push the final (0-based) index of the changes-loop
 # (which is output implicitly as result)

Δ ]N # Same as above:
 ā # Push a list in the range [1,length] (without popping)
 < # Decrease it to 0-based range [0,length)
 ü2 # Get all overlapping pairs of this index-list
 v # Pop and loop over each index-pair `y`:
 Dyè # Get the values at indices `y` in a copy of the current list
 © # Store this pair of values in variable `®` (without popping)
 `›i # Pop the pair, and if the first is larger than the second:
 ®yRǝ # Swap the values at the index-pair `y` within the list:
 ® # Push values-pair `®`
 yR # Push the reversed of index-pair `y`
 ǝ # Insert the values at those reversed indices to the list

• Neil: Wouldn't ZªćU solve the potential problem with ćUZª?
• Kevin Cruijssen: @Neil You're completely right indeed, thanks. Can't believe I've overlooked that..

Answer 7

R, (削除) 90 (削除ここまで) 82 bytes

Edit: -8 bytes thanks to Giuseppe

f=\(l)`if`(is.unsorted(l),{l[c(F,d,T)]=l[c(T,d<-diff(cummax(l))>0)];f(l[-1])+1},0)

Attempt This Online!

Recursively performs carry-sort and counts how many times it's needed until the argument is sorted.

Take a look at pajonk's much more elegant and shorter approach that simply calculates the right answer directly, though...

Answer 8

Python + numpy, (削除) 67 (削除ここまで) 65 bytes

Edit: -2 bytes thanks to @ovs.

lambda x:len(x)and max(argsort(x)-r_[:len(x)])
from numpy import*

Attempt This Online!

Port of my R answer.

• ovs: Making some more use of numpy, range(len(x)) can be r_[:len(x)]

Answer 9

Ruby, (削除) 47 ... (削除ここまで) 41 bytes

->l{l.map{*l,c=l;l.count{|a|a>c}}.max||0}

Try it online!

• ovs: Something is off here, the third case on your TIO link produces the wrong output. And you need to count the f= as this is recursive.
• G B: @ovs Is fixed now

Answer 10

BQN, 7 bytes^SBCS

Another port of pajonks R answer.

0⌈ ́⍋-⊒ ̃

Run online!

Answer 11

Vyxal G, (削除) 9 7 (削除ここまで) 6 bytes

⇧$ẏ-0J

Try it Online! or verify all test cases

Port of @pajonk's R answer

-2 thanks to @Neil

Explanation

⇧$ẏ-0J # Implicit input
⇧ # Grade up: push the indices which will sort the list
 $ẏ # Swap and push a list in the range [0, len(input))
 - # Subtract the range from the grade up list
 0J # Append a 0 to this list
 # G flag gets the maximum
 # Implicit output

Old:

[⇧›$ż-G|0 # Implicit input
[ # If it isn't empty:
 ⇧ # Grade up: push the indices which will sort the list
 › # Increment it to make it one-indexed
 $ż # Swap and push a list in the range [1, len(input)]
 - # Subtract the range from the grade up list
 G # Pop and push the maximum item
 |0 # Otherwise, push 0
 # Implicit output

• Neil: I think ⇧$ẏ-0JG saves 2 bytes.
• The Thonnu: @Neil thanks. We can use the G flag as well to save another one.

Answer 12

Jelly, 4 bytes

Ụ_JṀ

A monadic Link that accepts the list and yields the number of required passes.

Try it online!

How?

Just as pajonk's R answer, but with automatic 0 as the maximum of an empty list.

Ụ_JṀ - Link: List, A
Ụ - grade-up (A) -> list of 1-indexed indices of the sorted values
 J - range of length (A) -> 1-based indices = [1..length(A)]
 _ - (graded indices) subtract (indices)
 Ṁ - maximum (the maximum of an empty list is 0)

Answer 13

J, 14 bytes

[:>./0,/:-i.@#

Try it online!

Explanation

Same approach as a few answers.

[:>./0,/:-i.@#
 /: grade up input
 - and subtract from each position
 i.@# the corresponding element in the range [0, size)
 0, prepend zero (edge case of empty lists)
[: and then
 >./ take the maximum of that array (which is otherwise -∞ for empty lists)

Answer 14

Factor, 46 bytes

[ arg-sort [ - ] map-index 0 suffix supremum ]

Try it online!

Port of @TheThonnu's Vyxal answer.

• arg-sort Get the indices that would sort the sequence. (aka grade up/inverse permutation)
• [ - ] map-index Subtract each index from its element.
• 0 suffix Append a 0.
• supremum Get the maximum element.

Answer 15

Desmos, (削除) 52 (削除ここまで) 48 bytes

s=[0...x.length]
f(x)=max(sort(s,join(0/0,x))-s)

Try it on Desmos!

One of the only times where 0/0 is useful. Based on pajonk's answer.
-4 bytes thanks to Aiden Chow.

• Aiden Chow: This seems to work for 48 bytes.

Answer 16

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}9 bytes ^SBCS

⌈/0,⍋-⍳∘≢

Try it on APLgolf!

Explanation

⌈/0,⍋-⍳∘≢
 ≢ ⍝ length of the input
 ⍳∘ ⍝ create a range from 1 to the length
 - ⍝ subtract that list from...
 ⍋ ⍝ the input graded up
 0, ⍝ prepend a zero
⌈/ ⍝ get the maximum of the resulting list

Just for reference, this is what the train tree looks like:

 ┌─┴─┐ 
 / ┌─┼───┐ 
┌─┘ 0 , ┌─┼─┐ 
⌈ ⍋ - ∘ 
 ┌┴┐
 ⍳ ≢

Answer 17

Wolfram Language (Mathematica), 66 bytes

---

Golfed version, try it online!

x~Append~∞//Ordering//Max[#-Range@*Length@#/.Thread[Not@#->1]]&;

Ungolfed version

f[x_List] := Module[{y, yOrder, seqY},
 y = Append[x, Infinity];
 yOrder = Ordering[y];
 seqY = Range[Length[yOrder]] /. Thread[Not[yOrder] -> 1];
 Max[yOrder - seqY]
]
(* function testing *)
f[{}]//Print (* -> 0 *)
f[{-10}]//Print (* -> 0 *)
f[{-2, 3, 9}]//Print (* -> 0 *)
f[{4, 1, 2, 3}]//Print (* -> 1 *)
f[{1, 3, 2, 4}]//Print (* -> 1 *)
f[{4, 3, 2, 1}]//Print (* -> 3 *)
f[{0, -1, -2, -3, -4}]//Print (* -> 4 *)
f[{1, 2, 0, 3, 2, 1, 2, 4, 3}]//Print (* -> 3 *)
f[{1, 1, 2, 2, 3, 3, 4, 4}]//Print (* -> 0 *)
f[{4, 4, 3, 3, 2, 2, 1, 1}]//Print (* -> 6 *)