"Sort" by element duplication

Question

Inspired by one of many bugs I ran into while implementing selection sort in trilangle.

Given a non-empty list of non-negative integers, "sort" the list using the following procedure:

1. Find and output the smallest value in the list.
2. If the list only has one element, stop.
3. Recurse on a sublist:
   • If the last element in the list is the smallest, recurse on everything but the last value.
   • Otherwise, recurse on everything but the first value.

Your code doesn't have to follow this procedure exactly, as long as the result is the same.

Sample implementation in JS:

function* sort(arr) {
 if (arr.length === 1) {
 return yield arr[0];
 }
 const min = Math.min(...arr);
 yield min;
 if (min === arr.at(-1)) {
 arr.pop();
 yield* sort(arr);
 } else {
 const [, ...rest] = arr;
 yield* sort(rest);
 }
}

Some notes on the algorithm:

• The output will always contain the same number of elements as the input.
• The input may contain duplicates.
• Every element in the output is an element of the input, but they don't necessarily appear the same number of times.
• The elements of the output will be in nondecreasing order.

I/O

I/O defaults apply. Since I don't see this mentioned there, I will explicitly add the following rule:

You are allowed to implement this destructively. If taking the input by reference, the input does not have to have the same value once the procedure is completed. Note that I use this in the sample implementation above: I call .pop() without copying the array first.

Examples

[4, 3, 1, 2] => [1, 1, 1, 2]
[1, 2, 3, 4] => [1, 2, 3, 4]
[3, 2, 1, 0] => [0, 1, 2, 3]
[1, 2, 3, 1] => [1, 1, 2, 3]
[101, 103, 101, 105] => [101, 101, 101, 105]

Scoring

This is code-golf, so shortest program (per language) wins.

• Command Master: Can I take the input reversed?
• Command Master: Can I assume the input is always non-negative?
• Bbrk24: @CommandMaster I'm going to say no, you have to take the input in the specified order. And the question explicitly says "non-negative integers"

Answer 1

Vyxal, (削除) 15 (削除ここまで) (削除) 13 (削除ここまで) (削除) 10 (削除ここまで) 9 bytes

(:g...Ȯt=ǔḢ

Try it Online!

(削除) It's not every day I get to use recursion in a lambda (削除ここまで) Nevermind, I don't anymore.

-3 thanks to AndrovT

-1 by outputting items on newlines

Explained

(:g...Ȯt=ǔḢ
( # input length times:
 :g... # get the minimum of the top of the stack without popping and print that without popping
 Ȯt # push the tail of the item over the top of the stack
 = # does that equal the min?
 ǔ # rotate the list right that many times (once if tail is min [placing tail at front] or no times at all).
 Ḣ # Remove the head of the list

• AndrovT: 10 bytes, apparently checking if the last item is smallest manually is shorter
• lyxal: @AndrovT very big brain idea. Makes sense that all is shoter than getting min and tail from the same list.

Answer 2

Jelly, 10 bytes

ṖḊṂṄ=Ṫʋ`?ƒ

Try it online!

Full program, printing each element on its own line with a trailing newline.

I tried a couple printing-based solutions earlier (including some with Ṫ that also attempted to leverage it for Ṗ), but they all tied the pure solution. However, Jonathan Allan's golf to that gave me room to fit a print in with the extra space so long as it was also with dyadic chaining, which then required some creative wrestling with the loop quick of choice (at one point the program ended in μμ¿!) until it eventually inspired me to abuse ƒ.

 ƒ Reduce over the list, starting with the list, by:
 Ignoring the right argument,
 ? if
 Ṫʋ the last element (popped) from
 = ` the list of for each element in the list if it equals
 Ṃ the minimum
 Ṅ which is printed on its own line,
Ṗ then remove the last element,
 Ḋ else remove the first element.
 ƒ The end result is an empty list with no effect on the output.

Jelly, (削除) 12 (削除ここまで) 11 bytes

ṖḊ=ṂṪƊ?ƬṂ€Ṗ

Try it online!

-1 thanks to Jonathan Allan

Feels kinda clumsy, but may as well post it (削除) while it's the shortest (削除ここまで) :P

 Ƭ Repeat while unique, collecting all results:
 ? If
 Ṫ the last element (popped) from
 = Ɗ the list of, for each element of the input, if it's equal to
 Ṃ the minimum,
Ṗ then remove the last element,
 Ḋ else remove the first element.
 Ṃ€ Take the minimum of each result
 Ṗ and remove the last.

Answer 3

Nekomata, 10 bytes

ɪ{:Ɔ≥$tI}ṁ

Attempt This Online!

ɪ{:Ɔ≥$tI}ṁ
ɪ{ } Iterate the block until it fails
 I Choose the first non-failed result between the following two:
 :Ɔ≥$ If the last item is the smallest, remove it from the list; otherwise fail
 t Remove the first item of the list
 ṁ Take the minimum of each step of the iteration

---

Nekomata v0.1.0.0, 13 bytes

i{:↔C≥↔$t?∃}⊥

i{:↔C≥↔$t?∃}⊥
i{ } Iterate the block until it fails
 ?∃ Choose the first non-failed result between the following two:
 :↔C≥↔$ If the last item is the smallest, remove it from the list; otherwise fail
 t Remove the first item of the list
 ⊥ Take the minimum of each step of the iteration

• Bbrk24: This looks interesting, but I don't have Haskell set up on my machine, so I can't try it myself. Do you happen to have an online interpreter up yet? (No worries if not!)
• alephalpha: @Bbrk24 Sorry, not yet.

Answer 4

05AB1E, (削除) 10 (削除ここまで) 9 bytes

vDW=Qθ._¦

-1 byte being inspired by the rotate used in @lyxal's Vyxal answer.

Try it online or verify all test cases.

Original 10 bytes answer:

vDW=Êθ·<.$

Outputs the result on separated newlines.

Try it online or verify all test cases.

Explanation:

v # Loop over the (implicit) input-list, without using its values:
 D # Duplicate the current list
 # (which will be the implicit input-list in the first iteration)
 W # Push its minimum (without popping the list)
 = # Output it with trailing newline (without popping)
 Q # Check for each value in the list whether it's equal to this minimum
 θ # Pop and push the last item
 ._ # Rotate the list that many times towards the left
 ¦ # Remove the first item
vDW= # Same as above
 Ê # Check for each value in the list whether it's NOT equal to this minimum
 θ # Pop and push the last item
 · # Double it
 < # Decrease it by 1
 .$ # Remove that many leading items from the list
 # (1 will remove the first item; -1 will remove the last item)

Answer 5

JavaScript (ES6), 65 bytes

f=a=>a+a?[m=Math.min(...b=[...a]),...f(b.pop()^m?a.slice(1):b)]:a

Try it online!

Commented

f = a => // recursive function taking the input array a[]
a + a ? // if a[] is not empty:
 [ // append ...
 m = Math.min( // ... m, which is the minimum value in a[]
 ...b = [...a] // define b[] as a copy of a[]
 ), //
 ...f( // append the result of a recursive call:
 b.pop() // remove the last element from b[]
 ^ m ? // if it's not equal to the minimum:
 a.slice(1) // pass a[] without the first element
 : // else:
 b // pass b[] (i.e. a[] without the last element)
 ) // end of recursive call
 ] //
: // else:
 a // stop

---

JavaScript (ES13), 64 bytes

Suggested by @tsh.

f=a=>a+a?[m=Math.min(...a),...f(a,a.splice((a.at(-1)>m)-1,1))]:a

Attempt This Online!

• Kevin Cruijssen: I was confused by the ...b=[...a] for a moment, but I now see the b=[...a] is to define the copy, and the leading ... is for the Math.min. Didn't knew this was possible without parenthesis (...(b=a[...])). :) Nice answer btw!
• Unmitigated: @KevinCruijssen You can also do things like [...condition ? [] : [1,2,3]]. You actually rarely need brackets in these cases.
• tsh: f=a=>a+a?[m=Math.min(...a),...f(a,a.splice((a.at(-1)>m)-1,1))]:a

Answer 6

PARI/GP, 57 bytes

f(a)=if(#a,concat(m=vecmin(a),f(a[^if(m-a[#a],1,#a)])),a)

Attempt This Online!

Answer 7

Charcoal, 25 bytes

Wθ«⟦I⌊θ⟧≔⎇=↨θ0⌊θ...θ⊖LθΦθλθ

Try it online! Link is to verbose version of code. Explanation:

Wθ«

Repeat until the list is empty.

⟦I⌊θ⟧

Output its minimum.

≔⎇=↨θ0⌊θ...θ⊖LθΦθλθ

Remove the last or first element as appropriate.

Answer 8

Excel (ms365), 153 bytes

enter image description here - enter image description here - enter image description here - enter image description here - enter image description here

With data in A1:A4, formula in B1:

=TOCOL(BYCOL(REDUCE(A1:A4,A1:A3,LAMBDA(x,y,LET(z,TOCOL(TAKE(x,,-1),2),HSTACK(x,IF(TAKE(z,-1)=MIN(z),DROP(z,-1),DROP(z,1)))))),LAMBDA(a,MIN(TOCOL(a,2)))))

• Bbrk24: If I wanted to give a longer input, would I only have to change the A4 near the start of the formula, or is there more to it?
• JvdV: The only changes are A1:A4,A1:A3. Note that the A3 reference is one below the previous A4 reference @Bbrk24
• Jos Woolley: Maybe the part IF(TAKE(z,-1)=MIN(z),DROP(z,-1),DROP(z,1)) could be abbreviated to DROP(z,-1^(TAKE(z,-1)=MIN(z)))?
• JvdV: I've been playing with these constructs as well however it appears I couldn't get this to work inside DROP(). Could you? @JosWoolley
• Jos Woolley: Hmmm. Works for my answer but not yours. Must be something buggy to do with its position within the LAMBDA/LET construction.

Answer 9

R, (削除) 68 (削除ここまで) (削除) 63 (削除ここまで) 57 bytes

f=function(l)if(L<-sum(l|1))c(m<-min(l),f(l[-L^!l[L]>m]))

Try it online!

-5 bytes thanks to pajonk. 50 bytes if using newer versions of R.

• pajonk: I think returning empty list in the if is unnecessary: -5 bytes.
• Giuseppe: @pajonk ah, yes, you're right.

Answer 10

Haskell + hgl, 25 bytes

uue$mn-<(nt?.tl~<gj*=*mn)

Explanation

This answer is based around the uue builtin, which has the type:

uue :: (List a -> (b, List a)) -> List a -> List b

This is a bit complex but it basically describes the recursion scheme we want, it accepts a function which removes a value from a list, and repeatedly applies the function until the list is empty collecting the results in a list.

With this all we have to do is build a function which takes a list and "removes" the proper value. Getting the value itself is really easy, it's the minimum, so we can just use mn. We just have to build the list itself. nt removes the last element from a list and tl removes the first. We combine them with the ternary (?.) to make nt?.tl which accepts a boolean and a list and removes the last if true and the first otherwise. Then we make gj*=*mn which takes a list and compares if the minimum mn and the last gj are equal. We combine these with (~<) to thread their arguments together, to build

nt?.tl~<gj*=*mn

Which removes an element based on the logic described in the question.

To finish this off we use the fanout (-<) to combine the parts int a single function emitting a tuple, and feed that to uue.

Reflection

This is pretty good, the logic in the question itself is pretty messy, and it feels like this captures it pretty efficiently. But I'm seeing a few things that could be improved.

• I could pre-compose uue and variants with a fanout. This can't be done with every unfolding function, but it would save a bunch of bytes here, and has reusability.

  uef mn$nt?.tl~<gj*=*mn
  

• ixu could do with a version pre-composed with ø. i.e. an "interate until empty" function. This would save 1 byte:

  mn<<ixe(nt?.tl~<gj*=*mn)
  

  While I'm at that I might as well add other variants, like ixz for "iterate until zero".

Answer 11

Python, 53 bytes

f=lambda l:l and[m:=min(l)]+f(l[l[-1]>m:][:len(l)-1])

Attempt This Online!

Find the minimum. Remove the first element, or not, as appropriate; then take the first n−1 elements where n is the original number of elements, which removes the last element if the first wasn't removed. Call recursively.

Answer 12

Swift 5.6, 96 bytes

func f(x:[Int])->[Int]{x.min().map{[0ドル]+f(x:0ドル==x.last ?x.dropLast():[_](x.dropFirst()))} ?? []}

Try it on SwiftFiddle

It's not often you see Optional.map(_:) used in real-world code, since it's easily confused with other operations of the same name (i.e. Array.map(_:)).

Ungolfed:

func f(_ arr: [Int]) -> [Int] {
 return arr.min()
 .map { min in
 [min] + f(
 arr.last == min
 ? arr.dropLast()
 : Array(arr.dropFirst()) // dropFirst is lazy by default
 )
 } ?? []
}

Or, written without .map:

func f(_ arr: [Int]) -> [Int] {
 if let min = arr.min() {
 return [min] + f(
 arr.last == min
 ? arr.dropLast()
 : Array(arr.dropFirst())
 )
 } else {
 return []
 }
}

Answer 13

Arturo, 63 bytes

f:$[a][([]=a)?->a[m:min a@[m]++f(m=last a)?->chop a->drop a 1]]

Try it

Answer 14

Pip, 19 bytes

WgIg@v=PMNgDQgELPOg

Takes input as multiple command-line arguments. Attempt This Online!

Explanation

I was expecting to use recursion for this, but a plain old while loop ended up shorter.

WgIg@v=PMNgDQgELPOg
 ; g is list of command-line args; v is -1 (implicit)
Wg ; Loop while g is not empty:
 I ; If
 MNg ; Minimum of g
 P ; (Print that value)
 = ; Is equal to
 g@v ; Last element of g
 ; Then
 DQg ; Remove last element of g
 EL ; Else
 POg ; Remove first element of g

Answer 15

Go, (削除) 166 (削除ここまで) 160 bytes

func f(I[]int)[]int{m,L,k:=I[0],len(I),I
if L<2{return I}
for _,e:=range I{if e<m{m=e}}
if m==I[L-1]{k=f(I[:L-1])}else{k=f(I[1:])}
return append([]int{m},k...)}

Attempt This Online!

A quick-and-dirty port of the sample implementation.

Changelog:

• L==1 -> L<2, return I[0:1] -> return I: -5 bytes

• Bbrk24: I don't think the [0:1] on the second line is necessary at all, and the fact that the input is non-empty means L==1 could be L<2. There's probably better ways to shorten it, but I don't know Go.
• bigyihsuan: [0:1] because just [0] is an int, vs return type []int
• Bbrk24: If the list only has one element, why can't you just return I?
• bigyihsuan: that's very true

Answer 16

Julia 1.0, 41 bytes

!l=!l[(2:end).-(l[end]==@show min(l...))]

Try it online!

I interpreted "1. Find and output the smallest value in the list." as "print the value with garbage around it", hopefully that's acceptable. Also ends with an error. Otherwise, cleaner version below

Julia 1.0, 55 bytes

!l=l>[] ? [(m=min(l...););!l[(2:end).-(l[end]==m)]] : l

Try it online!

Clean version (returns the "sorted" list)

Answer 17

Excel, 136 bytes

Define g in Name Manager as:

=LAMBDA(a,
 LET(
 b,TAKE(a,-1),
 c,MIN(a),
 d,DROP(a,-1^(c=b)),
 e,MIN(d),
 IF(COUNT(d),VSTACK(e,g(d)))
 )
)

Then, within the worksheet:

=LET(f,A1:A4,VSTACK(MIN(f),DROP(g(f),-1)))

Assumes data in A1:A4.

• Bbrk24: How did you get 136? I count 192 as written, or 135 without whitespace.
• Jos Woolley: Whitespace was included only for easy of reading. If it's forbidden by the forum rules I'll gladly remove. I counted the single-letter definition for g as an extra byte.
• Bbrk24: Adding whitespace certainly isn't forbidden, but I thought you have to count any whitespace you do use, so it's beneficial to remove any you don't need. Counting the name of "g" makes sense.

Answer 18

Pyth, 13 bytes

#=?qeQ
hSQPQt

Try it online!

Explanation

#=?qeQhSQPQtQ # implicitly add Q
 # implicitly assign Q = eval(input())
# # repeat until error
 = # assign to Q
 ?qeQhSQ # if the last element of Q equals the minimum element of Q (min element is printed here by newline)
 PQ # all but the last element of Q
 tQ # else all but the first element of Q

Answer 19

as long as the numbers are within a small range, like [0, 10^8), one could do ::::

 echo '1,1,3,101,2,2,2,101,103,4,3,3,4,105,1,3,0,2,1,1' | 

 mawk '
 function ______(__,___,_,____) {
 for(_ in __) break
 if (length(__) <= (_+=_^=NF=FS=OFS="")) { 
 if (+__[___=_--]<+__[_]) {
 __[_]=__[___] substr("",
 __[___]=__[_])
 } return } _=+(____=" ")
 for(___ in __) { !+(_=__[___]) ? ($!_=(_)____$!_) : $_=$_(____)_ } 
 return split($(_<_),__,NF=FS=OFS=____) 
 } BEGIN { CONVFMT = "%.250g" 
 ORS = "," } { printf("\n [ %s%.0s ]\n\n [ ",
 $_, split($_,__,",")______(__)) 
 for(___ = length(__); ++_<___;) print __[_]
 printf("%s ]\n\n", __[___]) }'

 [ 1,1,3,101,2,2,2,101,103,4,3,3,4,105,1,3,0,2,1,1 ]
 [ 0,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,101,101,103,105 ]

instead of doing any sort of comparisons, it's what I would call "NF-sort" - it's essentially like a hybrid between counting sort and pigeonhole (aka bucket) sort,

e.g. right before the last step in the function,

101ドル == "101 101" - 2 copies of the string "101"

although the code isn't short at all, it's a purely linear algorithm (aka O(n)) since no comparisons, nested loops, or recursions are needed other than for the special case of "0", which are prepended at 1ドル instead.

• Bbrk24: The language I originally did this in has the integer limit of 2^23-1, so well within 10^8. Neat that you managed to do it in O(n), but given that this is shortest code and not best complexity, I don’t expect this answer to be too well received.
• RARE Kpop Manifesto: @Bbrk24 : it's quote-and-quote """"O(n)"""" with implied cheating since it leverages the fact awk reconstructs 0ドル sequentially, something that's "free" to this code but still very much carries a hidden cost that's hard to substantiate (or just call it O( n log n ) assuming their internal sorting isn't that bad ) ps : if you're bored, that integer limit can be rephrased as :::::::::::::::::::::::::::::::: ::::::::::::::::::; 2 ^ ( 32 - 3^2 ) - 3 + 2