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

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 2

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 3

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 4

Mathematica, 27 bytes

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

Answer 5

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 6

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 7

Ruby, 45 bytes

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

Answer 8

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 9

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 10

MATL, 6 bytes

ttY>=)

Try it online!

Answer 11

Japt, 8 bytes

f@¯Y e§X

Try it here

Answer 12

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 13

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 14

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 15

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 16

Maple (48 and 50 bytes)

48 byte solution using a for loop:

m:=L[1];(for v in L do if v>=m then m:=v fi od);

50 byte solution using seq:

seq(if L[i]>=max(L[..i])then L[i]fi,i=1..nops(L));

Both examples expect their input to be in a list, L, and produce their output as a sequence.

Answer 17

Vyxal, 9 5 bytes

ɖ∴=Tİ

Try it Online!

Explanation

ɖ∴=Tİ
ɖ     # Cumulatively reduce by an element
 ∴    # Dyadic Maximum
  =   # equal
   T  # Get indices of truthy elements
    İ # Index into list at indices

Answer 18

Thunno, \$ 13 \log_{256}(96) \approx \$ 10.7 bytes

eDM=E1zIz0sAI

Attempt This Online!

Explanation

eDM=E1zIz0sAI  # Implicit input
e   E          # Map over the input:
 D             #  Duplicate it
  M=           #  Is it the largest number on the stack?
     1zI       # Truthy indices of this list
        z0     # Push the input list again
          sAI  # Index into the input list
               # Implicit output

Answer 19

Thunno 2, 6 bytes

Ʋ§;=Vi

Attempt This Online!

Explanation

Ʋ§;=Vi  # Implicit input
Ʋ ;     # Cumulative reduce (scanl) by:
 §      # Dyadic maximum
   =    # Equals the input list?
    V   # Truthy indices
     i  # Index in
        # Implicit output

Answer 20

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 21

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 22

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 23

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

Answer 24

PHP, 63 bytes

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

Try it online!

Answer 25

SmileBASIC, 57 bytes

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

Answer 26

Perl 5, 24 22 bytes

Includes +2 for -la

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

Try it online!

Answer 27

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 28

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 29

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 30

Perl 6, 35 bytes

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

Try it online!