Lossy Sorting (Implement Dropsort)

Question

Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only some of the original elements. Any element that is not at least as large as the maximum of the elements preceding it is simply removed from the list and discarded.

In this task, you will be given a list of integers as input (STDIN or function argument, you are required to support at least the range of 8-bit signed integers.) Your task is to dropsort them and then output the remaining elements in order.

You may assume that the list is non-empty.

This is code golf, so the shortest program wins.

Test Cases

Input             Output
1 2 5 4 3 7       1 2 5 7
10 -1 12          10 12
-7 -8 -5 0 -1 1   -7 -5 0 1
9 8 7 6 5         9
10 13 17 21       10 13 17 21
10 10 10 9 10     10 10 10 10

Leaderboard

var QUESTION_ID=61808,OVERRIDE_USER=39022;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Answer 1

APL, 9 bytes

⊢(/⍨)⊢=⌈\

This is a monadic function train with diagram:

┌─┼───┐  
⊢ ⍨ ┌─┼─┐
┌─┘ ⊢ = \
/     ┌─┘
      ⌈  

The non-train version is

{⍵/⍨⍵=⌈\⍵}

This basically checks if each element is equal to the running maximum.

Note that Martin Büttner's J solution is the same length as this and was posted first.

Answer 2

J, 10 9 bytes

#~(=>./\)

Working version of my CJam idea (in fewer bytes). E.g.:

   f =: #~(=>./\)
   f 10 10 10 9 10
10 10 10 10
   f 1 2 5 4 3 7
1 2 5 7

Explanation

First, we get the maximum of each prefix, with:

    >./\

(Here, >. is the maximum operator, / folds that operator onto a list, and \ gets all the prefixes of the input.)

Then we compare the initial list with those maxima for equality:

  (=>./\)

And finally, we select all elements where this list of boolean results gave a 1:

#~(=>./\)

Answer 3

Haskell, 28

foldr(\x l->x:filter(x<)l)[] 

An anonymous function. Call it like

foldr(\x l->x:filter(x<)l)[] [-7, -8, -5, 0, -1, 1] 
[-7,-5,0,1]

Equivalent to the recursion

f[]=[]
f(x:l)=x:filter(x<)(f l)

Translated iteratively, we iterate over the elements, and for each one we see, we remove the ones smaller than it from the remainder of the list that we're iterating over. Thanks to Antisthenes for a byte saved with (x<).

Answer 4

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))

Answer 5

JavaScript (ES6), 29

Abusing of the standard type conversion in javascript, array to number:

• array of just 1 number => that number
• any other array => NaN

d=l=>l.filter(v=>l>v?0:[l=v])

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[
  [[1,2,5,4,3,7], [1,2,5,7]]
, [[10,-1,12], [10,12]]
, [[-7,-8,-5,0,-1,1], [-7,-5,0,1]]
, [[9,8,7,6,5], [9]]
, [[10,13,17,21], [10,13,17,21]]
, [[10,10,10,9,10], [10,10,10,10]]
].forEach(t=>( i=t[0],r=d(i),x=t[1],              
  console.log('Test '+i+' -> '+r+(r+''==x+''?' OK':' Fail (expected '+x+')')))
)

<pre id=O></pre>

Answer 6

Brachylog, 5 bytes

⊇ᶠ↔ᵒt

Try it online!

Jelly, 5 bytes

ŒPUÞṪ

Try it online!

Explanation

⊇ᶠ↔ᵒt    ŒPUÞṪ
⊇ᶠ       ŒP       On all subsequences of {the input}
   ᵒ        Þ     sort by
  ↔        U      their reverse
    t        Ṫ    then take the last element (i.e. the maximum as given by the sort)

This is a rare situation: I get to use an algorithm which (as far as I could tell with a quick skim) nobody is using so far, and it somehow ends up the same length in two very different golfing languages with very different syntax and builtin sets, with a 1-to-1 correspondence between the programs (the commands are even in the same order!). So it seemed to make more sense to combine them – in a way, these are the same program, and I wrote it in both languages to see which was shorter – than to submit them separately.

The basic idea here is that the dropsort of a list is its subsequence with the lexicographically maximum reverse. Oddly, neither Brachylog nor Jelly has a builtin to find the maximum by a particular function (Jelly has a builtin to return all the maxima by a particular function, but that'd return a singleton list containing the result rather than the result itself, and also isn't even shorter than doing it this way). So instead, we generate all possible subsequences, sort by reverse, take the last.

The reason why "lexicographically maximum reverse" works is that the chosen output must end (thus its reverse must start) with the highest number in the input list (it's easy to see that the dropsort output will always end with that), and thus can't contain anything after that (because taking subsequences preserves order). Repeat inductively and we end up with the definition of dropsort.

Answer 7

Octave, 27 19 bytes

@(a)a(cummax(a)==a)

Answer 8

Pyth, 12 bytes

eMfqeTeST._Q

Verify all test cases at once.

How it works

         ._Q  Compute all prefixes of the input.
  f           Filter; for each T in the prefixes:
    eT          Retrieve the last element of T.
      eST       Sort T and retrieve its last element.
   q            Check for equality.
              Keep T if q returned True.
eM            Select the last element of each kept T.

Answer 9

Mathematica, 26 Bytes

DeleteDuplicates[#,#>#2&]&

Answer 10

R, 29 26 bytes

function(x)x[x>=cummax(x)]

This creates a function object that accepts a vector x and returns x after removing all elements not at least as large as the cumulative maximum of x.

Saved 3 bytes thanks to flodel!

Answer 11

K, 11 bytes

{x@&~x<|\x}

In action:

  f: {x@&~x<|\x}
  f'(1 2 5 4 3 7
     10 -1 12
     -7 -8 -5 0 -1 1
     9 8 7 6 5
     10 13 17 21
     10 10 10 9 10)

(1 2 5 7
 10 12
 -7 -5 0 1
 ,9
 10 13 17 21
 10 10 10 10)

Answer 12

PowerShell, 32 bytes

$args|?{$e-eq$p-or$_-ge$p;$p=$_}

Try it online!

Less golfed:

$args|?{
    $empty -eq $previous -or $_ -ge $previous
    $previous = $_
}

Answer 13

Python 3, 67

Pretty brute force. Changed it to a function, because I missed that it was a valid answer.

def f(i):
 s=[i[0]]
 for n in i[1:]:
  if s[-1]<=n:s+=[n]
 return s

Ungolfed version:

input_numbers = input().split()
sorted_numbers = []
previous_number = int(input_numbers[0])
for number in map(int, input_numbers):
    if previous_number <= number:
        sorted_numbers.append(number)
        previous_number = number
print(sorted_numbers)

Answer 14

Java, 82 bytes

void f(int[]a){int m=a[0];for(int n:a){System.out.print(m>n?"":n+" ");m=n>m?n:m;}}

Here's a simple output loop. It just keeps the max in m and compares each element.

Answer 15

Perl, 33 bytes

32 bytes code + -p

$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge

If additional spaces are acceptable in the output, can be 31 bytes by removing and ?. Accepts a string (or number of newline separated) strings via STDIN:

perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '-7 -8 -5 0 -1 1'
-7 -5 0 1

perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '10 10 10 9 10'
10 10 10 10

Answer 16

Haskell, 38 37 bytes

Saved 1 byte thanks to JArkinstall.

f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s

Answer 17

C# - 6864 or 132127 Characters

int[]f(int[]b){return b.Where((v,i)=>i<1||b[i-1]<=v).ToArray();}

Where in this case is iterating through the list, and for each element v at index i in the list, evaluates the boolean expression. If the expression evaluates to true, then the item is added to the result. The only real trick to the boolean expression is that C# short circuits or evaluation as soon as a condition evaluates to true. This prevents the IndexOutOfRangeException exception, and keeps the first element in the list.

If the input and output have to be strings (I couldn't tell for sure, so I'll leave it to the OP and the rest of you to decide.)

string t(string b){var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();return String.Join(" ",c.Where((v,i)=>i<1||c[i-1]<=v));}

Decompressing that a bit gives:

string t(string b) 
{
    var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();
    return String.Join(" ",c.Where((v, i)=>i<1||c[i-1]<=v));
}

In this case the second line of the function is using the exact same logic as above. The Select grabs the elements of the list and converts them to int. The call to ToList¹ forces the select to be evaluated, and turns the var into a List<int> at compile time, so that the Where is operating on a collection of integers.

Try it on C# Pad

Thanks to VisualMelon for helping trim 4 bytes and 5 bytes respectively. :)

_{1 tutu list?}

Answer 18

CJam, 15 bytes

q~{_2$<{;}&}*]p

Try it online in the CJam interpreter.

How it works

q~               Read an evaluate all input.
  {        }*    Reduce; push the first element; or each remaining element:
   _2$           Copy the topmost and second topmost element from the stack.
      <          Check if the topmost is smaller than the second topmost.
       {;}&      If it is, remove it from the stack.
             ]   Wrap the stack i an array.
              p  Print.

Answer 19

Python 2, 41 bytes

for n in input():
 if-n<=id:print n;id=-n

Try it online!

A nice to trick is to use id as the initial running maximum, since it's already initialized. Python 2 allows this weird comparison, but unfortunately functions are smaller than numbers, we instead store the running max negated.

---

Python 3.8 (pre-release), 41 bytes

lambda l,m=-128:[m:=n for n in l if n>=m]

Try it online!

A nice solution using the Python 3.8+ walrus operator. We use -128 as the initial minimum since the challenge specifies the code needs to work for signed 8-bit integers.

Answer 20

Python 3.8 (pre-release), 38 bytes

lambda l:[l:=[n]for n in l if n>=l[0]]

Try it online!

This outputs in the format

[[-2], [0], [1], [2], [5], [5], [7]]

e.g. a list of lists containing one element each. According to this default for output, it is allowed to use a singleton list in place of a single value, so arguably this should be allowed as well.

Answer 21

><> with -v flag, 36 31 + 2 = 33 bytes

:&\o " "&n:~& <
~ >l?!;:&:&(?!^

Input the list on the stack with -v so that the first element of the list is at the top of the stack. It will print the dropsorted list with a trailing space.

Test run :

$ for input in "1 2 5 4 3 7" "10 -1 12" "-7 -8 -5 0 -1 1" "9 8 7 6 5" "10 13 17 21" "10 10 10 9 10"; do echo $input '-> ' $(python fish.py dropsort.fsh -v $(echo $input | tac -s ' ')); done

1 2 5 4 3 7 ->  1 2 5 7

10 -1 12 ->  10 12

-7 -8 -5 0 -1 1 ->  -7 -5 0 1

9 8 7 6 5 ->  9

10 13 17 21 ->  10 13 17 21

10 10 10 9 10 ->  10 10 10 10

Edit : saved 5 bytes thanks to Fongoid

Answer 22

Burlesque, 13 bytes

11 byte solution that passes test-cases:

-.2CO:so)[~

Try online here.

Explanation:

-. -- prepend head of list to list
2CO -- n-grams (sliding window) of size 2
:so -- filter sorted lists
)[~ -- map last

However, this version only works by using the fact, that no two smaller numbers are in between two numbers. Otherwise use the version below (which is 13B):

Older versions:

J-]{cm-1.>}LO

Try online here. Explanation:

J -- duplicate
-] -- head
{
  cm -- compare (returning -1,0 or 1)
  -1.> -- greater than -1
}LO -- Loop

If you'd drop equal numbers as well you could go with just .> instead of using cm. Also, if lists only contain positive numbers you can use either 0 or -1 instead of J-].

Answer 23

C: 73 bytes

int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;

or

C: 49 bytes

(If customs header made for codegolf competitions is allowed)

I z,y;z=y=INT_MIN;w(s(D,&y)!=E)i(y>z)p(D,y),z=y;}

Still can't beat CJam, but at least this allow to beat few other languages.

Answer 24

Ruby, 32 characters

->a{m,=a;a.select{|n|m<=n&&m=n}}

Thanks to:

• Value Ink for reminding that in Ruby all numbers are truthy, so && number assignment does not change the preceding boolean expression.

Try it online!

Ruby, 41 37 characters

->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}

(My old attempt.)

Sample run:

2.1.5 :001 > [
2.1.5 :002 >     [1, 2, 5, 4, 3, 7],
2.1.5 :003 >     [10, -1, 12],
2.1.5 :004 >     [-7, -8, -5, 0, -1, 1],
2.1.5 :005 >     [9, 8, 7, 6, 5],
2.1.5 :006 >     [10, 13, 17, 21],
2.1.5 :007 >     [10, 10, 10, 9, 10],
2.1.5 :008 > ].each{ |test| p ->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}[test] }
[1, 2, 5, 7]
[10, 12]
[-7, -5, 0, 1]
[9]
[10, 13, 17, 21]
[10, 10, 10, 10]

Answer 25

Minkolang 0.9, 18 bytes

ndN(nd1R`2&dN$I$).

Try it here.

Explanation

ndN                Take first integer from input
(         $I$).    Repeat until the input is empty and then stop.
 nd1R`             Is the next integer less than the previous one?
      2&dN         If not (i.e., it's greater than or equal to), print it.

Answer 26

Python, 102 99 94 + 5 6 non-file-final newlines = 107 105 100 bytes

(I used tabs for indentation)

def d(l):
    j=b=0;m=l[j];r=[]
    for i in l:
        (m,b)=[(m,0),(i,1)][i>=m]
        if b>0:r+=[i]
        j+=1
    l[:]=r

Not the best out there, but this is my first shot at code golf. Couldn't figure out a way to sort the list inline without running into removal-related bugs, so I moved the ordered elements to a temporary list.

EDIT: list.append() is shorter than doing it the ugly way

r+=[i] was shorter than list.append(); thanks njzk2!

Answer 27

Scala: 232 126 120 bytes

def f(x:Int*)=(Seq[Int]()/:x)((r,y)=>r.headOption.filter(y>=).map(_=>y+:r).getOrElse(if(r.isEmpty) y+:r else r)).reverse

Answer 28

NARS2000 APL, 13 bytes

NARS2000 is a free APL interpreter for Windows; it includes multiset features accessed with the ⍦ operator.

(+⍦∩⌈\)

This is a monadic fork that takes the multiset intersection (⍦∩) of the input (+)* and the list of running maximums (⌈\).

Since ⍦ is not a standard APL character in the one-byte APL legacy encodings, we must use UTF-8, making the ⍦∩⌈ characters three bytes each. I chose + instead of ⊢ to save two bytes.

NARS2000 supports forks, which can be built into trains without parentheses, but unlike Dyalog it doesn't allow assignment to a function without wrapping the function in parentheses.

*+ is technically complex conjugate, but the input is real.

Answer 29

Scala, 54 bytes

def f(x:Int*)=(x:\Seq[Int]())((y,r)=>y+:r.filter(y<=))

Ungolfed:

def dropSort(xs: Seq[Int]): Seq[Int] =
  xs.foldRight(Seq.empty[Int]) { (x, result) =>
    x +: result.filter(r => r >= x)
  }

Answer 30

Tiny Lisp, 107 bytes

(This language was only published after this question, so this answer runs out of competition. Not that it had any chance to win. The language later evolved further to have more buildins than the ones I used here, but I'm staying with the version I originally implemented in 2015. This answer still works with the newer official interpreter, though it gives some warnings because I define a parameter a which shadows the new buildin a (for adding)._{Thanks to DLosc for the TIO link.})

(d r(q((m a)(i a(i(l(h a)m)(r m(t a))(c(h a)(r(h a)(t a))))()))))(d ds(q((b)(i b(c(h b)(r(h b)(t b)))()))))

This defines a function ds (and its recursive helper function r) which sorts its argument, which must be a list of integers.

r is not a tail-recursive function, so for very long lists this might run into a stack overflow.

Ungolfed:

(d r
   (q((m a)
      (i a
         (i (l (h a) m)
            (r m (t a))
            (c (h a)
               (r (h a) (t a))
             )
          )
         ()
       )
   ) )
 )
(d ds
  (q(
      (b)
      (i b
        (c (h b)
           (r (h b) (t b))
         )
        ()
       )
   ) )
 )

Here are some examples how to use this (with the test cases from the question):

(d list (q (args args)))
(d -
   (q( (n)
       (s 0 n)
    ) )
 ) 

(ds (list 1 2 5 4 3 7))
(ds (list 10 (- 1) 12))
(ds (list (- 7) (- 8) (- 5) 0 (- 1) 1))
(ds (list 9 8 7 6 5))
(ds (list 10 13 17 21))
(ds (list 10 10 10 9 10))

(Yeah, -7 is not an integer literal, so we have to define a function to represent them.) Output:

list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)

Answer 31

Jelly, 5 bytes

=»\Tị

Note that the challenge predates the creation of Jelly.

Try it online!

How it works

=»\Tị  Main link. Argument: A (list)

 »\    Yield the cumulative maxima of A.
=      Perform element-by-element comparison.
       Yields 1 iff A[n] = max(A[1], ..., A[n]).
   T   Get all indices of truthy elements.
    ị  Retrieve the items of A at those indices.

Answer 32

MATL, 6 bytes

ttY>=)

Try it online!

Answer 33

SWI-Prolog, 55 bytes

A/B:-append(C,[D,E|F],A),E<D,append(C,[D|F],G),G/B;A=B.

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

Answer 34

Japt, 8 bytes

f@¯Y e§X

Try it here

Answer 35

05AB1E, 8 6 bytes

vyMyQ—

Try it online!

v          # for each item of the input list
 y         # push it on the stack
  M        # push the maximum of the stack
   yQ      # is it equal to the maximum?
     —     # if yes, print it

Answer 36

Python 3, 58 56 bytes

f=lambda x:[e for i,e in enumerate(x)if max(x[:i+1])==e]

Not sure if the input would be a string or a list, my code only would work in the second case.

Answer 37

VBA, 173 133 bytes

Sub s(c)
d=UBound(c)
ReDim r(d)
r(i)=c(i)
For i=1To d
If r(j)<=c(i)Then j=j+1:r(j)=c(i)
Next
ReDim Preserve r(j)
c=r
End Sub

(after edits) The above code is shorter and expects the parameter c to be passed as a variant array of numbers. My original Test_Cases sub below uses the Split() function which returns an array of strings. You won't be able to use Test_Cases to test the above code. If you want to see the algorithm working you need to test with the function below.

148 bytes (as a function expecting a string array)

Function s(c)
d=UBound(c)
ReDim r(d)
r(i)=c(i)
For i=1To d
If Val(r(j))<=c(i)Then j=j+1:r(j)=c(i)
Next
ReDim Preserve r(j)
s=r
End Function

The following code use the function s() and sends all the test cases and shows the result.

Public Sub Test_Cases()

    Dim cases(5, 1) As String
    Dim i As Integer
    Dim match As Boolean

    ' Define space-delimited strings of numbers.
    ' The second array column shows the expected response.
    cases(0, 0) = "1 2 5 4 3 7":     cases(0, 1) = "1 2 5 7"
    cases(1, 0) = "10 -1 12":        cases(1, 1) = "10 12"
    cases(2, 0) = "-7 -8 -5 0 -1 1": cases(2, 1) = "-7 -5 0 1"
    cases(3, 0) = "9 8 7 6 5":       cases(3, 1) = "9"
    cases(4, 0) = "10 13 17 21":     cases(4, 1) = "10 13 17 21"
    cases(5, 0) = "10 10 10 9 10":   cases(5, 1) = "10 10 10 10"

    Debug.Print "Case Input"; Tab(25); "Output"; Tab(38); "Do they match?"
    For i = 0 To UBound(cases())
        Debug.Print i; Tab(6); cases(i, 0); Tab(25); cases(i, 1); Tab(42);
        ' When calling the sorting function, use Split() to convert the string to
        ' a character array and then use Join() to convert the sorted array back
        ' into a string.  Compare that to the expected response in the second column.
        match = cases(i, 1) = Join(s(Split(cases(i, 0), " ")), " ")
        Debug.Print match
    Next i
    Debug.Print

End Sub

Output should look like this in the Immediate window:

Case Input              Output       Do they match?
 0   1 2 5 4 3 7        1 2 5 7          True
 1   10 -1 12           10 12            True
 2   -7 -8 -5 0 -1 1    -7 -5 0 1        True
 3   9 8 7 6 5          9                True
 4   10 13 17 21        10 13 17 21      True
 5   10 10 10 9 10      10 10 10 10      True

This was a fun challenge. If you know of an online interpreter like TIO for VB6/VBScript/VBA please leave a comment.

If you want to test this code and have Microsoft Excel, Word, Access, or Outlook installed (Windows only), press Alt+F11 to open the VBA IDE. Insert a new code module (Alt+I,M) and clear out Option Explicit. Then paste in the code and press F5 to run it. The results should appear in the Immediate Window (press Ctrl+G if you don't see it).

Answer 38

Mathematica, 27 bytes

Pick[#,#-Max~FoldList~#,0]&

Answer 39

Haskell, 52 bytes

d(x:l)=x:e l x
e(x:l)m|x<m=e l m|0<1=x:e l x
e[]_=[]

d expects a list.

Answer 40

OCaml, 62

let rec f=function a::b::c when a>b->f(a::c)|a::t->a::f t|t->t

The idea is that if the second element is less than the first element, then we should discard the second element. Otherwise, the first element is kept and we move on to the rest of the list.

Answer 41

Ruby, 45 bytes

->a{o=[];a.map{|n|o<<n if !o[0]||n>=o.max};o}

Answer 42

Simplex v.0.7, 32 bytes

That was long. Sorry for the vague explanation.

u{viRux}ly^nR@^m^_R&>n?[L@o' s]]
u{viRux}                         ~~ take pseudo-tuple input
        ly                       ~~ converts to tuple
          ^nR@                   ~~ takes minimum and puts it into register
              ^m               ] ~~ map the tuple using inner function
                ^_               ~~ the current value
                  R&>n           ~~ checks if current value is not greater
                      ?[      ]  ~~ does inner if so
                        L@o' s   ~~ outputs the number and a space; stores as current min

Answer 43

Perl 5, (33 Bytes+2) = 35

A regex-less solution.

map{print$p=$_.$"if$_>=$p||!$p}@F

Test

Note that the @F array is populated because of the -a switch.

$ echo -7 -8 -5 0 -1 4 4 3 5|perl -na -e 'map{print$p=$_.$"if$_>=$p||!$p}@F'
-7 -5 0 4 4 5

Answer 44

PHP, 63 bytes

function d($l){$m=$l[0];foreach($l as$n)echo$n<$m?"":$m="$n ";}

Try it online!

Answer 45

SmileBASIC, 57 bytes

DEF D A
WHILE LEN(A)N=SHIFT(A)IF N>=M THEN M=N?N
WEND
END

Answer 46

Perl 5, 24 22 bytes

Includes +2 for -la

#!/usr/bin/perl -la
$_<"$o $_"||say$o=$_

Try it online!

Answer 47

Bash, 63 bytes

echo $1;a=$1;while test $a -gt ${2:?};do shift;done;shift;$0 $@

Try it online! (+3 bytes since "$0 $@" doesn't work in TIO)

Answer 48

Perl 5.10.0 -n, 17 16 15 bytes

$m>$_||say$m=$_

Try it online!

-1 byte thanks to Xcali

Answer 49

K (oK), 11 bytes

Solution:

{x@&~<':x}/

Try it online!

Examples:

{x@&~<':x}/1 2 5 4 3 7
1 2 5 7
{x@&~<':x}/10 -1 12
10 12
{x@&~<':x}/-7 -8 -5 0 -1 1
-7 -5 0 1
{x@&~<':x}/9 8 7 6 5
,9
{x@&~<':x}/10 13 17 21
10 13 17 21
{x@&~<':x}/10 10 10 9 10
10 10 10 10

Explanation:

{x@&~<':x}/ / the solution
{        }/ / perform function {} until results converge
     <':x   / less-than (<) each-previous (':) input
    ~       / not
   &        / where, indices where true
 x@         / index back into input at these indices

Answer 50

PowerShell, 59 bytes

param($a)$a[0];(1..$a.Count|?{$a[$_]-ge$a[$_-1]})|%{$a[$_]}

Try it online!

I will golf this further as soon as possible.

Answer 51

Perl 6, 35 bytes

{(grep {.[0]==.max},[\R,] $_)[*;0]}

Try it online!

Answer 52

Clojure, 55 bytes

#(for[[i j](map list(reductions max %)%):when(= i j)]j)

One day I'm gonna do a "Golfure" or something of that short which will have one-symbol names for most handy functions, and even more generic macros.

Answer 53

Python 3, 68 64 62 bytes

lambda L:[L[i]for i in range(len(L))if L[i]>=max(L[:1]+L[:i])]

Try it online!

Answer 54

C++ (gcc), 122 119 bytes

-3 bytes thanx to ceilingcat

#include<list>
auto f(std::list<int>l){auto i=l.begin();for(int m=*i;i!=l.end();)i=*i>=m?m=*i,++i:l.erase(i);return l;}

Try it online!

Answer 55

JavaScript, 7270 bytes

a=>{for(b=[a[l=i=0]];i<a.length;b[l]>=a[++i]?b[++l]=a[i]:0);return a}

72B->70B - -2B for removing assignment of the function.

Answer 56

MathGolf, 10 bytes

╓\ô`╙┼=╛o╘

Try it online!

This solution relies on stack manipulation. It could have been 2 bytes shorter if negative numbers are not included (skip the first two bytes). Basically a port of the 05AB1E answer, except there is more of a hassle to get the stack right.

Explanation

╓            minimum of two elements, min of list, minimum by filter
 \           swap top elements, pushing list to top
  ô          start block of length 6
   `         duplicate the top two items
    ╙        maximum of two elements, max of list, maximum by filter
     ┼       duplicate second item from top and push to top
      =      is equal (is the current element equal to the total maximum so far)
       ╛o    print without popping if equal
             loop ends here
         ╘   discard everything in stack

Answer 57

Oracle SQL, 115 bytes (Version 12c+)

select x from t match_recognize(order by i all rows per match pattern((p|{-y-})+)define p as x>=nvl(last(p.x,1),x))

It works with an assumption that input data is stored in a table t(i,x) (i for order), e.g.

with t(i,x) as (select rownum,value(v) from table(sys.odcinumberlist(1,2,5,4,3,7))v)

Test in SQL*Plus.

SQL> with t(i,x) as (select rownum,value(v) from table(sys.odcinumberlist(1,2,5,4,3,7))v)
  2  select x from t match_recognize(order by i all rows per match pattern((p|{-y-})+)define p as x>=nvl(last(p.x,1),x))
  3  /

         X
----------
         1
         2
         5
         7

Answer 58

Pushy, 14 bytes

@vL:Ov2d>?.;;_

Try it online!

                     \ Implicit: input on main stack.
@                    \ Reverse stack.
 v                   \ Move top item to auxiliary stack.
  L:        ;        \ length(main stack) times do:
    Ov               \   Move top item from main stack to auxiliary stack.
      2d>? ;         \   If top element > second element:
          .          \       Pop the main stack element.
             _       \ Output stack.

Answer 59

rs, 121 109 bytes

(\d+)/(_)^^(\1)
-/n
+\b((_+) n_+|(n_+) \3_+|(_+)(_+) \4|(_+ ) |( ) n_+)\b/\2\3\4\5\6\7
n/-
(_+)/(^^\1)
  / 0 

The magic line is 3, which basically continuously deletes elements that aren't sorted.

Live demo and test cases.

121-byte version

(\d+)/(_)^^(\1)
-/n
+\b(((_+) n_+)|((n_+) \5_+)|((_+)(_+) \7)|((_+ ) )|(( ) n_+))\b/\3\5\7\8\10\12
n/-
(_+)/(^^\1)
  / 0 

Dang...12 groups...

Live demo and test cases.

Answer 60

Ceylon, 73

Integer[]d(Integer[]l)=>[for(i->x in l.indexed)if(x==max{x,*l[0:i]})x];

Formatted and commented:

// dropsort: "sorts" a sequence of integers by dropping all elements which don't fit.
// input and output are (possible empty) sequences of integers.
Integer[] d(Integer[] l) =>
// construct a sequence with a comprehension
        [
    // iterate over the input sequence, with indexes.
    for (i->x in l.indexed)
        // only if x it is the maximum of ...
        if (x == max
            // .. an iterable made from x and the part of the input sequence just before the current index ...
                { x, *l[0:i] })
            // ... include x in the iteration.
            x];

This features an sequence comprehension (with for and if clause) for the return value, the => function defintion, the shortcut syntax X[] for Sequential<X> (i.e. a possibly empty sequence), a named argument list for max, in which we have actually no named arguments, but the contents for an iterable argument, given by a single entry and a spread argument made from a measured subsequence, to make it (the argument) non-empty (otherwise max could possibly return null, which can't be compared to x).

Answer 61

Python 2 59 bytes

f=lambda a: reduce(lambda x,y:x+([],[y])[y>x[-1]],a,[a[0]])

Assumes the list is not empty, as stated in the description. Simple.

Answer 62

RETURN, 29 bytes (noncompetitive)

[␃$a:␌[$¥][$a;-<[%][$a:␌]?]#]

Try it here.

Anonymous lambda that leaves result on Stack2. Usage:

1 2 5 4 3 7[␃$a:␌[$¥][$a;-<[%][$a:␌]?]#]!

NOTE: Make sure to paste this string using the Insert String button, which will transform the control pictures into their respective unprintables.

Explanation

[                            ]  lambda
 ␃$a:␌                         reverse stack, set TOS to a and push to Stack2
       [  ][               ]#   while loop
        $¥                        check if TOS is integer
            $a;-<                 if so, check if TOS < a
                 [ ][    ]?       conditional
                  %                 if so, drop TOS
                     $a:␌           otherwise, set TOS to a and push to Stack2