Sort an Integer List

Question

The Challenge

It's quite simple really, sort a list of numbers.

Details

You must sort a list of numbers in ascending order, without using any built-in sorting functions/libraries/etc (i.e. list.sort() in Python).

Input/output can be done in any method you choose, as long as it is human readable.

Standard loopholes are disallowed as always.

Shortest code in bytes wins.

You must explain/list what sort method you used (Bubble, Insertion, Selection, etc.)

Input will not contain duplicates.

Sample Input/Output

Input: 99,-2,53,4,67,55,23,43,88,-22,36,45

Output: -22,-2,4,23,36,43,45,53,55,67,88,99

Note: A near direct opposite of Sort a List of Numbers

Answer 1

Java 7, 106 104 bytes

void a(int[]a){for(int b=a.length-1,d=0,c=0,e;d<b*b;c=++d%b)if(a[c]>a[c+1]){e=a[c];a[c++]=a[c];a[c]=e;}}

Here's a good ole bubble sort. The function parameter is modified in place so I don't have to return anything. Still trying to squeeze some bytes out of this so I can beat the java lambda that someone posted.

-1 byte thanks to Geobits for pointing out that normal swapping beats xor'ing
-1 byte thanks to Leaky Nun for pointing out that I can move all the int declarations into the for-loop

Try it online!

Answer 2

Ruby, 22 bytes

->a{[*a.min..a.max]&a}

Builds an array out of the range between the minimum and maximum elements of the input array. Returns the intersection between the two arrays.

Answer 3

Desmos, 99 80 bytes

-19 thanks to Aiden Chow!

Unfortuantely Desmos does not have great capabilities for my favorite sorting algorithm, so here is an implementation of counting sort!

m=A.min
r=[m...A.max]
f(A)=[r[∑_{n=m}^rA[A=n].length=i][1]fori=[1...A.length]]

Try it on Desmos!

How it works:

\$m\$ is just a shorthand for \$A.\operatorname{min}\$ to shave off a few bytes from the code. Note that we are referring to \$A\$ even when it is not defined in this context, but this still works due to some wacko variable scoping.

\$r\$ is also a shorthand for the range \$[m\dots A.\operatorname{max}]\$. This expression appears twice so we can also shave off yet a few more bytes with this.

Next comes the actual sorting procedure:

f(A)=[r[∑_{n=m}^rA[A=n].length=i][1]fori=[1...A.length]]
     [                              fori=[1...A.length]]  repeat for i∈[1,A.length]
      r[                        ]                         filter r
        ∑_{n=m}^r                                         sum from min to r
                 A[A=n].length                            # of occurrences of n
                              =i                          sum=i
                                 [1]                      take the first result 

Still doesn't make sense? Let's review the algorithm:

• counting sort: count the occurrences of each value and reassemble them in order
  • # of occurrences is always 0 or 1 since every element is distinct
• instead of reassembling, we construct the sorted array on the spot
  • how? figure out where each element should be
  • since we know the number of times each element occurs, we can add up the past occurrences to get the sorted index of the current element
  • now we just look for the element with the specified index (and repeat this for every index)

For example:

A = [ 3 2 9 5 ]

             i ->  1 2 3 4 5 6 7 8
             r = [ 2 3 4 5 6 7 8 9 ]
 A[A=i].length = [ 1 1 0 1 0 0 0 1 ]  number of occurrences
∑A[A=i].length = [ 1 2 2 3 3 3 3 4 ]  cumulative sum/new index

Now for each index \$i\$ in the final sorted array we look for the first item in \$r\$ for which \$\sum A[A=i].\operatorname{length}=i\$. This gives all the elements in the original list, but in sorted order.

Answer 4

Jolf, 13 bytes

Uses bogosort. Try it out here! Replace ⌂ with \x7f. Input is a comma-separated list of numbers like 5,3,2,4,1.

W⌂Z,k)ok Tk}k

Explanation:

W⌂Z,k)ok Tk}k
W    )         while
 ⌂Z,            !isSorted
    k            input {
      ok          k =
        _Tk        shuffle(k)
           }   }
            k  out k

Answer 5

Javascript 55 bytes

a=>[...a].map(b=>a.splice(a.indexOf(Math.min(...a)),1)

Answer 6

Python 2, 159

Implements bozosort (randomly swap two elements until the array is sorted).

It's not very efficient...

from random import randint as r
def b(l):
 s,a=len(l)-1,0
 while not a:
        c,d=r(0,s),r(0,s);l[d],l[c]=l[c],l[d];e,a=l[0],1
        for f in l:a,e=a*(f>=e),f
 return l

Answer 7

Tcl, 49: sleep sort

The examples so far aren't very consistent in how they take input, so this sorts command-line arguments. On particularly slow systems, where the foreach takes more than a millisecond, it might need three extra bytes (after ${x}0).

foreach x $argv {after $x puts $x}
vwait forever

Answer 8

SmileBASIC, 79 bytes

DEF S A
FOR Z=0TO I
FOR I=1TO LEN(A)-1SWAP A[I-(A[I-1]>A[I])],A[I]NEXT
NEXT
END

It's bubble sort but instead of checking to see if it's finished, it just assumes that every input is the worst case and does n^2 (actually n*(n+2)) iterations.

Answer 9

Perl 5, 65 bytes

Insertion sort subroutine:

sub r{map{$t=0;$_[$_]<$_[$t]&&($t=$_)for 0..$#_;splice@_,$t,1}@_}

Try it online!

Answer 10

Dodos, 75 bytes

	/
/
	/ s w
w
	h
	/ t
s
	s R
R
	t
	h
h
	t I q
q
	dot t
	dot
I
	I dip
t
	dab

Try it online!

Only support non negative integers. Terrible runtime, especially for large numbers.

---

Explanation

First, define t to be the tail of a list. (all elements except the first)

Given a list [x,y] where x<y, function I computes the incremental difference (with a 0 prepended), which is used in h (head of a list, by getting the sum of all elements, subtract by the sum of all elements except the first)

Function R reverses a list of 2 elements. (concatenate the tail and the head) Generally, it rotates the first element to the last.

s sorts a list of 2 elements. Generally, given a list, it find the least non negative n such that rotate the list left by n make the list less than itself Red.

/ sorts a list of arbitrarily many elements, by / the list' tail, and then / s the result.

Answer 11

Haskell, 97 bytes

s=f.map pure
a@(x:y)!b@(z:w)|x>z=z:a!w|0<1=x:y!b
a!b=a++b
d(x:y:z)=x!y:d z
d p=p
f[x]=x
f x=f$d x

Try it online!

A stable, incremental merge sort.

Answer 12

Pyth, 8 bytes

_ueg#G.p

Try it online!

• ueg#G.p:
  • u Repeatedly apply the following function to the input until the result stops changing.
  • .p: Generate all permutations of the current list
  • g#G:
    • #: Filter the list of permutations
    • g: On being greater than or equal to
    • G: The current list
  • e: Take the last permutation in the filtered list. This will only be the same as the current list if the filter only leaves behind one list, because the permutation function .p always puts its input first.

At this point, we have the maximum permutation of the input, which is in reverse sorted order. _ reverses that to give the sorted list.

---

Note that Pyth does not have an opposite of g - there is no less than or equal to builtin.

---

I wanted to see what the intermediate lists are when sorting with this method. Putting a newline at the end of the code prints all of the intermediate lists:

Try it online!

For the input [0,7,4,1,6,5,2,3], here's what the intermediate lists look like:

[0, 7, 4, 1, 6, 5, 2, 3]
[3, 2, 5, 6, 1, 4, 7, 0]
[7, 0, 4, 1, 6, 5, 2, 3]
[7, 3, 2, 5, 6, 1, 4, 0]
[7, 4, 0, 1, 6, 5, 2, 3]
[7, 5, 3, 2, 6, 1, 0, 4]
[7, 6, 4, 0, 1, 2, 3, 5]
[7, 6, 5, 3, 2, 1, 0, 4]
[7, 6, 5, 4, 0, 1, 2, 3]
[7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7]

Basically, what's happening is that at each step, the (reverse) sorted prefix stays, and then the last number larger than the front unsorted number is moved to the front of the unsorted region, and the rest of the unsorted region is reversed. It's like a low-quality selection sort with reversals thrown in for fun.

I think this runs in approximately O(n^2 n!) time - n! permutations, n comparisons each, and O(n) rounds (at most 2n, from what I can tell.

Answer 13

minigolf, 48 bytes

Implements insertion sort.

0,;i,:#1,;ns,s,n2,;:,n_T*+0s,,_1_,o_,n__n1+,;o__

Try it online!

Explanation

0,;         Begin from an empty `sorted` list
i,          For each item in input list:
  :#1,;       Duplicate, and wrap `sorted`'s length
              in a singleton list
              (that is to be used later in a 'fry' structure)

  ns          Push current foreach item, and swap it below the length
  ,           'Fry' the input list's length inside
              (accessed with n; singleton lists only loop once)

              Note: at this point the remaining items on the stack are the `sorted` list and the current item of the outer foreach loop.
    s           Swap outer foreach loop item below the `sorted` list
    ,           Foreach item in the sorted list:
      n           Push current foreach item in `sorted` list
      2,;         Pair (but reversed); to implement a conditional swap
                  if the pair happens to be in decreasing order at any point in our loop
      :           Duplicate it, to perform a conditional check
      ,n_         Dump the pair onto the stack
      T*+         Subtract them

      0s          Swap 0 underneath
      ,,_1_       Repeat n times: drop & push 1
                  So if the left item in the pair > right item in the pair,
                  We would definitely execute the next conditional 1 time.

      ,o_         Execute (0 pr 1 times) based on our previous value: reverse the pair
      ,n_         Dump the pair onto the stack
    _           End foreach loop over sorted list
                (We're now in our 'fry' structure.)
    n           Push the length of our previous `sorted` list
    1+          Add 1 to that
    ,;o         Wrap last n items into a list,
                and reverse it back into the right order
                (Now we have a new `sorted` list for the next iteration of the foreach loop.)
  _           End fry sequence
_           End foreach loop in input list

Answer 14

Javascript, 49 Bytes

a=>a.map(c=>setTimeout(alert,c-Math.min(...a),c))

Basic sleep sort implementation. Takes input as an array and outputs as alerts.

Answer 15

Thunno 2 M, 2 bytes

lṗ

Try it online!

Port of Adnan's 05AB1E answer.

Explanation

lṗ  # Implicit input
l   # Length of input
 ṗ  # Permutations with that length
    # Implicit output of minimum

Answer 16

Vyxal, 14 bits^v1, 1.75 bytes

⇧İ

Try it Online!

Grade up technically doesn't sort the list, but rather gives the position of the first minimum, followed by the position of the second most minimum, followed by the position of the third most minimum and so on.

Explained

⇧İ
⇧  # Grade up the list
 I # and index into the input

Answer 17

TI-Basic, 42 41 bytes

Ans→A
cumSum(seq(sum(Ans=I),I,min(Ans),max(Ans
min(ʟA)+seq(sum(Ans<I),I,1,dim(ʟA

Counting sort. Takes input in Ans. Fails if the range is greater than the list size limit.

---

45 44 bytes

Ans→A
While 0>min(ΔList(augment(Ans,{max(Ans
randIntNoRep(1,dim(Ans
seq(ʟA(Ans(I)),I,1,dim(Ans
End
Ans

Bogosort. Takes input in Ans. Only works on calculators where randIntNoRep( is supported. For lists with more than one element, you can replace augment(Ans,{max(Ans with Ans for -5 bytes.

---

63 bytes

Prompt A
For(I,1,dim(ʟA
For(J,I,dim(ʟA
ʟA(I→T
If Ans>ʟA(J:Then
ʟA(J→ʟA(I
T→ʟA(J
End
End
End
ʟA

Similar method to this answer, though I'm not sure if it's exactly bubble sort as the elements it compares aren't always adjacent.

---

72 71 bytes

Ans→A
For(I,1,dim(Ans)-1
min(Ans→ʟB(I
sum(not(cumSum(ʟA=Ans
seq(ʟA(I+(I>Ans)),I,1,dim(ʟA)-1→A
End
Ans(1→ʟB(I:ʟB

Selection sort. Takes input in Ans. For lists with more than one element, you can replace Ans(1→ʟB(I:ʟB with augment(ʟB,Ans for -6 bytes.

Answer 18

Julia, 58 29 bytes

r(A,B=[])=A>[] ? (push!(B,popat!(A,argmin(A)));r(A,B)) : B

!A=A.|>_->popat!(A,argmin(A))

Attempt This Online!

• an out-place selection sort
• shortened slightly considerably by @MarcMush

Answer 19

ReRegex, 78 bytes

(_+),-(_+)/-$2,$1/-(_+),-\1(_+)\b/-$1$2,-$1/(?<!-)(_+)(_+),\1\b/$1,$1$2/#input

Try it online!

Essentially a Parallel Bubble-sort. Takes input as Signed Unary. Much of the program is just edge-cases for signed integers, without them this is just:

Unsigned, 28 bytes

(_+)(_+),\1\b/$1,$1$2/#input

Try it online!

Answer 20

C#, 125 bytes

using System.Linq;x=>{for(int i=0;i<x.Count;i++){int temp=x.GetRange(i,x.Count-i).Min();x[x.IndexOf(temp)]=x[i];x[i]=temp;}};

It uses the selection sort. I don't need to return the sorted list, because in C# lists are reference types, so the variable only holds a reference to the actual object, and if I change the object from here, it'll be visible at other places, as described in this stackoverflow question.

Answer 21

Tcl, 160 bytes

set i 0
time {incr j;set x 0;while \$x<$i {if [lindex $L $i]<[lindex $L $x] {set L [lreplace [linsert $L $x [lindex $L $i]] $j $j]};incr x};incr i} [llength $L]

Try it online!

Without even thinking on a "standard" method, I implement it by using Insertion Sort.

Answer 22

Attache, 36 bytes

{If[#_,Min[_]'$[Remove[_,Min!_]],_]}

Try it online!

Selection sort. Recursively sorts the list by concatenating the minimum with the sorted removed list.

Answer 23

Haskell, 3332 bytes

import Data.Set
s=elems.fromList

Try it online!

Answer 24

Javascript

for(i=0;i<size;i++){for(j=i+1;j<size;j++){if(num[i]>num[j]){swap=num[j];num[j]=num[i];num[i]=swap;}}}for(i=0;i<size;i++)console.log(num[i])

Here's an implementation of bubble sort.

Answer 25

JavaScript, 42 bytes

a=>Object.keys(a.reduce((o,k)=>o[k]=o,{}))

Note: doesn't work for negative numbers. The iteration order of an object's keys are defined as such in the current spec, requiring that all numerical indexes are iterated in sorted numerical order first.

Answer 26

Japt -m, 9 bytes

M=Wk§M rm

Try it

Answer 27

C# (Visual C# Interactive Compiler), 77 bytes

a=>{for(int@i=0,t;++i<a.Count;)if((t=a[i-1])>a[i]){a[i-1]=a[i];a[i]=t;i=0;}};

Try it online!

Answer 28

Itr, 9 bytes

äRm«â-ÍÌ+

online-interpreter

Explanation

äRm«â-ÍÌ+  ; implicit input
ä          ; duplicate the input
 Rm«       ; get the smallest element
    â      ; push a copy of the element below the list
     -     ; subtract the smallest element from the list
      Í    ; create list with 1's at the positions given by the list
       Ì   ; get the positions of the ones (in ascending order)
        +  ; add back the minimum element