20
\$\begingroup\$

Given a list of Integers greater than zero, Sort each of the unique values in ascending order, then repeat the process on the remaining duplicate values and append.

Example:

[1,5,2,2,8,3,5,2,9] ==> [1,2,3,5,8,9,2,5,2]
[8,5] ==> [5,8]
[2,2,2] ==> [2,2,2]
\$\endgroup\$
6
  • 13
    \$\begingroup\$ You should add more test inputs, including "corner" cases such as [4 4 4] and [8 5], as well as [] if the empty input need to be handled \$\endgroup\$
    – Luis Mendo
    Dec 12, 2023 at 23:43
  • \$\begingroup\$ Closely related: Simulate Round Robin Scheduling \$\endgroup\$
    – Bubbler
    Dec 13, 2023 at 4:37
  • 1
    \$\begingroup\$ added extra cases \$\endgroup\$
    – pacman256
    Dec 13, 2023 at 15:13
  • 3
    \$\begingroup\$ I read this first as cynically sort a list, and was really curious. Still am, but in a different way. \$\endgroup\$
    – Scot
    Dec 13, 2023 at 23:16
  • 1
    \$\begingroup\$ @DomHastings yeah, i was just lazy typing this out \$\endgroup\$
    – pacman256
    Dec 22, 2023 at 16:30

32 Answers 32

10
\$\begingroup\$

Haskell, 44 bytes

import Data.List
concat.transpose.group.sort

Try it online! (has an extra 2 bytes for f=)

\$\endgroup\$
8
\$\begingroup\$

Jelly, 5 bytes

ṢŒgZF

Try it online!

A monadic link taking an unsorted list of integers and returning the list sorted as described.

Explanation

Ṣ     | Sort
 Œg   | Group runs of identical digits together
   Z  | Transpose
    F | Flatten
\$\endgroup\$
7
\$\begingroup\$

Uiua, 11 bytes

▽≠0.♭⍉⬚0⊕∘.

Try it!

  • . duplicate input

enter image description here

  • ⬚0⊕∘ group by identity, filling with zeros

enter image description here

  • transpose

enter image description here

  • deshape

enter image description here

  • ▽≠0. keep non-zeros

enter image description here

\$\endgroup\$
7
\$\begingroup\$

Vyxal, 28 bitsv2, 3.5 bytes

sĠ∩f

Try it Online!

Bitstring:

1000100001100101100111101000

Port of the Uiua answer except without the 0 filling because it's not needed here. And they say having a fixed array model is a good thing! :p

Explained

sĠ∩f­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌­
s     # ‎⁡Sort the input
 Ġ    # ‎⁢Group on consecutive items
  ∩   # ‎⁣Transpose
   f  # ‎⁤and flatten
💎

Created with the help of Luminespire.

\$\endgroup\$
6
\$\begingroup\$

Nekomata + -1, 5 bytes

oOᵐůj

Attempt This Online!

oOᵐůj
o       Sort
 O      Find a set partition
  ᵐů    such that no part contains duplicates
    j   Join

The flag -1 finds only the first solution.

The built-in O (\setPartition) uses the following algorithm (taken from Curry's Combinatorial package), which ensures that the first solution is exactly the one we want:

partition    :: [a] -> [[a]]
partition [] = []
partition (x:xs) = insert x (partition xs)
    where insert e [] = [[e]]
          insert e (y:ys) = ((e:y):ys) ? (y:insert e ys)
\$\endgroup\$
6
\$\begingroup\$

Jelly, 4 bytes

ĠZFị

A monadic Link that accepts a list and yields the "sorted" list.

Try it online!

How?

ĠZFị - Link: list A            e.g. [8,8,8,3,7,7,3,3]
Ġ    - Group indices of A by value  [[4,7,8],[5,6],[1,2,3]]
 Z   - transpose                    [[4,5,1],[7,6,2],[8,3]]
  F  - flatten                      [4,5,1,7,6,2,8,3]
   ị - index into A                 [3,7,8,3,7,8,3,8]
\$\endgroup\$
5
\$\begingroup\$

R, 40 bytes

function(x)x[order(ave(!x,x,FUN=seq),x)]

Try it online!

Shorter to use order than split.

R, 55 bytes

function(x,y=sort(x))unlist(split(y,ave(!y,y,FUN=seq)))

Try it online!

Noticed the split and ave characterization about 2 minutes after posting the longer answer below. Rough R equivalent to the Jelly answer.

R, 73 bytes

f=function(x,o={},d=duplicated(x))'if'(sum(x),f(x[d],c(o,sort(x[!d]))),o)

Try it online!

Naive implementation: sort unique values and recurse on remainder, appending as you go. Probably there's a shorter way.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 62 52 bytes

import Data.List
f[]=[]
f x|z<-sort$nub x=z++f(x\\z)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

J, 13 bytes

/:],.~1#.]=]\

Try it online!

  • /: Sort by
  • 1#.]=]\ Running sum count of each unique value first
  • ,.~ Followed by
  • ] The original value

That is, we form pairs <running count for this value, this value> and sort by those pairs.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 45 bytes

Expects an Uint16Array filled with unsigned bytes and returns a Buffer.

a=>Buffer(a.map(o=v=>o[v]=o[v]+256|v).sort())

Try it online!

Commented

a =>             // a[] = input Uint16Array
Buffer(          // coerce to bytes:
  a.map(o =      //   o = object to keep track of the number
                 //       of times each value appears
  v =>           //   for each value v in a[]:
    o[v] =       //     update o[v]:
      o[v] + 256 //       increment the high byte
                 //       (no effect on the 1st iteration)
      | v        //       use v as the low byte
  )              //   end of map()
  .sort()        //   sort the 16-bit values
)                // end of Buffer()

JavaScript (ES6), 51 bytes

Expects an Uint16Array filled with unsigned bytes and returns an array in the same format.

(This version could be updated to support larger integers at the cost of a few extra bytes.)

a=>a.map(o=v=>o[v]=o[v]+256|v).sort().map(v=>v&255)

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ I would think using bytes is only an option if the language only supports such values. Especially given your input can support larger integers and then gives incorrect output. \$\endgroup\$ Dec 13, 2023 at 12:21
  • 1
    \$\begingroup\$ @JonathanAllan That's a fair point but I honestly don't really know what the exact rule is. JS can handle IEEE 754 double-precision numbers, or 32-bit signed integers for bitwise operations, or 8-bit, 16-bit,etc. signed / unsigned integers in typed arrays, or integers of any size with BigInts. Yet I don't think there's any obligation to use BigInts in all answers to get the maximum available integer size. \$\endgroup\$
    – Arnauld
    Dec 13, 2023 at 14:14
  • \$\begingroup\$ You seem to be using "unsigned bytes" to save bytes of code, but it means you have to limit the domain of the content of an array which naturally would contain unsigned 16-bit integers. The problem domain is positive integers and this code fails if I don't follow your instruction that I must limit the maximal value, yet this is not a limitation of the type or the language (or is it?). \$\endgroup\$ Dec 13, 2023 at 19:33
  • 1
    \$\begingroup\$ @JonathanAllan I think this should be discussed in Meta -- and that's an interesting discussion indeed. If the input n is a Number and my code does something as common as n+3&1 instead of (n+3)%2 to save two bytes, it would also limit the domain to 32-bit integers although it could have worked in the full Number range \$[-2^{53}+1 \dots 2^{53}-1]\$. So it seems like we need a clear rule here. \$\endgroup\$
    – Arnauld
    Dec 13, 2023 at 20:08
4
\$\begingroup\$

BQN, 6 bytes

⍋∘⊒⊸⊏∧

Try it online!

Or alternatively, ∾⊒⊸⊔∘∧

\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 38 bytes

mO$`(.+)(?<=((^\1$)|.|¶)*)
$#3$*1,$&$*

Try it online! Takes input on separate lines but link splits on commas for convenience. Explanation: Sorts each value by a key made up of its occurrence count and value, expressed in unary.

@TwiNight's idea of sorting twice (since the sort is stable) saves 10 bytes, since the second sort doesn't have to guard against extraneous matches:

O#`
O#$`(.+)(?<=(¶?\1)+)
$#2

Try it online! Takes input on separate lines but link splits on commas for convenience.

Note that each link can be turned into a test suite by prefixing %( to the header.

\$\endgroup\$
3
\$\begingroup\$

BQN (CBQN), 10 bytes

{∾∧¨𝕩⊔˜⊒𝕩}

Attempt This Online!

\$\endgroup\$
3
\$\begingroup\$

Perl 5 -MList::Util=uniq -a, 59 bytes

map$t{$_}++,@F;1while@F=grep{say;--$t{$_}}sort{$a-$b}uniq@F

Try it online!

\$\endgroup\$
3
3
\$\begingroup\$

Retina, 30 26 bytes

N`
N$`(.+)(?<=(¶?\1)+)
$#2

Attempt This Online!

Edit: -4 bytes thanks to Neil, by changing I/O format

Input and output are newline-separated decimals.

First sort normally, then sort (stably) again using the occurrence index

\$\endgroup\$
1
  • \$\begingroup\$ You could save 4 bytes by taking input on separate lines. Try it online! \$\endgroup\$
    – Neil
    Dec 13, 2023 at 8:58
3
\$\begingroup\$

Ruby, 41 bytes

->l,*r{l.sort_by{|x|[(r<<x).count(x),x]}}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Classic), 15 bytes

-2 bytes thanks to att.

{0~⍨,⍉⊣¨⌸⍵[⍋⍵]}

Try it online!

Explanation

{0~⍨,⍉⊣¨⌸⍵[⍋⍵]}­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏‏​⁡⁠⁡‌⁣​‎⁠⁠⁠⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌­
{                 }  # ‎⁡dfn
           ⍵[⍋⍵]   # ‎⁢sort
       ⊣¨⌸          # ‎⁢⁢groups into matrix, padding with zeros
     ⍉              # ‎⁢⁣transpose
    ,                # ‎⁢⁤ravel (flatten)
 0~⍨                 # ‎⁣⁡remove zeros
💎

Created with the help of Luminespire.

I think that using a dfn rather than tacit is probably shorter here, since we are applying a bunch of monadic functions, and sorting is no shorter in tacit: ⊂∘⍋⌷⊢.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ ⍴⍨∘⍴⌸ -> ⊣¨⌸ \$\endgroup\$
    – att
    Dec 13, 2023 at 21:11
  • \$\begingroup\$ @att Thanks! I was trying to think of a way to "reshape into the shape of" but that is a very interesting solution. \$\endgroup\$
    – Tbw
    Dec 14, 2023 at 9:30
3
\$\begingroup\$

PowerShell Core, 73 bytes

$f={param($a)if($a){($g=$a|group).Name
&$f($g|%{,$_.Name*($_.Count-1)})}}

Try it online!

Recursive function
Takes an array as a parameter
Returns an array

Explanation

param($a)                    # The array in variable $a
if($a){...}                  # If the array is empty, do nothing, otherwise:
($g=$a|group).Name           # Group the numbers in the array, store the groups in $g and return the unique elements sorted
$g|%{,$_.Name*($_.Count-1)}  # From the groups, rebuild a list with one element less for each elements
&$f(...)                     # Recursively invoke the function on the rebuilt list
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 5 bytes

oḅz₁c

Try it online!

Explanation

o        Sort in ascending order
 ḅ       Group consecutive elements together
  z₁     Zip without cycling
    c    Concatenate
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 24 bytes

UMθ⟦№…θκιι⟧W⁻θυ⊞υ⌊ιIEυ⊟ι

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

UMθ⟦№…θκιι⟧

Replace each value with a tuple of its occurrence index and value.

W⁻θυ⊞υ⌊ι

Sort the tuples into order.

IEυ⊟ι

Output the sorted values.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 5 bytes

{γζ˜þ

Try it online.

Explanation:

{      # Sort the (implicit) input-list
 γ     # Group it into equal adjacent values
  ζ    # Zip/transpose; swapping rows/columns,
       # using " " implicitly as filler for unequal length lists
   ˜   # Flatten this list of lists
    þ  # Remove all " " by only keeping integers
       # (after which the resulting list is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

APL(NARS), 23 chars

{0≥≢⍵:⍬⋄a[⍋a],∇⍵∼⍦a←∪⍵}

use:

  {0≥≢⍵:⍬⋄a[⍋a],∇⍵∼⍦a←∪⍵}1 5 2 2 8 3 5 2 9
┌9─────────────────┐
│ 1 2 3 5 8 9 2 5 2│
└~─────────────────┘

zilde has to be as void set for all the types

\$\endgroup\$
2
\$\begingroup\$

APL+WIN, 30 bytes

Prompts for list of integers:

(,⍉⊃(⌈/¨⍴¨n)↑¨n←n⊂n←m[⍋m←⎕])~0

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 62 bytes

a=>a.map(t=$=>[t[$]=9+t[$]||Array($)+t,$]).sort().map(x=>x[1])

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Japt, 5 bytes

ü Õcf

Try it

ü Õcf     :Implicit input of array
ü         :Group & sort by value
  Õ       :Transpose
   c      :Flatten after
    f     :  Filtering (to remove null values)
\$\endgroup\$
2
\$\begingroup\$

Haskell + hgl, 11 bytes

cx<tx<sr<bg

Attempt This Online!

Alternative

cx<tx<gr<sr

Attempt This Online!

Explanation

  • bg group the input into bags of equal elements
  • sr sort the bags by value
  • tx transpose
  • cx concat

Reflection

There are a couple of ways hgl could be improved I'm seeing here:

  • There are two options for how to sort the bags in bg

    • Sort by how many items are in a bag
    • Sort by how early the earliest item appears

    Neither of these is really helpful in this case. It might be nice to have a case function to sort by the value in the bags which would save us here, but really we need an option for the user to specify how to sort (wouldn't help here since sr<bg is already quite short).

  • There's probably an argument to be made to have a combined cx<tx. I can see that being used in more places than just here.

\$\endgroup\$
2
\$\begingroup\$

Python, 53 bytes

f=lambda L:[*map(L.remove,x:={*L})]and sorted(x)+f(L)

Attempt This Online!

Straight-forward method used by many other answers previously: Pick, sort and remove uniques and start over.

\$\endgroup\$
1
\$\begingroup\$

Scala 3, 118 bytes

A Port of @matteo_c's Haskell answer in Scala.


Golfed version. Attempt This Online!

_ match{case Nil=>Nil;case x=>x.sorted.distinct++f(x.sorted.groupBy(identity).mapValues(_.tail).values.flatten.toSeq)}

Ungolfed version. Attempt This Online!

object Main extends App {
  def f(lst: List[Int]): List[Int] = lst match {
    case Nil => Nil
    case x =>
      val sorted = x.sorted
      val distinctElements = sorted.distinct
      val groupedElements = sorted.groupBy(identity).mapValues(_.tail).values.flatten.toList
      distinctElements ++ f(groupedElements)
  }

  val testcases = List(
    (List(1, 5, 2, 2, 8, 3, 5, 2, 9), List(1, 2, 3, 5, 8, 9, 2, 5, 2)),
    (List(4, 4, 4), List(4, 4, 4)),
    (List(8, 5), List(5, 8)),
    (List[Int](), List[Int]())
  )

  testcases.foreach { case (input, expectedOutput) =>
    assert(f(input) == expectedOutput, s"Test failed for input: $input")
  }

  println("All tests passed!")
}
\$\endgroup\$
1
\$\begingroup\$

Desmos, 63 bytes

f(l)=sort(l,[l[1...i][l=l[i]].countfori=[1...l.count]]2l.max+l)

Port of some other answers which sort by running occurrence count and value of the corresponding element.

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
1
\$\begingroup\$

Q, 51 Bytes

{$[x~();x;asc[key g],.z.s x asc(,/)_[1]'[g:(=:)x]]}

The above function takes an implicit parameter, x, and:

  • returns x if it is empty
  • otherwise, groups the items in x using K function =: which is equivalent to Q function group. This yields a dictionary where each key is a unique items in x and each value is a list of the indexes at which the item occurs in x
  • and returns:
  1. the sorted, unique items in x. The unique items are found by taking the keys of the group dictionary

concatenated with

  1. the results of a recursive call to the function (.z.s) with the remaining items as the parameter. The remaining items are found by dropping the first index from each list in the group dictionary values (using _[1]'), merging the lists (using ,/), and grabbing the items at those indices from x
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.