30
\$\begingroup\$

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

\$\endgroup\$
5
  • 8
    \$\begingroup\$ I'm very surprised if this isn't a duplicate, but I don't have the time to check. Anyway, "built-in sorting functions" should be better defined. Can you use a function that indexes all values? [7 2 4 1] -> [4 2 3 1]. Also, can the CSV list be inside brackets? Also, the specific input format is very suitable for some languages, and bad for others. This makes input parsing a big part for some submissions, and unnecessary for others. \$\endgroup\$ Commented Apr 15, 2016 at 12:52
  • 1
    \$\begingroup\$ @StewieGriffin I've seen many sorting challenges, but none dealing with sorting just a basic integer list. There are many challenges that are easier for some languages, and much more difficult in others. \$\endgroup\$ Commented Apr 15, 2016 at 13:00
  • \$\begingroup\$ This is very similar, but has a O(Nlog(N)) restriction. \$\endgroup\$ Commented Apr 15, 2016 at 14:06
  • 3
    \$\begingroup\$ Very closely related to this question, but since some answers here (e.g. Dennis' range filtering) require the input to be integers I won't vote to close as dupe. \$\endgroup\$ Commented Apr 15, 2016 at 20:55
  • 1
    \$\begingroup\$ Relevant: youtube.com/user/AlgoRythmics/videos — An Youtube channel which teaches sorting algorithms through Hungarian dances! \$\endgroup\$
    – sergiol
    Commented Apr 30, 2017 at 12:05

58 Answers 58

1
2
2
\$\begingroup\$

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!

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ I guess that's a kind of en.wikipedia.org/wiki/Counting_sort. \$\endgroup\$ Commented Nov 26, 2017 at 4:48
  • \$\begingroup\$ @PeterCordes That was kinda the point \$\endgroup\$
    – anna328p
    Commented Nov 26, 2017 at 4:52
  • \$\begingroup\$ The question asks you to describe what kind of sort it is, so I thought it was useful to link to the well-known algorithm as well as just describing what it actually does. \$\endgroup\$ Commented Nov 26, 2017 at 4:54
  • \$\begingroup\$ True. Thanks @PeterCordes \$\endgroup\$
    – anna328p
    Commented Nov 26, 2017 at 4:55
1
\$\begingroup\$

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

Javascript 55 bytes

a=>[...a].map(b=>a.splice(a.indexOf(Math.min(...a)),1)
\$\endgroup\$
2
  • \$\begingroup\$ Doesn't work for me on Firefox; for the sample input I get [[-22], [-2], [4], [23], [36], [43], , , , , , ,]. \$\endgroup\$
    – Neil
    Commented May 19, 2016 at 19:33
  • \$\begingroup\$ @Neil yeah, missed something \$\endgroup\$
    – Bálint
    Commented May 19, 2016 at 19:44
1
\$\begingroup\$

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
\$\endgroup\$
3
  • 2
    \$\begingroup\$ you can save a couple of bytes by indenting s,a=..., while not a: and return l with a single space, and the contents of the while loop with a single tab because tab is considered deeper indentation than space. that will make this answer python2 only, though \$\endgroup\$ Commented May 20, 2016 at 0:16
  • \$\begingroup\$ @undergroundmonorail Thanks! \$\endgroup\$
    – Numeri
    Commented May 20, 2016 at 13:58
  • \$\begingroup\$ You can probably use while a<1, or if a is always 0 or 1, you can use while~-a \$\endgroup\$
    – mbomb007
    Commented Apr 25, 2017 at 20:46
1
\$\begingroup\$

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

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.

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

Perl 5, 65 bytes

Insertion sort subroutine:

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

Try it online!

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

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.

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

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.

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

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.

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

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ Won't this fail for negative integers in the array? \$\endgroup\$
    – Shaggy
    Commented Jul 4, 2023 at 23:33
  • \$\begingroup\$ @Shaggy This is accounted for via -Math.min(...a), which, for the case in which the smallest value is -5, would shift all values up by 5, ensuring this still works. \$\endgroup\$
    – ATaco
    Commented Jul 5, 2023 at 0:10
1
\$\begingroup\$

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

Vyxal, 14 bitsv1, 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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ I think you can do Ans→A \$\endgroup\$
    – MarcMush
    Commented Oct 7, 2023 at 17:31
1
\$\begingroup\$

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

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Haskell, 3332 bytes

import Data.Set
s=elems.fromList

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Japt -m, 9 bytes

M=Wk§M rm

Try it

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
1
2

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.