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 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. — Wheat Wizard, Mar 15 at 22:24
Grade up, if you have that builtin, will do a lot of the heavy lifting here. — Neil, Mar 16 at 1:00

pajonk · Accepted Answer · 2023-03-16 19:37:41Z

11

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

edited Mar 16 at 19:37

answered Mar 16 at 11:31

pajonk

15.1k3 gold badges21 silver badges65 bronze badges

\$\begingroup\$ This is beautiful, but I think you need seq(!x) to avoid problems with single-element lists with a negative value...? \$\endgroup\$
– Dominic van Essen
Mar 16 at 11:52
\$\begingroup\$ (or \(x)`if`(a<-sum(x|1),max(order(x)-1:a),0)...?) \$\endgroup\$
– Dominic van Essen
Mar 16 at 11:55
\$\begingroup\$ @DominicvanEssen thanks, I didn't think of one-element negative inputs. \$\endgroup\$
– pajonk
Mar 16 at 12:07
\$\begingroup\$ \(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. \$\endgroup\$
– Giuseppe
Mar 16 at 13:30
1

\$\begingroup\$ 35 bytes? \$\endgroup\$
– Dominic van Essen
Mar 16 at 15:32

| Show 2 more comments

Arnauld · Accepted Answer · 2023-03-18 10:02:38Z

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

Neil · Accepted Answer · 2023-03-16 18:01:28Z

Charcoal, 53 33 31 bytes

≔⟦⟧ηＷ⁻θυ«⊞υ⌊ιＦ⌕Ａθ⌊ι⊞η⁻κＬη»Ｉ∨⌈η⁰

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.

Ｗ⁻θυ«

Repeat until the list has been graded.

⊞υ⌊ι

Track the elements already graded.

Ｆ⌕Ａθ⌊ι⊞η⁻κＬη

Save the offsets of each matching element in the list.

»Ｉ∨⌈η⁰

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

JvdV · Accepted Answer · 2023-03-16 10:10:07Z

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:

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)

lyxal · Accepted Answer · 2023-03-16 03:49:10Z

3

Vyxal, 25 bytes

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

Try it Online!

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

answered Mar 16 at 3:49

lyxal

32.3k2 gold badges56 silver badges138 bronze badges

\$\begingroup\$ Get outgolfed lol :p \$\endgroup\$
– The Thonnu
Mar 16 at 11:50
3

\$\begingroup\$ @TheThonnu you say that like it's something that doesn't happen on days that end in y :p \$\endgroup\$
– lyxal
Mar 16 at 12:11

Add a comment |

Kevin Cruijssen · Accepted Answer · 2023-03-16 09:56:43Z

05AB1E, 19 15 bytes

ΔZªć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)
  ª                 #  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

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

Dominic van Essen · Accepted Answer · 2023-03-16 11:45:16Z

3

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...

edited Mar 16 at 11:45

answered Mar 16 at 10:57

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

Add a comment |

pajonk · Accepted Answer · 2023-03-18 18:42:57Z

3

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.

edited Mar 18 at 18:42

answered Mar 17 at 19:11

pajonk

15.1k3 gold badges21 silver badges65 bronze badges

\$\begingroup\$ Making some more use of numpy, range(len(x)) can be r_[:len(x)] \$\endgroup\$
– ovs
Mar 18 at 16:56

Add a comment |

G B · Accepted Answer · 2023-03-20 15:23:33Z

3

Ruby, 47 ... 41 bytes

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

Try it online!

edited Mar 20 at 15:23

answered Mar 17 at 9:07

G B

21.3k1 gold badge19 silver badges51 bronze badges

1

\$\begingroup\$ 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. \$\endgroup\$
– ovs
Mar 17 at 11:17
\$\begingroup\$ @ovs Is fixed now \$\endgroup\$
– G B
Mar 31 at 14:36

Add a comment |

ovs · Accepted Answer · 2023-03-16 14:00:26Z

2

BQN, 7 bytes^SBCS

Another port of pajonks R answer.

0⌈´⍋-⊒˜

Run online!

answered Mar 16 at 14:00

ovs

58.1k3 gold badges42 silver badges154 bronze badges

Add a comment |

The Thonnu · Accepted Answer · 2023-03-16 14:45:41Z

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 thanks. We can use the G flag as well to save another one. — The Thonnu, Mar 16 at 14:46

Jonathan Allan · Accepted Answer · 2023-03-16 21:04:28Z

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)

Conor O'Brien · Accepted Answer · 2023-03-18 05:04:13Z

2

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)

answered Mar 18 at 5:04

Conor O'Brien

39.9k3 gold badges88 silver badges178 bronze badges

Add a comment |

chunes · Accepted Answer · 2023-03-16 16:10:09Z

1

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.

answered Mar 16 at 16:10

chunes

22.8k3 gold badges21 silver badges51 bronze badges

Add a comment |

Yousername · Accepted Answer · 2023-03-21 22:10:01Z

1

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.

edited Mar 21 at 22:10

answered Mar 18 at 3:12

Yousername

3,6509 silver badges24 bronze badges

\$\begingroup\$ This seems to work for 48 bytes. \$\endgroup\$
– Aiden Chow
Mar 21 at 4:53

Add a comment |

Aiden Chow · Accepted Answer · 2023-03-23 04:41:37Z

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 , ┌─┼─┐ 
⌈       ⍋ - ∘ 
           ┌┴┐
           ⍳ ≢

138 Aspen · Accepted Answer · 2023-04-09 06:23:31Z

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 *)

Stack Exchange Network

How long to carry sort?

Worked example

Task

Test cases

17 Answers 17

R, 41 40 35 bytes

JavaScript (ES6), 50 bytes

Commented

JavaScript (ES6), 66 bytes

Commented

Charcoal, 53 33 31 bytes

Excel (ms365), 137 bytes

Vyxal, 25 bytes

05AB1E, 19 15 bytes

R, 90 82 bytes

Python + numpy, 67 65 bytes

Ruby, 47 ... 41 bytes

BQN, 7 bytes^SBCS

Vyxal `G`, 9 7 6 bytes

Explanation

Jelly, 4 bytes

How?

J, 14 bytes

Explanation

Factor, 46 bytes

Desmos, 52 48 bytes

APL(Dyalog Unicode), 9 bytes ^SBCS

Explanation

Wolfram Language (Mathematica), 66 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
array
sorting
or ask your own question.

Hot Network Questions

How long to carry sort?

Worked example

Task

Test cases

17 Answers 17

R, 41 40 35 bytes

JavaScript (ES6), 50 bytes

Commented

JavaScript (ES6), 66 bytes

Commented

Charcoal, 53 33 31 bytes

Excel (ms365), 137 bytes

Vyxal, 25 bytes

05AB1E, 19 15 bytes

R, 90 82 bytes

Python + numpy, 67 65 bytes

Ruby, 47 ... 41 bytes

BQN, 7 bytesSBCS

Vyxal G, 9 7 6 bytes

Explanation

Jelly, 4 bytes

How?

J, 14 bytes

Explanation

Factor, 46 bytes

Desmos, 52 48 bytes

APL(Dyalog Unicode), 9 bytes SBCS

Explanation

Wolfram Language (Mathematica), 66 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfarraysorting or ask your own question.

Related

Hot Network Questions

BQN, 7 bytes^SBCS

Vyxal `G`, 9 7 6 bytes

APL(Dyalog Unicode), 9 bytes ^SBCS

Not the answer you're looking for? Browse other questions tagged
code-golf
array
sorting
or ask your own question.