22
\$\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\$
  • 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\$ – Stewie Griffin Apr 15 '16 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\$ – Michelfrancis Bustillos Apr 15 '16 at 13:00
  • \$\begingroup\$ This is very similar, but has a O(Nlog(N)) restriction. \$\endgroup\$ – Nathan Merrill Apr 15 '16 at 14:06
  • 2
    \$\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\$ – Peter Taylor Apr 15 '16 at 20:55
  • \$\begingroup\$ Relevant: youtube.com/user/AlgoRythmics/videos — An Youtube channel which teaches sorting algorithms through Hungarian dances! \$\endgroup\$ – sergiol Apr 30 '17 at 12:05

46 Answers 46

2
\$\begingroup\$

Python 3, 53 bytes

lambda l:[i for i in range(min(l),max(l)+1)if i in l]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This is essentially a bucket sort, right? So it fails if the input doesn't fall in the range of the hash table size? Can that happen? \$\endgroup\$ – Jakob Aug 28 '17 at 0:02
  • \$\begingroup\$ @Jakob I don't think so? To me it's just a range between min and max values, filtered with the input list \$\endgroup\$ – ASCII-only Aug 28 '17 at 0:14
  • \$\begingroup\$ @ASCII-only: agreed. Filtering the range between min and max looks like an implementation of en.wikipedia.org/wiki/Counting_sort to me, because it's sort of like making a histogram. (Same as @Mendeleev's Ruby answer) \$\endgroup\$ – Peter Cordes Nov 26 '17 at 4:57
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\$
  • \$\begingroup\$ Doesn't work for me on Firefox; for the sample input I get [[-22], [-2], [4], [23], [36], [43], , , , , , ,]. \$\endgroup\$ – Neil May 19 '16 at 19:33
  • \$\begingroup\$ @Neil yeah, missed something \$\endgroup\$ – Bálint May 19 '16 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\$
  • 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\$ – undergroundmonorail May 20 '16 at 0:16
  • \$\begingroup\$ @undergroundmonorail Thanks! \$\endgroup\$ – Numeri May 20 '16 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 Apr 25 '17 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
\$\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\$

R, 47 bytes

implements bogosort.

function(l){while(is.unsorted(l))l=sample(l);l}

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
\$\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, 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\$
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
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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