63
\$\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\$
7
  • 1
    \$\begingroup\$ Is the check highest < current? Or highest <= current? \$\endgroup\$ Oct 26 '15 at 13:20
  • 7
    \$\begingroup\$ Keep the current element if highest (so far)<=current. \$\endgroup\$ 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\$ Oct 26 '15 at 20:49
  • 20
    \$\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

64 Answers 64

1 2
3
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
  • 1
    \$\begingroup\$ You can save a byte using || instead of ?:: Try it online! \$\endgroup\$
    – Xcali
    Aug 10 '19 at 3:46
0
\$\begingroup\$

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

Husk, 2 bytes

ü<

Try it online!

nub sieve using lesser than.

\$\endgroup\$
1 2
3

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.