Implement Lazy Drop Sort

Question

This challenge already describes dropsort. However, I'm kinda lazy and I really only need my array to be a bit more sorted than before, it doesn't need to be sorted all the way.

In Drop Sort, we drop every element less than any element before it. In Lazy Drop Sort, we drop every element less than the one strictly preceding it.

Here's an example. Consider the following array:

8 6 9 9 7 2 3 8 1 3

Let's mark every element less than the one before it.

8 6 9 9 7 2 3 8 1 3
  ^     ^ ^     ^

Notice how neither 3 was marked, nor the last 8. They are all larger than the single element to the left of them.

Completing the algorithm, removing the marked elements, we get:

8 9 9 3 8 3

That basically looks more sorted. Kinda. I'm lazy.

Your task, as you may have already deduced, is to implement this algorithm.

Input is an array of at least 1 positive integer between 1 and 9, so you can take a string of digits as well.

This is code-golf, fewest bytes wins!

Additional test cases:

1
1

1 2 3
1 2 3

5 3 1
5

1 2 3 2 1
1 2 3

1 1 1 9 9 9 1 1 1 9 9 9 1 1 1
1 1 1 9 9 9 1 1 9 9 9 1 1

9 9
9 9

5 2 4 2 3
5 4 3

Answer 1

Husk, 4 bytes

m←ġ<

Try it online!

Explanation

m←ġ<
  ġ<    Group the numbers into decreasing sequences
m←      Keep the first element of each sequence

Answer 2

JavaScript (ES6), 28 25 bytes

Saved 3 bytes thanks to @Shaggy

a=>a.filter(n=>~-a<(a=n))

Try it online!

Answer 3

R, 27 bytes

(l=scan())[c(T,diff(l)>=0)]

Try it online!

Answer 4

MATL, 9 8 bytes

Saved one byte thanks to Giuseppe.

0yd0<h~)

Try it online!

---

Explanation:

0                 % Push a zero
 y                % Implicitly grab the input and duplicate it.
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [8 6 9 9 7 2 3 8 1 3]
  d               % The difference between each number of the last element:
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [-2, 3, 0, -2, -5, 1, 5, -7, 2]
   0<             % Which are negative?
                  % Stack: [8 6 9 9 7 2 3 8 1 3], 0, [1 0 0 1 1 0 0 1 0]
     h            % Concatenate. Stack: [8 6 9 9 7 2 3 8 1 3], [0 1 0 0 1 1 0 0 1 0] 
      ~           % Negate. Stack: [8 6 9 9 7 2 3 8 1 3], [1 0 1 1 0 0 1 1 0 1]
       )          % Index. Stack: [8 9 9 3 8 3]

Answer 5

Perl 5.10.0 + -nl, 16 bytes

$f>$_||say;$f=$_

Try it online!

Answer 6

Haskell, 29 bytes

f s=[b|(a,b)<-zip(0:s)s,a<=b]

just a simple list comprehension.

Answer 7

Japt, 8 7 bytes

Saved 1 byte thanks to @Oliver

k@>(U=X

Test it online!

Alternatives:

f@T§(T=X
k@ä>0 gY
i0 ò> mÅ c

Answer 8

Java 8, 66 55 48 bytes

l->{for(int i=0;;)if(i>(i=l.next()))l.remove();}

-11 bytes after a tip from @OlivierGrégoire.
-7 more bytes thanks to @OlivierGrégoire.

Explanation:

Try it online.

l->{                     // Method with Integer-ListIterator parameter and no return-type
  for(int i=0;;)         //  Loop over all items
    if(i>(i=l.next()))   //   If the current item is larger than the next
      l.remove();}       //    Remove this next item

Answer 9

Stax, 5 bytes

âÿ╠╦░

Run and debug this online

Unpacking, ungolfing, and commenting the code, we get this.

Z   Push a zero under the input
f   Use the rest of the program as a filter on the input.  Output passing elements.
>   Current element is greater than previous?
_~  Push current element to the input stack; when the main stack is empty, pops fall back to this
!   Logical not; applies to the result of the greater-than

Run this one

The ordering of the instructions is awkward but there's a reason for it. Stax source code packing doesn't always yield the same size output for the same size input. Basically, you have a chance to save a byte if the last character of source has a lower character code. Well, ! has one of the lowest codes you can get for a printable character. (33 specifically) Many 6 byte ASCII stax programs can't pack any smaller. But if they end with a !, then they can. So the reason for this particular ordering of instructions is to ensure that the logical not ends up at the end of the program.

Answer 10

J, 12 Bytes

#~1,2&(<:/\)

Explanation:

#~1,2&(<:/\)    | Whole function, executed as a hook
       <:/      | Distribute <: (greater or equal) over an array
    2&(   \)    | Apply to each sub array of length 2
  1,            | Append a 1 to the front
#~              | Choose elements from the original array

Examples:

    2&(<:/\) 8 6 9 9 7 2 3 8 1 3
0 1 1 0 0 1 1 0 1
    1,2&(<:/\) 8 6 9 9 7 2 3 8 1 3
1 0 1 1 0 0 1 1 0 1
    (1 0 1 1 0 0 1 1 0 1) # 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3
    f =: #~1,2&(<:/\)
    f 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Try it online!

Answer 11

Jelly, 6 bytes

>Ɲ0;¬×

I/O is on strings.

Try it online!

Answer 12

Octave, 21 bytes

@(x)x(~[0,diff(x)<0])

Try it online!

Explanation:

Take a vector x as input, and create a vector [0, diff(x)<0], where diff(x) is a vector with the difference between all adjacent elements. Keep only those that are negative by comparing it to zero, giving us a list of all the elements we want to drop.

We then select the elements from the input vector that we want to keep.

Answer 13

V, 25 bytes

òjälá k$yl+@"òç-/d
ç /dw

Try it online!

Hexdump:

00000000: f26a e46c e120 6b24 796c 2b40 2218 f2e7  .j.l. k$yl+@"...
00000010: 2d2f 640a e720 2f64 77                   -/d.. /dw

Worst language for the job. But I did it for a dare.

Answer 14

Python 2, 52 46 45 42 bytes

lambda a:[v for v,w in zip(a,[1]+a)if v/w]

Try it online!

---

Saved:

• -3 bytes, thanks to Rod

Answer 15

Triangularity, 71 bytes

.....).....
....IEL....
...)rFD)...
..2+)IE)w..
.+h)2_stDO.
={M)IEm}...

Try it online!

How it works?

)IEL)rFD)2+)IE)w+h)2_stDO={M)IEm} – Full program.
)IE                               – Get the 0th input I and evaluate it.
   L)r                            – And push the range [0 ... length of I).
      F                   {       – Filter the integers in this range which satisfy:
       D)2+)IE)w+h)2_stDO=        – This condition. Runs each element E on a separate
                                    stack and discard those that don't meet the criteria.
       D)2+                       – Duplicate and add 2 to the second copy.
           )IE                    – Retrieve I again.
              )                   – Push a 0 onto the stack.
               w                  – Wrap the 0 in a list. [0]
                +                 – Prepend it to I.
                 h                – Head. Trim the elements after index E+2.
                  )2_             – Literal -2.
                     st           – Tail.
                       DO=        – Check whether the result is invariant over sorting.
                           M)IEm} – Last part: indexing into the input.
                           M    } – For each index that satisfies the conditions:
                            )IEm  – Retrieve the element of I at that position.

Answer 16

Wonder, 27 bytes

-> ':1.!> 'sS#<=.cns2.++[0]

Usage example:

(-> ':1.!> 'sS#<=.cns2.++[0])[8 6 9 9 7 2 3 8 1 3]

Explanation

Ungolfed version:

(map get 1).(fltr sS <=).(cns 2).(++ [0])

Prepend 0, get list of consecutive pairs, keep list items where first number <= second number, get second number of each pair.

Answer 17

Python, 40 bytes

f=lambda h,*t:t and h+f(*t)[h>t[0]:]or h

Try it online!

Input as tuple of characters.

---

Python 3, 41 bytes

p=''
for x in input():x<p or print(x);p=x

Try it online!

String input.

---

Python 2, 41 bytes

for x in input():
 if x>=id:print x
 id=x

Try it online!

String input, just because strings are greater than id but numbers are smaller.

Answer 18

Wolfram Language (Mathematica), 33 bytes

Pick[#,Arg[#-{0}~Join~Most@#],0]&

Try it online!

How it works

The code # - {0}~Join~Most@# turns an array {a,b,c,d,e,f} into {a,b-a,c-b,d-c,e-d,f-e}. Applying Arg to this sets negative numbers to Pi and nonnegative numbers to 0.

Pick[#, ..., 0]& picks out the entries of # where ... has a 0: in our case, exactly the elements that yield a nonnegative number when you subtract the previous element. In other words, these are exactly the entries we want to keep when lazydropsorting.

Answer 19

Wolfram Language (Mathematica), 20 bytes

#&@@@Split[#,##>0&]&
(* or *)
Max/@Split[#,##>0&]&

Try it online!

Explanation

Input = {8, 6, 9, 9, 7, 2, 3, 8, 1, 3}

Split[#,##>0&]

Group consecutive elements that are strictly decresasing: {{8, 6}, {9}, {9, 7, 2}, {3}, {8, 1}, {3}}

#&@@@

Take the first element of each: {8, 9, 9, 3, 8, 3}

Answer 20

SWI-Prolog, 44 bytes

[A,B|C]-[A|E]:-B<A,[B|C]-[B|E];[B|C]-E. L-L.

Usage: Call "List-X" where List is a bracket-enclosed, comma-separated list e.g. [1,4,5,1,11,6,7].

Answer 21

APL+WIN, 14 bytes

Prompts for screen input of a vector of integers.

(1,1>2-/v)/v←⎕

Answer 22

05AB1E, 6 bytes

ĆÁü›_Ï

Try it online!

Explanation

Ć        # append the head of the list
 Á       # rotate right
  ü›     # apply pair-wise greater-than
    _    # logical negate each
     Ï   # keep elements of input that are true in this list

Answer 23

C# (.NET Core), 33 + 18 = 51bytes

x=>x.Where((a,n)=>n<1||x[n-1]<=a)

Try it online!

basically the statement is where x is the first int in the array, or is greater than or equal to the previous number, keep it. Else drop it.

Answer 24

Kotlin, 39 bytes

a->a.filterIndexed{i,v->i<1||v>=a[i-1]}

Try it online!

Filter items that are either the first item (index==0, or even shorter index<1) OR the current Value is greater than or equal to the previous item (a[i-1]).

Answer 25

APL (Dyalog Unicode), 11 bytes

{⍵⌿⍨1⍪2≤⌿⍵}

Try it online!

This is actually pretty similar to Graham's answer, but in Dyalog, and independently developed. Also, more symmetric.

Answer 26

K4, 10 bytes

Solution:

x_/|&<':x:

Example:

q)k)x_/|&<':x:8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Explanation:

Find indices where element is less than preceding, remove these indices from the input

x_/|&<':x: / the solution
        x: / store input as x
     <':   / less-than each-previous
    &      / indices where true
   |       / reverse
 _/        / drop-over
x          / the input

Answer 27

Attache, 24 bytes

{Mask[1'(Delta!_>=0),_]}

Try it online!

Explanation

Mask selects all elements from its second argument which correspond to truthy elements in its first argument. 1'(Delta!_>=0) calculates the indices which correspond to elements that are supposed to be in the final array.

Other attempts

28 bytes (pointfree): ~Mask#(1&`'##Delta#`>=#C[0])

32 bytes: {Mask[1'(&`<= =>Slices[_,2]),_]}

Answer 28

Jelly, 9 bytes

0;>ƝżµḢÐṂ

Try it online!

This feels pretty bulky, wouldn't be that surprised if there is a better way.

0;>ƝżµḢÐṂ
   Ɲ       For each adjacent pair in the input...
  >        ...is the first element greater than the second? (yields a list of 0/1)
0;         prepend a zero to this list (always keep the first element)
    ż      zip with the input
     µ     new monadic link
       ÐṂ  keep elements of the list with minimal value of... (Ðḟ would have worked here and been slightly more clear but I'll leave it as it is)
      Ḣ    ...their first element

Answer 29

Swift 4, 56 55 bytes

{var l=0;print($0.filter{($0>=l,l=$0).0})}as([Int])->()

Try it online!

Explanation

{var l=0;           // Declare variable l
print($0.filter{(   // Print every element e in the input
  $0>=l,            //   where e >= l
  l=$0).0})         //   And set l to e
}as([Int])->()      // Set the input type to integer array

Answer 30

Brain-Flak, 136, 120 bytes

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

Here it is formatted and "readable".

((()))
{
    {}

    ([{}]({}))

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

    {
        {}(({})<>)(())(<>)
    }

    {}

    ([][()])

}{}{}<>

{
    {}
    ({}<>)<>
}<>

Try it online!

Answer 31

SHELL ( 45 Bytes)

Solution 1 : output on 1 line ( 57 Bytes)

L(){ for i in $*;do(($i>=$o))&&echo $i;o=$i;done|xargs;}

Test :

>L 8 6 9 9 7 2 3 8 1 3
8 9 9 3 8 3

Solution 2 : output 1 element / line ( 51 Bytes)

L(){ for i in $*;do(($i>=$o))&&echo $i;o=$i;done;}

Test :

>L 8 6 9 9 7 2 3 8 1 3
8
9
9
3
8 

Solution 3 : with bc ( 51 Bytes)

 L(){ for i in $*;do bc<<<"if($i>$o)$i";o=$i;done;}

Solution 4 : optimisation ( suppression in $*, thanks user17752 ) ( 45 Bytes)

 L(){ for i;do bc<<<"if($i>$o)$i";o=$i;done;}

Answer 32

Python 2, 50 49 bytes

f=lambda s:s and f(s[:-1])+s[-1]*(s[-2:]<s[-1]*3)

I/O is on strings.

Try it online!

Answer 33

Retina 0.8.2, 32 31 bytes

\d
$*
r`(?<=1\1) (1+)\b

1+
$.&

Try it online! Link includes test cases. Explanation: The first and last stages are simply unary conversion. The middle stage deletes the numbers that are preceded by a larger number. A right-to-left match is used so that the lookbehind can be placed at the start of the regex, saving 1 byte.

Answer 34

Fortran (GFortran), 74 bytes

SUBROUTINE D(I,J)
INTEGER I(J)
DO1 K=1,J
1 IF(I(K)>=I(K-1))PRINT*,I(K)
END

This is my entry in this lovely language. It simply prints the "sorted" array, doesn't return it. I is the array to be "sorted" and J is its length. The TIO link below shows a complete program (with 160 bytes) using the subroutine. The input array is hardcoded in the main program.

Actually, I think that there might be some way to get an unknown length array as input, even from STDIN, using allocatable arrays, but it would be a really ugly program. Anyway, it seems fair to be lazy while implementing a lazy algorithm in a aged (and, therefore, tired) programming language :).

Conclusion: Fortran is an awesome language for arrays, as far as you know their lengths.

Try it online!

Answer 35

C, 82 bytes

f(a,c,i,j)int*a;{for(i=-1;++i<c;j=a[i])printf("%d "+3*(i&&j>a[i]),a[i]);puts("");}

Try it online!

I used the usual tricks (using K&R-style functions, indexing into a constant string, etc.) and because I don't like ending output on the same line as the next program added a newline. To make sure that the 1-element arrays were handled correctly, I special-cased it.

Answer 36

C (clang), 53 bytes

x,c;f(char *s){for(x=0;c=*s++;x=c)c>=x?putchar(c):0;}

Try it online!

Takes input as string of digits, For all digits, prints it if greater than previous.