15
\$\begingroup\$

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 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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ So carry sort is a single pass through bubble sort's loop? \$\endgroup\$
    – Bbrk24
    Mar 15 at 22:22
  • \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    Mar 15 at 22:24
  • 4
    \$\begingroup\$ Grade up, if you have that builtin, will do a lot of the heavy lifting here. \$\endgroup\$
    – Neil
    Mar 16 at 1:00

17 Answers 17

11
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\begingroup\$ This is beautiful, but I think you need seq(!x) to avoid problems with single-element lists with a negative value...? \$\endgroup\$ Mar 16 at 11:52
  • \$\begingroup\$ (or \(x)`if`(a<-sum(x|1),max(order(x)-1:a),0)...?) \$\endgroup\$ 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\$ Mar 16 at 15:32
7
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

Charcoal, 53 33 31 bytes

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

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∨⌈η⁰

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 25 bytes

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

Try it Online!

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

\$\endgroup\$
2
  • \$\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
3
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Wouldn't ZªćU solve the potential problem with ćUZª? \$\endgroup\$
    – Neil
    Mar 16 at 9:53
  • \$\begingroup\$ @Neil You're completely right indeed, thanks. Can't believe I've overlooked that.. \$\endgroup\$ Mar 16 at 9:57
3
\$\begingroup\$

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

\$\endgroup\$
0
3
\$\begingroup\$

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.

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

Ruby, 47 ... 41 bytes

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

Try it online!

\$\endgroup\$
2
  • 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
2
\$\begingroup\$

BQN, 7 bytesSBCS

Another port of pajonks R answer.

0⌈´⍋-⊒˜

Run online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ I think ⇧$ẏ-0JG saves 2 bytes. \$\endgroup\$
    – Neil
    Mar 16 at 14:40
  • \$\begingroup\$ @Neil thanks. We can use the G flag as well to save another one. \$\endgroup\$
    – The Thonnu
    Mar 16 at 14:46
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

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

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 , ┌─┼─┐ 
⌈       ⍋ - ∘ 
           ┌┴┐
           ⍳ ≢
\$\endgroup\$
1
\$\begingroup\$

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 *)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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