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

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 5

Octave, 27 19 bytes

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

Answer 6

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 7

Python 2, 49

f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(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

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 13

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 14

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 15

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 16

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 17

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 18

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

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 20

Husk, 2 bytes

ü<

Try it online!

nub sieve using lesser than.

Answer 21

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

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 24

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 25

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 26

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 27

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 28

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 29

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 30

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