61
\$\begingroup\$

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>

\$\endgroup\$
  • 1
    \$\begingroup\$ Is the check highest < current? Or highest <= current? \$\endgroup\$ – Morgan Thrapp Oct 26 '15 at 13:20
  • 7
    \$\begingroup\$ Keep the current element if highest (so far)<=current. \$\endgroup\$ – SuperJedi224 Oct 26 '15 at 13:21
  • \$\begingroup\$ Can we assume that there will be at least one element in the list? \$\endgroup\$ – lirtosiast Oct 26 '15 at 20:44
  • \$\begingroup\$ @ThomasKwa: Yes. \$\endgroup\$ – SuperJedi224 Oct 26 '15 at 20:49
  • 19
    \$\begingroup\$ Dropsorts improved efficiency could save a company a lot of money if utilized in the payroll system. \$\endgroup\$ – PyRulez Oct 26 '15 at 21:06

60 Answers 60

1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ d$x:l is shorter than x:e l x \$\endgroup\$ – Akangka Oct 28 '15 at 12:13
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 45 bytes

->a{o=[];a.map{|n|o<<n if !o[0]||n>=o.max};o}
\$\endgroup\$
1
\$\begingroup\$

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Sorry to say, but this doesn't seem to work for the -7 -8 -5 0 -1 1 test case. :( \$\endgroup\$ – manatwork Oct 29 '15 at 16:36
  • \$\begingroup\$ @manatwork Thanks for noticing. :) The problem was that $p is undefined till a next higher number is found. Adding an additional check solved that problem. \$\endgroup\$ – LukStorms Oct 29 '15 at 22:14
1
\$\begingroup\$

MATL, 6 bytes

ttY>=)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Japt, 8 bytes

f@¯Y e§X

Try it here

\$\endgroup\$
  • \$\begingroup\$ This fails on some inputs where the original list goes down and then back up, though I don't see any test cases where that would be a problem. Here's an example. \$\endgroup\$ – Kamil Drakari Oct 29 '18 at 20:47
  • \$\begingroup\$ Thanks, @KamilDrakari; I misread the spec. (Or, rather, I didn't read the spec at all, just based my solution on the test cases! :) \$\endgroup\$ – Shaggy Oct 30 '18 at 11:55
1
\$\begingroup\$

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

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

\$\endgroup\$
  • \$\begingroup\$ You can get your function based answer down to 139 bytes as 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 or if get it down to 129 bytes with a subroutine approach as Sub 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) c=r End sub \$\endgroup\$ – Taylor Scott Aug 11 at 14:20
  • \$\begingroup\$ There is no online IDE for any of the VB family at this time, but if you are interested in something similar, you may consider taking a look at Yabasic at TIO. \$\endgroup\$ – Taylor Scott Aug 11 at 14:27
  • \$\begingroup\$ @taylorscott, Good tips to tighten it up. I can't get your sub() method to work. The c=r line is giving the error Variable uses an Automation type not supported in Visual Basic. \$\endgroup\$ – Ben Aug 12 at 2:32
  • 1
    \$\begingroup\$ Ok. I got the sub() method to work (offline) by changing my test case to pass a variant array of long instead of a variant array of string. That involved writing a loop to convert the string array to a long array which makes the test code longer. It will allow the val() call to be removed which removes another 5 characters. I will add your suggestion in a formatted block but not rewrite the test case because it's late and I'm tired (or just lazy). \$\endgroup\$ – Ben Aug 12 at 3:21
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

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

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

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

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.

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

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

PHP, 63 bytes

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

Try it online!

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

SmileBASIC, 57 bytes

DEF D A
WHILE LEN(A)N=SHIFT(A)IF N>=M THEN M=N?N
WEND
END
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 24 22 bytes

Includes +2 for -la

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

Try it online!

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

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)

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

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

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.

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

Perl 6, 35 bytes

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

Try it online!

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

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.

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

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!

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

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!

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

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.

\$\endgroup\$
  • \$\begingroup\$ Since you do not seem to recurse on f, you could spare yourself the first two bytes. \$\endgroup\$ – Jonathan Frech Apr 28 at 21:04
  • \$\begingroup\$ @Jonathan Frech Oh ok \$\endgroup\$ – Naruyoko Apr 28 at 21:11
  • \$\begingroup\$ I am possibly misunderstanding your implementation, but it does not seem to work properly. \$\endgroup\$ – Jonathan Frech Apr 28 at 22:21
0
\$\begingroup\$

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

Perl 5.10.0 -n, 17 16 15 bytes

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

Try it online!

-1 byte thanks to Xcali

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a byte using || instead of ?:: Try it online! \$\endgroup\$ – Xcali Aug 10 at 3:46
0
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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