Implement the "Lazy Sort"

Question

I'm supposed to sort a list of numbers, but I'm super lazy. It's really hard to figure how to swap all the numbers around until all of them are in increasing order, so I came up with my own algorithm that will guarantee that the new list is sorted¹. Here's how it works:

For a list of size N, we'll need N-1 iterations. On each iteration,

• Check if the N'th number is smaller than the N+1'th number. If it is, then these two numbers are already sorted, and we can skip this iteration.

• If they are not, then you need to continually decrement the first N numbers until these two numbers are in order.

Let's take a concrete example. Let's say the input was

10 5 7 6 1

On the first iteration, we'll compare 10 and 5. 10 is larger than 5, so we decrement it until it's smaller:

4 5 7 6 1

Now we compare 5 and 7. 5 is smaller than 7, so we don't need to do anything on this iteration. So we go to the next and compare 7 and 6. 7 is larger than 6, so we decrement the first three numbers until it's smaller than 6, and we get this:

2 3 5 6 1

Now we compare 6 and 1. Again, 6 is larger than 1, so we decrement the first four numbers until it's smaller than 1, and we get this:

-4 -3 -1 0 1

And we're done! Now our list is in perfect sorted order. And, to make things even better, we only had to iterate through the list N-1 times, so this algorithm sorts lists in O(N-1) time, which I'm pretty sure is the fastest algorithm there is.²

Your challenge for today is to implement this Lazy Sort. Your program or function will be given an array of integers in whatever standard format you like, and you must perform this lazy sort and return the new "sorted" list. The array will never be empty or contain non-integers.

Here are some examples:

Input: 10 5 7 6 1
Output: -4 -3 -1 0 1

Input: 3 2 1
Output: -1 0 1

Input: 1 2 3
Output: 1 2 3

Input: 19
Output: 19

Input: 1 1 1 1 1 1 1 1 1 
Output: -7 -6 -5 -4 -3 -2 -1 0 1 

Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16

Input: -8 17 9 7
Output: -20 5 6 7

As always, this is code-golf, so write the shortest program you can!

---

¹ This doesn't mean what it sounds like it means, but it is technically true

² I am completely kidding, please don't hate me

Answer 1

Jelly,  14 12 11  9 bytes

-2 bytes thanks to ETHproductions (use the minimum dyad, «)

I’«0Ṛ+\Ṛ+

A monadic link taking and returning lists of integers.

Try it online! or see the test suite.

I really don't think this is Lazy™ enough!

How?

I’«0Ṛ+\Ṛ+ - Link: list of integers, a              e.g. [ 8, 3, 3, 4, 6, 2]
I         - increments between consecutive items of a   [-5, 0, 1, 2,-4 ]
 ’        - decrement (vectorises)                      [-6,-1, 0, 1,-5 ]
   0      - literal 0
  «       - minimum of decremented increments and zero  [-6,-1, 0, 0,-5 ]
    Ṛ     - reverse                                     [-5, 0, 0,-1,-6 ]
      \   - cumulative reduce with:
     +    -   addition                                  [-5,-5,-5,-6,-12]
       Ṛ  - reverse                                     [-12,-6,-5,-5,-5]
        + - addition (with a)                           [-4,-3,-2,-1, 1, 2]

Answer 2

Haskell, 40 bytes

f(a:r)|h:t<-f r=h-max(r!!0-a)1:h:t
f x=x

Try it online!

Answer 3

JavaScript (ES6), 61 bytes

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

Test cases

let f =

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

console.log(JSON.stringify(f([10, 5, 7, 6, 1]))) // -4 -3 -1 0 1
console.log(JSON.stringify(f([3, 2, 1]))) // -1 0 1
console.log(JSON.stringify(f([1, 2, 3]))) // 1 2 3
console.log(JSON.stringify(f([19]))) // 19
console.log(JSON.stringify(f([1, 1, 1, 1, 1, 1, 1, 1, 1]))) // -7 -6 -5 -4 -3 -2 -1 0 1
console.log(JSON.stringify(f([5, 7, 11, 6, 16, 2, 9, 16, 6, 16]))) // 27 -25 -21 -20 -10 -9 -2 5 6 16
console.log(JSON.stringify(f([-8, 17, 9, 7]))) // -20 5 6 7

Answer 4

Jelly, 12 bytes

I»1U
0ị;Ç_\U

Try it online!

How it works

I»1U  Helper link. Argument: l (list of integers)
I     Compute the increments (difference between items) of l.
 »1   For each item n, take the maximum of n and 1.
   U  Reverse.

0ị;Ç_\U  Main link. Argument: l (list of integers)
   Ç     Call the helper link with argument l.
  ;      Concatenate this with
0ị       the 0th last item of the (1-indexed) l. (Can't use Ṫ because it modifies l)
    _\   Cumulatively reduce the result by subtraction.
      U  Reverse.

The basic idea at play is this: If you reverse the input and output arrays, the output is simply the input with each delta of 0 or greater replaced with -1. For example:

[10,  5,  7,  6,  1]   input
[ 1,  6,  7,  5, 10]   reverse
[   5,  1, -2,  5  ]   deltas
[  -1, -1, -2, -1  ]   min(deltas, -1)
[ 1, -1, -2, -1, -1]   reverse and concat the last item of the original
[ 1,  0, -2, -3, -4]   re-apply deltas
[-4, -3, -2,  0,  1]   reverse

Answer 5

k, 20 bytes

{x-|+\0,1_0|1+-':|x}

Try it online.

Explanation:

{                  } /function, x is input
                 |x  /reverse x
              -':    /difference between every element
            1+       /add one to each difference
          0|         /make minimum difference be 0
      0,1_           /swap first difference with a 0
    +\               /cumulative sum
   |                 /reverse again
 x-                  /subtract from x

Answer 6

Haskell, 56 bytes

a#(x:y:z)=map(+min(y-x-1)0)(a++[x])#(y:z)
a#x=a++x
([]#)

Try it online!

Keep the first part of the list in parameter a. At each step add the next element x to the end of a and increase all elements of a by the minimum of (y-x-1) and 0.

Answer 7

Python, 54 bytes

f=lambda a,*r:r and[f(*r)[0]-max(r[0]-a,1)]+f(*r)or[a]

Try it online!

Takes input splatted like f(1,2,3). Outputs a list. Uses exponential time.

Answer 8

C#, 76 bytes

a=>{for(int d=0,i=a.Length-1;i>0;a[--i]-=d)d=a[i-1]-d<a[i]?d:a[i-1]-a[i]+1;}

This modifies the list in place. It goes through the list backwards and keep a running total of the delta to apply to each number.

Answer 9

JavaScript (ES6), 59 bytes

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]

Answer 10

Brain-Flak, 153 bytes

{(({})<>[({})])(({}({}))[({}[{}])])<>(([{}]({})))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}({}<>{}())((<>))}{}{}}{}<>{}([]){{}({}<>)<>([])}<>

Try it online!

This includes +1 for the -r flag.

#While True
{

    #Push the last value left in the array minus the counter onto the alternate stack
    (({})<>[({})])

    #Put the counter back on top of the alternate stack
    (({}({}))[({}[{}])])

    #Toggle
    <>

    #Find the difference between the last two inputs left on the array
    (([{}]({})))

    #Greater than or equal to 0?
    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    #If So:
    {

      #Pop the truthy/falsy value
      {}

      #Increment the counter by the difference between elements +1
      ({}<>{}())

      #Push two falsys
      ((<>))

    #Endwhile
    }

    #Pop the two falsys
    {}{}

#Endwhile
}

#Pop the falsy

{}

#Toggle back
<>

#Pop the counter

#Reverse the stack
{}
([]){{}({}<>)<>([])}<>

Answer 11

R, 56 bytes

function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}

Answer 12

JavaScript (ES6), 68 bytes

a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

Input and output is an array of integers.

Test Snippet

f=
a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

<input id=I oninput="O.value=f(this.value.split` `.map(x=>+x)).join` `">
<input id=O disabled>

Answer 13

JavaScript (ES6), 50 bytes

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

Explanation:

This is a recursive solution, which first clones the array, then decreases all values up until an element is greater or equal to the next element in the array.

The function calls itself as long as any elements are out of order. When the elements are finally sorted, the clone is returned. (We can't return the array itself, because the some() method would have decremented all its elements, making them all off by -1.)

Test cases:

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

console.log(f([10,5,7,6,1])+'');
console.log(f([1,1,1,1,1,1,1,1,1])+'');
console.log(f([5,7,11,6,16,2,9,16,6,16])+'');
console.log(f([19])+'');
console.log(f([-8,17,9,7])+'');
console.log(f([1,2,3,4,5,6,7])+'');

Answer 14

SWI-Prolog, 194 bytes

:-use_module(library(clpfd)).
f([],[],_,_).
f([A|B],[M|N],P,D):-A#=M-D-E,A#<P,abs(M,S),T#=S+1,E in 0..T,label([E]),f(B,N,A,D+E).
l([],[]).
l(A,B):-reverse(Z,B),f([X|Y],Z,X+1,0),reverse(A,[X|Y]).

Might be able to try it online here: http://swish.swi-prolog.org/p/LazySort.pl

You ask l(L, [10,5,7,6,1]). which says "solve for L, where L is the lazy sorted version of this list".

The two functions are:

• lazysorted(A,B) - states that A is the lazysorted version of B, if they're both empty lists, or if A can be obtained by reversing B, calling a helper function to walk the list and do a subtraction with an accumulator pushing each value lower than the previous one, and reversing the result of that back to the right way around.
• f helper matches two lists, the value of the previous number in the list, and a rolling difference accumulator, and solves for the new value of the current list position being the original value minus the difference accumulator, optionally minus a new value required to force this value below the previous number in the list, and f must solve for the tail of the list recursively with the now increased difference accumulator.

Screenshot of the test cases on Swish:

Answer 15

C# (.NET Core), 89 88 86 79 bytes

• Saved just 1 byte with a slightly different approach.
• Saved another 2 bytes with a simplification of the fors.
• Saved 7 bytes thanks to the amazing golfing skills of VisualMelon.

a=>{for(int i=0,j,k;++i<a.Length;)for(k=a[i-1]-a[j=i]+1;--j>=0;)a[j]-=k>0?k:0;}

Try it online!

First for iterates through the array, then it calculates the decrement and finally the second for decrements the elements if necessary until the ith position.

Is it valid to just modify the original array instead of returning a new one (still getting used to the rules)?

Answer 16

JavaScript (ES6), 61 bytes

a=>a.reduceRight((r,e)=>[e-(d=(c=e-r[0]+1)>d?c:d),...r],d=[])

Not the shortest solution but I couldn't pass over the opportunity to use reduceRight.