# Lossy Sorting (Implement Dropsort)

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>

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

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

• Bonus points because it looks cute. – Sammitch Oct 26 '15 at 18:02
• Code looks like a disgruntled dude shooting at a cat flap – slebetman Oct 27 '15 at 5:42
• I don't know much about byte counting and what encoding is intended to be used, but according to mothereff.in/byte-counter and meta.codegolf.stackexchange.com/questions/4944/… this is 17 bytes, and bytesizematters.com it's 13. – DLeh Oct 28 '15 at 15:43
• @DLeh That's in UTF-8. APL has its own legacy encoding that is 1 byte per APL character, from before unicode existed. – isaacg Oct 29 '15 at 16:52
• @DLeh bytesizematters uses a made up algorithm to count the bytes, which does not (and cannot) correspond to an actual encoding. – Dennis Feb 19 '16 at 18:00

# 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:

#~(=>./\)


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

• Why not curry the lambda? Should save a few characters... – MathematicalOrchid Oct 29 '15 at 12:47
• @MathematicalOrchid If you mean foldr(\x->(x:).filter(>=x))[], that turns out to be the same length. – xnor Oct 29 '15 at 22:55
• Ah. I just saw the filter at the end and thought "hey, you can curry that!" Didn't occur to me that the x: forces you to add the dot operator. Oh well... – MathematicalOrchid Oct 30 '15 at 8:10
• it's O(n^2) though. lots of unneeded comparisons. ;-( – proud haskeller Mar 27 '16 at 22:27
• Why not change (>=x) to (x<)? It will save 1 byte – Antisthenes Jun 16 '17 at 20:02

# Python 2, 49

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

• This is amazing. – Morgan Thrapp Oct 26 '15 at 17:46
• @ThomasKwa The problem is how do you stop the recursive calls. You need the empty case even if the input excludes that case. – Bakuriu Oct 27 '15 at 12:39
• problem with that is that it is not linear because of max(a) – njzk2 Oct 28 '15 at 20:31
• @njzk2 The challenge does not require the implementations to run in linear time. – feersum Oct 28 '15 at 20:50
• @njzk2 Nice codes finish last! – feersum Oct 28 '15 at 21:06

# 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>

• Wow. I thought 38 bytes was approximately the best possible; apparently I was very wrong. +1 – ETHproductions Oct 26 '15 at 15:45
• Table driven tests. Nice! – slebetman Oct 27 '15 at 5:43

# Octave, 27 19 bytes

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


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


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

# 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!

• The function form would be shorter. – flodel Oct 26 '15 at 23:10
• @flodel You're absolutely right. Thanks! – Alex A. Oct 26 '15 at 23:19

# Mathematica, 26 Bytes

DeleteDuplicates[#,#>#2&]&

• I don't know Mathematica, but something that calls DeleteDuplicates doesn't look like it would return {10, 10, 10, 10} for input {10, 10, 10, 9, 10} – Dennis Oct 27 '15 at 15:49
• @Dennis: It does, I tested it. The trick is that I pass "is greater than" as "equivalence" test. Yes, it's a misuse of that function, but it works, and code golf is not exactly about best programming practices anyway. – celtschk Oct 27 '15 at 19:02
• OK, in spite of what the name suggests, DeleteDuplicates with two arguments seems to be a simple filter. – Dennis Oct 27 '15 at 19:19

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

• {x@&~<':x} is a byte shorter. – kirbyfan64sos Oct 26 '15 at 16:04
• @kirbyfan64sos: Using eachprior does not produce the correct result. Consider the input case 3 4 2 2 5. – JohnE Oct 26 '15 at 17:42
• Ah, I see. A fix would be {x@&~<':x}/, but that's the same length. – kirbyfan64sos Oct 26 '15 at 19:59

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

• You can shorten it by using a lambda: a->{int m=a[0]... – Daniel M. Oct 27 '15 at 17:14
• Yea, you usually can. I don't lambda-ize java golfs, though. – Geobits Oct 27 '15 at 17:57

## 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


# 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  • You can replace one of your sets of parentheses with a $ to cut down by one whole byte! f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s);f s=s (Semi-colon used because comments don't allow newlines) – JArkinstall Oct 27 '15 at 1:14 # 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 ToList1 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? • If I miscounted, or if my explanation needs some explaining, please let me know. :) – theB Oct 27 '15 at 2:58 • Nice work - you can save a few bytes by using some common tricks - you don't need the spaces after the array declarations int[]f(int[]b) is fine, and you can use i<1 rather than i==0 to shorten that check a bit. For the string version, you can also drop the brackets around a single-argument in a lambda (e.g. (d)=>int.Parse(d) can be d=>int.Parse(d). I also only count 67 bytes, not 68, in your orignal ;) – VisualMelon Oct 27 '15 at 9:13 • @VisualMelon - Thanks! I figured that any miscounting would end up making the total bigger. ;) – theB Oct 27 '15 at 9:28 # 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.  # PowerShell, 32 bytes $args|?{$e-eq$p-or$_-ge$p;$p=$_}


Try it online!

Less golfed:

$args|?{$empty -eq $previous -or$_ -ge $previous$previous = $_ }  # 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. • Sorry, the custom header isn't allowed; it would count as a different language. – lirtosiast Oct 26 '15 at 17:07 • The primary problem with your custom headers is that you published them after this competition started. – Dennis Oct 26 '15 at 19:31 • Sure I understand, but then I cannot use it neither in future competitions? – GameDeveloper Oct 27 '15 at 9:24 • @DarioOO You can, but you'd be required to include the import statement towards your byte count. – SuperJedi224 Mar 15 '16 at 14:14 • Or just call it a new language. – CalculatorFeline Mar 22 '16 at 4:07 ## Burlesque, 13 bytes 11 byte solution that passes test-cases: -.2CO:so)[~  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-]. • Yeah, but then I can't hyperlink it :). – mroman Oct 26 '15 at 16:44 • fixed. I'll just add a "try online here" line. – mroman Oct 26 '15 at 16:46 # 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)  ## Minkolang 0.9, 18 bytes ndN(nd1R2&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.  # Ruby, 41 37 characters ->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}  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]  • -[p] is shorter than .compact – Not that Charles Oct 27 '15 at 17:49 • Oops. Of course. Thank you. (Note to myself: is not enough to just upvote the [link codegolf.stackexchange.com/questions/363/… for golfing in Ruby[/link], I should also memorize them.) – manatwork Oct 27 '15 at 18:02 # 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. • So, why doesn't codegolf.stackexchange.com/questions/61808/… apply here too? – cat Mar 21 '16 at 20:02 • NARS2000 can't use the legacy APL encodings--and even before the rule that encodings must be the ones actually used by interpreters, this couldn't be 7 bytes because psi isn't part of any legacy APL encoding. – lirtosiast Mar 21 '16 at 21:48 # ><> 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

• You can save 5 bytes by refactoring line 1 as :&\o" "&n:~& < and line 2 as ~ >l?!;:&:&(?!^ – Fongoid Oct 27 '15 at 21:42
• @Fongoid thanks, updated ! – Aaron Oct 28 '15 at 10:37

# Python, 10299 94 + 5 6 non-file-final newlines = 107105 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!

• r+=[i] is shorted than r.append – njzk2 Oct 28 '15 at 20:44
• I tried doing that before, but got an error because I didn't realize you have to do it with brackets. Thanks! – James Murphy Oct 28 '15 at 20:57

# Scala: 232126 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

• Adding an "extension method" for List[Int] does not meet requirements, you should get the input via STDIN or as an argument. Plus, it bloats your answer... Why not simply have def dropSort(s:Seq[Int]):Seq[Int]? – Jacob Oct 27 '15 at 15:47
• I thought it would be fancy, but you're right, way too much bytes... – Martin Seeler Oct 27 '15 at 19:07
• Very nice improvement using fold! You can still shave off some spaces and also you can use y>= rather than _<=y which yields a compile warning without a proper import, but also demonstrates how awesome Scala is (oh, and shaves off another character). – Jacob Oct 28 '15 at 22:33
• Thx for the tipp! – Martin Seeler Oct 29 '15 at 7:07

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

• "-7 is not an integer literal" I'm still laughing, +1 – cat Mar 21 '16 at 19:58
• Did you really use up every single character for builtins? (Except r, I guess..) – CalculatorFeline Mar 22 '16 at 14:35
• @CatsAreFluffy sorry, I have problems understanding your comment. Tiny Lisp has 7 build-in functions and three build-in macros, all of them having single character-names (I guess to make the language easier to use for golfing), with parentheses and space being special syntax. Note that Tiny Lisp is not my invention. – Paŭlo Ebermann Apr 2 '16 at 15:02
• Ah, I think I get it now ... you are proposing to use a single-character name instead of ds? I guess this could be done, would save another byte. I guess I selected ds as a abbreviation for drop sort. – Paŭlo Ebermann Apr 2 '16 at 15:03
• Hey, I just noticed this. Nice job! According to meta consensus, unnamed lambda functions are a valid form of submission, so you can save 6 bytes by getting rid of (d ds and the matching ) at the end. Other golfs are possible if you want to use my current interpreter, but if you want to stick to the spec in the original question, that's fine too. :) – DLosc Feb 2 '18 at 23:37

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


# Mathematica, 27 bytes

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


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

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