DropSort it like it's hot

Question

As described in this 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.

To use one of their test cases, an input of {1, 2, 5, 4, 3, 7} yields {1, 2, 5, 7}, as 4 and 3 are both dropped for being smaller than the previously "sorted" value, 5.

We don't want "sorting" algorithms, we want them to be the real deal. Therefore, I want you to write a program that, given a list of numbers, outputs a list of DropSorted lists (to be a complete sorting algorithm, we would need to merge these lists, but merging two sorted lists has been done before, and asking you to do it again is pretty much asking two questions, so this question is specifically the "splitting" step of our complete DropSort).

The arrangement and content of our lists is crucial, however. The output of your program must be equivalent to the output of a DropSort, followed by a DropSort of the discarded values, and so on until you have only have a list of sorted chains. Again, borrowing the existing test suite (and adding two more):

Input                  -> Output
{1, 2, 5, 4, 3, 7}     -> {{1, 2, 5, 7}, {4}, {3}}
{10, -1, 12}           -> {{10, 12}, {-1}}
{-7, -8, -5, 0, -1, 1} -> {{-7, -5, 0, 1}, {-8, -1}}
{9, 8, 7, 6, 5}        -> {{9}, {8}, {7}, {6}, {5}}
{10, 13, 17, 21}       -> {{10, 13, 17, 21}}
{10, 10, 10, 9, 10}    -> {{10, 10, 10, 10}, {9}}  //Note equivalent values aren't dropped
{5, 4, 3, 8, 7, 6}     -> {{5, 8}, {4, 7}, {3, 6}}
{0, 2, 5, 4, 0, 7}     -> {{0, 2, 5, 7}, {4}, {0}}

You may assume the input is non-empty.

This is code-golf, so standard rules apply!

Answer 1

Haskell, 67 59 58 bytes

(q:r)!x|x<last q=q:r!x|1<2=(q++[x]):r
_!x=[[x]]
foldl(!)[]

Explanation: Given a list of lists (that are already sorted) and a value x, the ! operator will place x at the end of the first list whose last element is less than or equal to x. If no such list exists, the list [x] is placed at the end.

Try it online.

Answer 2

Husk, 10 bytes

hUmü<¡Ṡ-ü<

Try it online!

This is a combination of my other Husk answer and xnor's Haskell answer. The duplicate ü< feels clunky, but I don't know how to get rid of it...

Explanation

The function ü< translates to nubBy(>) in Haskell. It traverses a list from left to right, keeping those elements for which no previously kept element is strictly greater. In other words, it performs dropsort. The leftover elements are obtained by taking list difference of the original list and the result of ü<.

hUmü<¡Ṡ-ü<  Implicit input, say x = [2,3,5,4,4,2,7].
     ¡      Iterate
      Ṡ-    list difference between argument
        ü<  and its dropsort: [[2,3,5,4,4,2,7],[4,4,2],[2],[],[],[],...
  m         Map
   ü<       dropsort: [[2,3,5,7],[4,4],[2],[],[],[],...
 U          Prefix of unique elements: [[2,3,5,7],[4,4],[2],[]]
h           Drop last element: [[2,3,5,7],[4,4],[2]]

Answer 3

Haskell, 50 bytes

import Data.List
f[]=[]
f l|r<-nubBy(>)l=r:f(l\\r)

Try it online!

Answer 4

MATL, 15 10 9 bytes

5 bytes off using @beaker's idea of cumulative maximum

t"ttY>=&)

Input is a numeric row vector, in the format [1, 2, 5, 4, 3, 7] (commas are optional). The output contains lists separated by newlines, with the numbers in each list separated by spaces.

Try it online! Or verify all test cases.

Explanation

Given an array, the code picks from it every entry that equals the cumulative maximum up to that entry.

For example, given

1 2 5 4 3 7

the code picks the first, second, third and sixth entries:

1 2 5     7

Then the process is repeated on the subarray formed by the remaining entries (in the original order):

      4 3

This needs to be done until the subarray of remaining entries is empty. An upper bound on the required number of iterations is the input size. The last iterations may not be needed. In that case they operate on an empty array, producing additional empty arrays.

At the end, the stack contains the required arrays and possibly several empty arrays, which are not displayed at all.

t        % Implicit input. Duplicate
"        % Do as many times as the input size
  tt     %   Duplicate twice
  Y>     %   Cumulative maximum
  =      %   Compare for equality. Will be used as logical index
  &)     %   Two-output indexing: pushes indexed subarray, and then
         %   a subarray with the remaining entries
         % End (implicit)
         % Display stack (implicit). Empty arrays are not displayed

Answer 5

Husk, 16 bytes

hUm₁≤¡₁>
ṠfSz⁰G▲

Try it online!

Explanation

This first line is the main function, and the second is a higher order helper function (it takes a function as argument and returns a new function). It's accessed by the subscript ₁. The idea is that ₁≤ performs dropsort and ₁> gives the leftover elements.

ṠfSz⁰G▲  Helper function, takes binary function p (as ⁰) and list x (implicit).
         For example, p = (≤) and x = [2,4,3,4,5,2].
     G▲  Left scan on x with maximum: [2,4,4,4,5,5].
  Sz     Zip with x
    ⁰    using the function p: [1,1,0,1,1,0].
Ṡf       Keep elements of x at truthy indices: [2,4,4,5].

In the main function, we iterate the leftovers function ₁> and apply the dropsort function ₁≤ to the results.

hUm₁≤¡₁>  Main function, implicit list argument, say x = [2,4,3,4,5,2].
     ¡    Iterate
      ₁>  the leftovers function: [[2,4,3,4,5,2],[3,2],[2],[],[],[],...
  m       Map
   ₁≤     the dropsort function: [[2,4,4,5],[3],[2],[],[],[],...
 U        Prefix of unique elements: [[2,4,4,5],[3],[2],[]]
h         Drop last element (an empty list): [[2,4,4,5],[3],[2]]

Answer 6

Python 3, 131 112 103 95 bytes

Thanks a lot @Mr. Xcoder for a smashing 19 bytes!!

Thanks a lot @ovs for an amazing 17 bytes!

def f(x):
 a,*x=x or[0];m=[a];d=[]
 for i in x:[m,d][i<m[-1]]+=i,
 return[m]+(x and(d>[])*f(d))

Try it online!

Explanation:

def f(x):               #recursive function taking list, returns list of lists 
 if len(x)<2:return[x]  #for a single element return [element] 
 m=[x[0]];d=[]          #initialize main and dropped lists
 for i in x[1:]:[m,d][i<m[-1]]+=[i]  #append elements from the argument list accordingly into main and dropped list 
 return[m]+(d>[])*list(f(d)) #add main-list along with further evaluated dropped-list(recursived) into a list of lists

Answer 7

Haskell, 113 107 102 92 bytes

import Data.List
a!(b:c)|b<last a=a!c|1>0=a++[b]!c
a!b=a
g x@(b:c)|i<-[b]!c=i:g(x\\i)
g x=[]

Try it online!

This feels really long.

Explanation

! performs the drop sort on a list, while # collects the trimmings. g then repeatedly applies # until the list is empty recording the results in a list.

Answer 8

APL, 27 bytes

{⍵≡⍬:⍬⋄(⊂X/⍵),∇⍵/⍨~X←⍵≥⌈\⍵}

Explanation:

• ⍵≡⍬:⍬: if the input is empty, return the empty list
• X←⍵≥⌈\⍵: all numbers greater or equal to the running maximum
• (⊂X/⍵): the list of those numbers,
• ∇⍵/⍨~X: followed by the result of running this function on the remaining numbers

Answer 9

JavaScript (ES6), 64 bytes

f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

Ungolfed:

f=(a,l,r=[])=>
  a+a&&                                    //any elements left?
  [a.filter(                               //filter elements that are in order,
    e=>e<l?!r.push(e):(l=e,1)              //push unsorted elements to r
   ),                                      //push() returns the new length of the array,
                                           //... so !push() will always return false
   ...f(r)                                 //recurse on r
  ]

f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

console.log(JSON.stringify(f([1, 2, 5, 4, 3, 7])));     // [1, 2, 5, 7][4][3]
console.log(JSON.stringify(f([10, -1, 12])));           // [10, 12][-1]
console.log(JSON.stringify(f([-7, -8, -5, 0, -1, 1]))); // [-7, -5, 0, 1][-8, -1]
console.log(JSON.stringify(f([9, 8, 7, 6, 5])));        // [9][8][7][6][5]
console.log(JSON.stringify(f([10, 13, 17, 21])));       // [10, 13, 17, 21]
console.log(JSON.stringify(f([10, 10, 10, 9, 10])));    // [10, 10, 10, 10][9]
console.log(JSON.stringify(f([5, 4, 3, 8, 7, 6])));     // [5, 8][4, 7][3, 6]
console.log(JSON.stringify(f([0, 2, 5, 4, 0, 7])));     // [0,2,5,7],[4],[0]

Answer 10

R, 61 bytes

f=function(x)if(sum(x|1)){print(x[b<-x==cummax(x)]);f(x[!b])}

Try it online!

Recursive function. sum(x|1) is shorthand for length(x), so this recursion will run untill x is empty. cummax takes the cumulative maximum of x, which is then compared to x again. This produces a boolean vector of length x, where all the TRUEs correspond to sorted values. We use that to take a subset of x and print it. The function is then called again on the remainder of x.

Answer 11

Java 8, 182 179 177 bytes

import java.util.*;l->{List r=new Stack(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Stack()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}

-3 bytes thanks to @Nevay.
-2 bytes by using Stack instead of Vector.

Explanation:

Try it here.

import java.util.*;            // Required import for List and Vector
l->{                           // Method with ArrayList<Integer> parameter and List return-type
  List r=new Stack(),          //  Return-List
       t;                      //  Temp-List
  for(int p,i,x;               //  Some temp integers
      l.size()>0;)             //  Loop (1) as long as there are still items left in the list
    for(p=l.get(0),            //   Set `p` to the first item of the list
        r.add(t=new Stack()),  //   Add a new inner List to the result-List
        i=0;i<l.size();        //   Inner loop (2) from 0 to the size of the list (exclusive)
         p=x)                  //     After every iteration, save the previous value in `p`
      if((x=l.get(i++))>=p)    //    If the current item is equal or larger than the previous:
        t.add(l.remove(--i));  //     Add it to the temp-List, and remove it from the input-List
                               //   End of inner loop (2) (implicit / single-line body)
                               //  End of loop (1) (implicit / single-line body)
  return r;                    //  Return result-List
}                              // End of method

Answer 12

C#, 188 203 bytes

int[][]f(int[]a){int[]t=a.Where((n,i)=>i<1||n>=a[i-1]).ToArray(),m=a.Where((n,i)=>i>0&&n<a[i-1]).ToArray();var s=new int[][]{t}.ToList();if(m.Any())s.AddRange(f(m));return s.ToArray();}

The byte count includes +18 for:

using System.Linq;

Try it online!

Answer 13

C++14, 118 108 bytes

Using the algorithm from w0lf's Haskell answer.

As unnamed generic lambda. First parameter is a container of the values to dropsort (like vector<int>) and second parameter requires a compatible empty container of containers (like vector<vector<int>>) for the return value via reference.

In the first version of the program, there was R.clear;() as first statement, so that the container of containers didnt need to be empty. Peter Cordes thought this could into the specification, so dropping 10 byte for that.

[](auto A,auto&R){for(auto x:A){for(auto&D:R)if(D.back()<x){D.push_back(x);goto F;}R.emplace_back(1,x);F:;}}

Try it online!

Ungolfed:

[](auto A,auto&R){
 for(auto x:A){       //foreach item
  for(auto&D:R)       //foreach result list
   if(D.back()<x){    //x bigger than last element
    D.push_back(x);   //add x
    goto F;           //break and jump over the emplace
   }
  R.emplace_back(1,x);//create new list with this element
  F:;
 }
}

Answer 14

Python 2, 88 bytes

-4 bytes thanks to Arnold Palmer

b,r=input(),[]
for i in b:
 for l in r:
	if l[-1]<=i:l+=[i];break
 else:r+=[[i]]
print r

Try it online!

Solution similar to @w0lf's haskell [answer][1]

Rare use case for for-else construction

Iterate through sorted lists for l in r (empty at start).
If element(from input) i is larger than last element of list l[-1], add element to list l+=[i], break.
If no list was accepted, add new list with this elemens r+=[[i]]

Answer 15

JavaScript (ES6), 71 70 68 bytes

a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o

Pretty simple, just iterates the array, looks for the first inner array whose last value is <= to the next value to drop, if none exists, append a new inner array with the next value to the output, otherwise append the next value to the first found inner array that matches the condition.

Updates

Thanks to Neil, saved three bytes converting (...,o) to ...&&o and re-organizing the callback to map() to be more compact.

f=a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o;[[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],[5,4,3,8,7,6],[0,2,5,4,0,7]].map(f).map(JSON.stringify).map(v=>console.log(v))

.as-console-wrapper{max-height:100%!important}

Answer 16

Japt, 29 bytes

@lOpP)<1}a@=f_<VªOoV=Z+S}V=Ug

Test it online!

Answer 17

C (gcc), 176 175 173 bytes

#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;main(a){while(scanf("%d",*l+w)>0)++w;while(i=w){P(l[a=!a][w=0])for(j=1;j<i;++j){x=l[a][j];x<t?l[!a][w++]=x:P(x)}puts("");}}

Try it online!

Somewhat readable version:

#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;
main(a)
{
    while(scanf("%d",*l+w)>0)++w;
    while(i=w)
    {
        P(l[a=!a][w=0])
        for(j=1;j<i;++j)
        {
            x=l[a][j];
            x<t?l[!a][w++]=x:P(x)
        }
        puts("");
    }
}

Answer 18

PHP, 91 103 96 85 bytes

(Edited to add 12 chars of print_r($r); to meet requirement to output)
(Edited to remove 7 bytes when allowing PHP Errors)
(Edited to remove 11 bytes when golfing the assignment further)

while($a){$b=$d=[];foreach($a as$i)${max($b)>$i?d:b}[]=$i;$a=$d;$r[]=$b;}print_r($r);

Given input $a, it produces result $r

Pretty:

while ($a) {
    $b = $d = [];
    foreach ($a as $i) {
        ${max($b) > $i ? d : b}[] = $i;
    }
    $a   = $d;
    $r[] = $b;
}

The pseudo-recursive outer loop initializes the keep $b and discard $d arrays to empty, then does a basic drop sort loop, finally setting the discards as the new input and adding the keeps to the result $r

Answer 19

PHP, 102 bytes, 98 bytes

<?php function s($i){static$s;foreach($i as$v)${$v<max($l)?f:l}[]=$v;$s[]=$l;!$f?:s($f);return$s;}

Try it online!

-4 bytes, thanks to @Umbrella

Explanation

<?php

The function takes the input list as an array.

function s($i) {

$s, which will become the finally returned list of lists, is declared static. This extends its scope to all calls of this function, allowing the function to be called recursively without having to pass this result list as an argument or to return it.

    static $s;

Loop through each value in the list.

    foreach ($i as $v)

Is it less than the biggest current list member?

        $v < max($l) ?

Yes, put it on list $f for further sorting.

                        $f[] = $v :

No, put it on list $l.

                        $l[] = $v;

Push list $l onto the list of lists.

    $s[] = $l;

If there's anything in list $f, send it round again for further sorting.

    !$f ?: s($f);

Return the list of lists.

    return $s;
}

Answer 20

Sage, 102 bytes

def f(w,a=[]):
 for x in w:
  q,c=exists(a,lambda b:b[-1]<=x)
  if q:c+=[x]
  else:a+=[[x]]
 return a

Very similar to @Dead Possum's answer.
Appends each member x of w to the first list in a {list of lists} with x greater than it's last element.
if none, appends [x] to a.

I would really like it if exists returned a if nothing was found! Also trying to apply @officialaimm's one-line idea ...

Question: If I removed my code from the function, I'd have to assign w to input right? So would it save bytes?

Answer 21

Ocaml, 69 62 bytes

let rec d=function h::i::t when h>i->d(h::t)|h::t->h::d t|x->x

Explanation:

let rec d = function (* Implicitly take an list as a parameter *)
    (* If the list starts with two elements h and i and h is greater than i, drop i and sort the list starting with h and the rest t *)
    | h::i::t when h > i -> d (h::t) 
    (* If h is not greater than i, make a new list starting with h and a tail containing the drop sorted rest *)
    | h::t -> h::d t
    (* If none of the cases apply, the list is empty. *)
    | x -> x

Answer 22

APL, 100 88 83 79 78 57 56 77 76 bytes

{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)}

-0 bytes thanks to Kritixi Lithos...

Try it online!

There's got to be some better way to do this (There is). Any tips are very greatly appreciated and welcome.

How?

(Note, some of this explanation might be wrong, as I forgot how this worked)

{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)} - separate the argument into nested drop-sorts
{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}  - un-nesting (passed the result of the above)
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘     - fixing array mishaps (passed the result of the above)

Answer 23

Jelly, 26 bytes

<»\¬x@ðW;µ⁸Ñ
<»\x@µÑ
1Ŀ¹L?

This is the same method as marinus' APL answer.

Try it online!.

Answer 24

JavaScript (Node.js), 125 109 106 bytes

-16 18 bytes from Zacharý

-1 by removing { and } by changing the incrementer to include the "set last to the current"

m=x=>{z=[[],[]];l=NaN;for(i=0;i<x.length;l=x[i++])if(l>x[i])z[1].push(x[i]);else z[0].push(x[i]);return z}

Basically, asks is the current item greater than the last item, add to the first list. Otherwise, add to the second.

Found out during this that comparing any number to NaN will always result false. Interesting!

Explanation:

m = x => {                         // Create function
  z = [[], []];                      // Initialize dropsort output
  l = NaN;                           // Initialize last element
  for (i = 0; i < x.length; l=x[i++])// For each item in input...
    if (l > x[i])                    // If current item is greater than previous
      z[1].push(x[i]);               // Then add it to the first part of output
    else                             // Elsewise
      z[0].push(x[i]);               // Add it to the nonordered part of the dropsort
                                     // Set last item to current item
  }                                  // Repeat
  return z                           // Return finished dropsort
}                                    // End function

Try it online!