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

23
\$\begingroup\$

05AB1E, 2 bytes

Code:

ϧ

Same algorithm as the Jelly answer. Computes all permutations of the input and pops out the smallest one.

Try it online!


A more efficient method is:

E[ß,Ž

Performs selection sort. Uses CP-1252 encoding.

Try it online!

\$\endgroup\$
  • 6
    \$\begingroup\$ Accepting this temporarily as I don't see anyone getting less than 2. \$\endgroup\$ – Michelfrancis Bustillos Apr 15 '16 at 14:30
  • 6
    \$\begingroup\$ @MichelfrancisBustillos well, if they did, it would be a builtin, wouldn't it? \$\endgroup\$ – Destructible Lemon Aug 22 '16 at 7:15
  • \$\begingroup\$ I just looked at 05AB1E/Base a minute ago, and then I looked at this. Coincidence? \$\endgroup\$ – facepalm42 Jul 11 at 8:52
17
\$\begingroup\$

Jelly, 3 bytes

Œ!Ṃ

This generates all permutations of the input list, then selects the lexographically smallest permutation. Very efficient.

Credits to @Adnan who had the same idea independently.

Try it online!


Jelly, 4 bytes

ṂrṀf

This builds the range from the minimum of the list to the maximum of the list, then discards the range elements not present in the original list. This is technically a bucket sort, with very small buckets. I'm not aware of a name for this specific variant.

Try it online!

How it works

ṂrṀf  Main link. Argument: A (list/comma-separated string)

Ṃ     Compute the minimum of A.
  Ṁ   Compute the maximum of A.
 r    Yield the inclusive range from the minimum to the maximum.
   f  Filter the range by presence in A.
\$\endgroup\$
  • \$\begingroup\$ O(very). Uses much sort. \$\endgroup\$ – mbomb007 Apr 15 '16 at 19:14
  • 22
    \$\begingroup\$ So O. Very uses. Much sort. Amaze! (Sorry, what?) \$\endgroup\$ – Dennis Apr 15 '16 at 19:19
  • \$\begingroup\$ I'm not great at complexity of algorithms, would this be O(n!)? \$\endgroup\$ – FlipTack Jan 28 '17 at 21:48
  • 2
    \$\begingroup\$ @FlipTack Neither am I. Probably a bit higher, since there are n! arrays of length n. \$\endgroup\$ – Dennis Jan 28 '17 at 22:15
  • 1
    \$\begingroup\$ Just selecting the smallest lexographically is O(n*n!) since each of the n! arrays must be compared sequentially, and lexographical comparison is O(n). Generation can be done in O(n*n!) as well if done efficiently so I would bet the algorithm is only O(n*n!) if well implemented \$\endgroup\$ – PunPun1000 Aug 28 '17 at 18:59
12
\$\begingroup\$

Python, 46 45 bytes

lambda l:[l.pop(l.index(min(l)))for _ in 1*l]

Simple selection sort.

\$\endgroup\$
  • 4
    \$\begingroup\$ l[:] could be 1*l \$\endgroup\$ – feersum Apr 16 '16 at 6:18
9
\$\begingroup\$

Brachylog, 12 7 bytes

p.'(s>)

This uses permutation sort, which is obviously terrible, but hey it's shorter than Pyth!

Explanation

p.       Unifies the output with a permutation of the input
  '(  )  True if what's inside the parentheses cannot be proven, else backtrack and
         try with another permutation of the input.
    s    Take an ordered subset from the output
     >   True if the first element is bigger than the second (hence not sorted)
         We don't need to check that the subset is 2 elements long because > will be false
         for inputs that are not 2 elements long anyway
\$\endgroup\$
9
\$\begingroup\$

Haskell, 38 bytes

h%t|(a,b)<-span(<h)t=a++h:b
foldr(%)[]

The binary function % insert a new element h into a sorted list t by partitioning t into a prefix a of elements <h and a suffix b of elements >h, and sticks in h between them.

The operation foldr(%)[] then builds up a sorted list from empty by repeatedly inserting elements from the input list.

This is one byte shorter than the direct recursive implementation

f(h:t)|(a,b)<-span(<h)$f t=a++h:b
f x=x

Another strategy for 41 bytes:

f[]=[]
f l|x<-minimum l=x:f(filter(/=x)l)
\$\endgroup\$
8
\$\begingroup\$

JavaScript (ES6), 51 bytes

a=>a.map(_=>m=Math.min(...a.filter(e=>e>m)),m=-1/0)

Each loop finds the smallest number that hasn't been found so far.

\$\endgroup\$
  • \$\begingroup\$ Calling this on [1,2,3,4,5,4,3,2,1] produces [1, 2, 3, 4, 5, Infinity, Infinity, Infinity, Infinity] \$\endgroup\$ – Benjamin Gruenbaum Apr 16 '16 at 21:55
  • \$\begingroup\$ @BenjaminGruenbaum "Input will not contain duplicates." \$\endgroup\$ – Neil Apr 17 '16 at 9:33
  • \$\begingroup\$ I have the exact same bytecount with a different approach \$\endgroup\$ – Bálint May 19 '16 at 19:02
  • \$\begingroup\$ Actually, 1 byte less \$\endgroup\$ – Bálint May 19 '16 at 19:32
  • \$\begingroup\$ This algorithm is a en.wikipedia.org/wiki/Selection_sort \$\endgroup\$ – Peter Cordes Nov 26 '17 at 5:52
8
\$\begingroup\$

Python 2, 34 bytes

def f(s):m=min(s);print m;f(s-{m})

Takes input as a set, printing its elements in increasing order, terminating with error.

A clean termination can be done in 41 bytes:

def f(s):
 if s:m=min(s);print m;f(s-{m})

or

l=input()
while l:m=min(l);print m;l-={m}

The input can be take as a list for 39 bytes, or 38 bytes in Python 3.5:

def f(l):m=min(l);print m;f(set(l)-{m})
def f(l):m=min(l);print(m);f({*l}-{m})
\$\endgroup\$
  • \$\begingroup\$ This is a en.wikipedia.org/wiki/Selection_sort, using m=min(s) / s - (m) as the inner loop to find and remove the min from the unsorted elements, and recursion as the outer. \$\endgroup\$ – Peter Cordes Nov 26 '17 at 5:45
8
\$\begingroup\$

Haskell, 42 41 38 bytes

f u=filter(`elem`u)[(minBound::Int)..]

Loops through all integers (signed 64bit, on my machine) and keeps those that are in u. Of course it doesn't finish in reasonable time.

The previous version looped through [minimum u..maximum u] which has the same worst case running time.

Edit: @xnor saved a byte. Thanks!

\$\endgroup\$
  • \$\begingroup\$ filter is one shorter: f u=filter(`elem`u)[minimum u..maximum u] \$\endgroup\$ – xnor Apr 15 '16 at 16:26
  • \$\begingroup\$ How brute force! Does [minimum u..] not work for type reasons? \$\endgroup\$ – xnor Apr 15 '16 at 23:06
  • \$\begingroup\$ @xnor: I think so. When calling, let's say f [1,3,0], the elements default to type Integer which is unbound, so the .. never ends. If you have to call it like f ([1, 3, 0]::[Int]) then I guess, the type annotation has to be included in the byte count. \$\endgroup\$ – nimi Apr 15 '16 at 23:53
  • \$\begingroup\$ How does it detect elements that occur more than once? \$\endgroup\$ – feersum Apr 16 '16 at 6:19
  • 1
    \$\begingroup\$ @feersum: it doesn't, but the challenge says: "Input will not contain duplicates". \$\endgroup\$ – nimi Apr 16 '16 at 13:21
8
\$\begingroup\$

Oracle SQL 11.2, 205 bytes

WITH s AS(SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))),v(p,f)AS(SELECT e,e FROM s UNION ALL SELECT p||','||e,e FROM v,s WHERE e+0>f)SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1);         

Un-golfed

WITH 
s AS  -- Split the string using ',' as separator
(     -- ||'' cast the xml type to varchar
  SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))
),  
v(p,f) AS  -- Recursive view : p = sorted string, f last number added
(
  SELECT e,e FROM s -- use each number as seed
  UNION ALL         -- only add a number if it is > the last added
  SELECT p||','||e,e FROM v,s WHERE e+0>f  -- +0 is needed to compare int and not strings
)  
-- The valid string has the same length as the input
SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1)          

As for what sort method it is, I have no idea, ORDER BY made sure I forgot them.

\$\endgroup\$
  • \$\begingroup\$ I barely know SQL, but from your comments I think you're selecting the min or max from the remaining unsorted elements, and appending that to the end of a sorted list. That makes this a en.wikipedia.org/wiki/Selection_sort. \$\endgroup\$ – Peter Cordes Nov 26 '17 at 5:58
8
\$\begingroup\$

x86-16 machine code (BubbleSort int8_t), 20 19 bytes

x86-64/32 machine code (JumpDownSort) 21 19 bytes

Changelog:

  • Thanks to @ped7g for the lodsb/cmp [si],al idea, and putting that together with a pointer increment / reset that I'd been looking at. Not needing al/ah lets us use nearly the same code for larger integers.

  • New (but related) algorithm, many implementation changes: Bubbly SelectionSort allows a smaller x86-64 implementation for bytes or dwords; break-even on x86-16 (bytes or words). Also avoids the bug on size=1 that my BubbleSort has. See below.

  • It turns out that my Bubbly Selection Sort with swaps every time you find a new min is already a known algorithm, JumpDown Sort. It's mentioned in Bubble Sort: An Archaeological Algorithmic Analysis (i.e. how did Bubble Sort become popular despite sucking).


Sorts 8-bit signed integers in-place. (Unsigned is the same code size, just change the jge to a jae). Duplicates are not a problem. We swap using a 16-bit rotate by 8 (with a memory destination).

Bubble Sort sucks for performance, but I've read that it's one of the smallest to implement in machine code. This seems especially true when there are special tricks for swapping adjacent elements. This is pretty much its only advantage, but sometimes (in real life embedded systems) that's enough advantage to use it for very short lists.

I omitted the early termination on no swaps. I used Wikipedia's "optimized" BubbleSort loop which avoids looking at the last n − 1 items when running for the n-th time, so the outer loop counter is the upper bound for the inner loop.

NASM listing (nasm -l /dev/stdout), or plain source

 2 address  16-bit       bubblesort16_v2:
 3          machine      ;; inputs: pointer in ds:si,  size in in cx
 4          code         ;; requires: DF=0  (cld)
 5          bytes        ;; clobbers: al, cx=0
 6                       
 7 00000000 49               dec     cx          ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 8                       .outer:                 ; do{
 9 00000001 51               push    cx          ;   cx = inner loop counter = i=max_unsorted_idx
10                       .inner:                 ;   do{
11 00000002 AC               lodsb               ;     al = *p++
12 00000003 3804             cmp     [si],al     ;     compare with *p (new one)
13 00000005 7D04             jge     .noswap
14 00000007 C144FF08         rol     word [si-1], 8    ; swap
15                       .noswap:
16 0000000B E2F5             loop    .inner      ;   } while(i < size);
17 0000000D 59               pop     cx          ;  cx = outer loop counter
18 0000000E 29CE             sub     si,cx       ;  reset pointer to start of array
19 00000010 E2EF             loop    .outer      ; } while(--size);
20 00000012 C3               ret

22 00000013  size = 0x13 = 19 bytes.

push/pop of cx around the inner loop means it runs with cx = outer_cx down to 0.

Note that rol r/m16, imm8 is not an 8086 instruction, it was added later (186 or 286), but this isn't trying to be 8086 code, just 16-bit x86. If SSE4.1 phminposuw would help, I'd use it.

A 32-bit version of this (still operating on 8-bit integers but with 32-bit pointers / counters) is 20 bytes (operand-size prefix on rol word [esi-1], 8)

Bug: size=1 is treated as size=65536, because nothing stops us from entering the outer do/while with cx=0. (You'd normally use jcxz for that.) But fortunately the 19-byte JumpDown Sort is 19 bytes and doesn't have that problem.


Original x86-16 20 byte version (without Ped7g's idea). Omitted to save space, see the edit history for it with a description.


Performance

Partially-overlapping store/reload (in memory-destination rotate) causes a store-forwarding stall on modern x86 CPUs (except in-order Atom). When a high value is bubbling upwards, this extra latency is part of a loop-carried dependency chain. Store/reload sucks in the first place (like 5 cycle store-forwarding latency on Haswell), but a forwarding stall brings it up to more like 13 cycles. Out-of-order execution will have trouble hiding this.

See also: Stack Overflow: bubble sort for sorting string for a version of this with a similar implementation, but with an early-out when no swaps are needed. It uses xchg al, ah / mov [si], ax for swapping, which is 1 byte longer and causes a partial-register stall on some CPUs. (But it may still be better than memory-dst rotate, which needs to load the value again). My comment there has some suggestions...


x86-64 / x86-32 JumpDown Sort, 19 bytes (sorts int32_t)

Callable from C using the x86-64 System V calling convention as
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size); (return value = max(array[])).

This is https://en.wikipedia.org/wiki/Selection_sort, but instead of remembering the position of the min element, swap the current candidate into the array. Once you've found the min(unsorted_region), store it to the end of the sorted region, like normal Selection Sort. This grows the sorted region by one. (In the code, rsi points to one past the end of the sorted region; lodsd advances it and mov [rsi-4], eax stores the min back into it.)

The name Jump Down Sort is used in Bubble Sort: An Archaeological Algorithmic Analysis. I guess my sort is really a Jump Up sort, because high elements jump upwards, leaving the bottom sorted, not the end.

This exchange design leads to the unsorted part of the array ending up in mostly reverse-sorted order, leading to lots of swaps later on. (Because you start with a large candidate, and keep seeing lower and lower candidates, so you keep swapping.) I called it "bubbly" even though it moves elements the other direction. The way it moves elements is also a little bit like a backwards insertion-sort. To watch it in action, use GDB's display (int[12])buf, set a breakpoint on the inner loop instruction, and use c (continue). Press return to repeat. (The "display" command gets GDB to print the whole array state every time we hit the breakpoint).

xchg with mem has an implicit lock prefix which makes this extra slow. Probably about an order of magnitude slower than an efficient load/store swap; xchg m,r is one per 23c throughput on Skylake, but load / store / mov with a tmp reg for an efficient swap(reg, mem) can shift one element per clock. It might be a worse ratio on an AMD CPU where the loop instruction is fast and wouldn't bottleneck the inner loop as much, but branch misses will still be a big bottleneck because swaps are common (and become more common as the unsorted region gets smaller).

 2 Address               ;; hybrib Bubble Selection sort
 3        machine         bubblyselectionsort_int32:   ;; working, 19 bytes.  Same size for int32 or int8
 4        code               ;; input: pointer in rsi, count in rcx
 5        bytes              ;; returns: eax = max
 6                       
 7                           ;dec  ecx           ; we avoid this by doing edi=esi *before* lodsb, so we do redundant compares
 8                                               ; This lets us (re)enter the inner loop even for 1 element remaining.
 9                       .outer:
10                           ; rsi pointing at the element that will receive min([rsi]..[rsi+rcx])
11 00000000 56               push   rsi
12 00000001 5F               pop    rdi
13                           ;mov    edi, esi     ; rdi = min-search pointer
14 00000002 AD               lodsd
16 00000003 51               push   rcx          ; rcx = inner counter
17                       .inner:                   ; do {
18                           ; rdi points at next element to check
19                           ; eax = candidate min
20 00000004 AF               scasd                 ; cmp eax, [rdi++]
21 00000005 7E03             jle  .notmin
22 00000007 8747FC           xchg   [rdi-4], eax   ; exchange with new min.
23                         .notmin:
24 0000000A E2F8             loop  .inner          ; } while(--inner);
26                           ; swap min-position with sorted position
27                           ; eax = min.  If it's not [rsi-4], then [rsi-4] was exchanged into the array somewhere
28 0000000C 8946FC           mov    [rsi-4], eax
29 0000000F 59               pop   rcx           ; rcx = outer loop counter = unsorted elements left
30 00000010 E2EE             loop  .outer        ; } while(--unsorted);
32 00000012 C3               ret

34 00000013 13           .size: db $ - bubblyselectionsort_int32
           0x13 = 19 bytes long

Same code size for int8_t: use lodsb / scasb, AL, and change the [rsi/rdi-4] to -1. The same machine-code works in 32-bit mode for 8/32-bit elements. 16-bit mode for 8/16-bit elements needs to be re-built with the offsets changed (and 16-bit addressing modes use a different encoding). But still 19 bytes for all.

It avoids the initial dec ecx by comparing with the element it just loaded before moving on. On the last iteration of the outer loop, it loads the last element, checks if it's less than itself, then is done. This allows it to work with size=1, where my BubbleSort fails (treats it as size = 65536).

I tested this version (in GDB) using the this caller: Try it online!. You can run this it on TIO, but of course no debugger or printing. Still, the _start that calls it exits with exit-status = largest element = 99, so you can see it works.

\$\endgroup\$
  • \$\begingroup\$ There might be room to improve on the inner-loop loop condition, it seems to be using a lot of bytes. Maybe push/pop cx and use loop for both? Maybe loop the other way, from back to front of the array so we count an index down to zero? (And increment bx because the sorted portion is at the end you loop towards). \$\endgroup\$ – Peter Cordes Nov 25 '17 at 15:32
  • 1
    \$\begingroup\$ Got it down to 19B, but with lot of changes, also input regs (some changes probably not needed, but as I was toying around, they remained there from earlier experiments)... it's still based on your work, so reluctant to post it as answer, you can check it on pastebin: pastebin.com/0VMzdUjj \$\endgroup\$ – Ped7g Nov 26 '17 at 2:54
  • \$\begingroup\$ @Ped7g: Nice! I'd considered sub si, cx as part of the outer loop using a pointer instead of indexing, but I hadn't thought of lodsb / cmp [si], al. I'd been considering lodsw / dec si, or lodsb /xchg al,ahto still set up for cmp ah,al \$\endgroup\$ – Peter Cordes Nov 26 '17 at 3:44
  • \$\begingroup\$ @Ped7g: oh, your version requires cld, or I guess we could make that part of the calling convention. AFAIK, having DF cleared is not a standard part of 16-bit calling conventions, only 32/64. Or is it just that you can't assume it in a bootloader? But with a custom register calling convention, this is as much of a code fragment as a function, so sure, why not require DF=0. (And if we want, ES=DS so we could scasb instead of lodsb if that's more convenient.) \$\endgroup\$ – Peter Cordes Nov 26 '17 at 3:48
  • 1
    \$\begingroup\$ @Ped7g: I have no idea about 16-bit conventions, all I know is that you couldn't always assume DF was cleared. But I think that's mostly in a bootloader context. I've never run anything I've written on real DOS. I was on Atari Mega 4 STe (68000/68020), then Linux (on a Pentium MMX), so I managed to avoid 16-bit x86 entirely until SO questions rammed it down my throat. \$\endgroup\$ – Peter Cordes Nov 26 '17 at 4:39
6
\$\begingroup\$

C, 72 bytes

i,j;a(int*l,int n){for(i=0;i=i?:--n;j>l[n]?l[i]=l[n],l[n]=j:0)j=l[--i];}

Bubblesort. The first argument is a pointer to the array, the second argument is the length of the array. Works with gcc.

\$\endgroup\$
  • \$\begingroup\$ This really needs an ungolfed version to be readable; it's really hard to keep track of where the ternary operators start / end. \$\endgroup\$ – Peter Cordes Nov 26 '17 at 5:44
5
\$\begingroup\$

MATL, 11 10 bytes

Y@t!d0>AY)

Extremely inefficient examination of all permutations of the input.

Try it Online!

Explanation

        % Implicitly grab input array
Y@      % Compute all permutations (each permutation as a row)
t       % Duplicate this matrix
!d      % Transpose and take the differences between the values
0>A     % Find the rows where all differences are > 0
Y)      % Return only the row where this is true
        % Implicitly display the result
\$\endgroup\$
5
\$\begingroup\$

Ruby, 40 bytes

Selection sort. Anonymous function; takes the list as argument.

->a{r=[];r<<a.delete(a.min)while[]!=a;r}
\$\endgroup\$
4
\$\begingroup\$

Python, 120 Bytes

def f(a):import time,threading;[threading.Thread(None,lambda b=b,c=min(a):print(time.sleep(b-c)or b)).start()for b in a]

This probably won't be the shortest answer but I feel like this algorithm belongs here. call with a list of integers, they'll be printed in a sorted manner to stdout. I wouldn't try it with too large numbers though.

\$\endgroup\$
  • \$\begingroup\$ Nice first post! And nice username. :P \$\endgroup\$ – Rɪᴋᴇʀ Apr 15 '16 at 17:05
4
\$\begingroup\$

MIPS, 68 bytes

I wrote a simple unoptimized bubble sort implementation a while ago. Byte count begins at loop and ends at li $v0, 10, assuming that the list address and list length are already in memory.

 Address    Code        Basic                     Source

0x00400000  0x3c011001  lui $1,4097           5    main:   la      $s0, list       # List address
0x00400004  0x34300000  ori $16,$1,0               
0x00400008  0x2411000a  addiu $17,$0,10       6            li      $s1, 10         # List length
0x0040000c  0x24080000  addiu $8,$0,0         8    loop:   li      $t0, 0          # swapped
0x00400010  0x24090001  addiu $9,$0,1         9            li      $t1, 1          # for loop "i"
0x00400014  0x1131000b  beq $9,$17,11         11   for:    beq     $t1, $s1, fend  # break if i==length
0x00400018  0x00095080  sll $10,$9,2          13           sll     $t2, $t1, 2     # Temp index, multiply by 4
0x0040001c  0x01505020  add $10,$10,$16       14           add     $t2, $t2, $s0   # Combined address
0x00400020  0x8d4b0000  lw $11,0($10)         15           lw      $t3, 0($t2)     # list[i]
0x00400024  0x8d4cfffc  lw $12,-4($10)        16           lw      $t4, -4($t2)    # list[i-1]
0x00400028  0x21290001  addi $9,$9,1          18           addi    $t1, $t1, 1     # i++
0x0040002c  0x016c082a  slt $1,$11,$12        20           ble     $t4, $t3, for   # if list[i-1] > list[i]
0x00400030  0x1020fff8  beq $1,$0,-8               
0x00400034  0xad4bfffc  sw $11,-4($10)        21           sw      $t3, -4($t2)    # swap and store
0x00400038  0xad4c0000  sw $12,0($10)         22           sw      $t4, 0($t2)     
0x0040003c  0x24080001  addiu $8,$0,1         23           li      $t0, 1          # swapped=true
0x00400040  0x08100005  j 0x00400014          24           j       for
0x00400044  0x20010001  addi $1,$0,1          26   fend:   subi    $s1, $s1, 1     # length--
0x00400048  0x02218822  sub $17,$17,$1             
0x0040004c  0x1500ffef  bne $8,$0,-17         27           bnez    $t0, loop       # Repeat if swapped==true
0x00400050  0x2402000a  addiu $2,$0,10        29           li      $v0, 10        
0x00400054  0x0000000c  syscall               30           syscall

Now I wait to be blown out of the water with x86...

\$\endgroup\$
  • 1
    \$\begingroup\$ You can leave out the swapped=true early-out check and count down based on the array size. See my 20 byte x86-16 version that sorts 8-bit integer. I might make a normal 32 or 64-bit x86 version that sorts 32-bit integers at some point, but 8-bit integers in 16-bit mode is kind of a sweet spot for x86. \$\endgroup\$ – Peter Cordes Nov 25 '17 at 16:00
4
\$\begingroup\$

Awk, 66 bytes

{b=$0;a[b]}m<b{m=b}n>b{n=b}END{for(i=n;i<=m;i++)if(i in a)print i}

Arrays in awk are like dictionaries, not like C arrays. The indexes can be non-contiguous, and they grow (and are created) as needed. So, we create an array a for the input, with each line being a key. And we save the min and max values. Then we loop from min to max, and print all keys which exist in a. b is just to avoid repeated usage of $0.

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

Python 3, 91 62 47 bytes

def f(z):
 while z:m=min(z);z.remove(m);yield m

Thanks to wnnmaw and Seeq for golfing help.

The argument z should be a list. This is a variant of selection sort.

I'm not sure how min stacks up against built-in sorting functions, since I'm not sure how Python implements min. Hopefully, this solution is still okay. Any golfing suggestions in the comments or in PPCG chat are welcome.

\$\endgroup\$
  • \$\begingroup\$ Make sure to state what type of sort you are using. \$\endgroup\$ – Michelfrancis Bustillos Apr 15 '16 at 13:32
  • \$\begingroup\$ @MichelfrancisBustillos I've honestly forgotten what algorithm this is. Might be selection sort? \$\endgroup\$ – Sherlock9 Apr 15 '16 at 13:33
  • 1
    \$\begingroup\$ Just out of curiosity, why not just directly take a list? The question allows for open input format \$\endgroup\$ – wnnmaw Apr 15 '16 at 15:02
  • 1
    \$\begingroup\$ @wnnmaw Dang it, I wrote one up but forgot to post it. Thanks for the reminder :D \$\endgroup\$ – Sherlock9 Apr 15 '16 at 16:56
  • \$\begingroup\$ Hmm, maybe def f(z):\nwhile z:m=min(z);z.remove(m);yield m \$\endgroup\$ – seequ Apr 15 '16 at 22:13
4
\$\begingroup\$

MATL, 11 bytes

`t4#X<2#)tn

Try it online!

This sorts by the following procedure, which is O(n2):

  1. Take the minimum of the array.
  2. Remove that value from the array, and store it for subsequent display.
  3. Apply the same procedure with the rest of the array, until it becomes empty.
  4. Display all numbers in the order in which they were obtained.

MATL is stack-based. The array with remaining values is kept at the top of the stack. The removed values are below, in order. At the end of the program all those values are displayed. The array at the top would also be displayed, but since it's empty it's not shown.

`        % Do...while loop
  t      %   Duplicate. Implicitly take input in the first iteration
  4#X<   %   Compute index of mininum of the array
  2#)    %   Push the minimum, and then the array with remaining entries
  tn     %   Duplicate and push number of elements, to be used as loop condition
         % Implicitly end do...while loop
         % Implicitly display stack contents
\$\endgroup\$
3
\$\begingroup\$

Pyth - 15 13 11 10 bytes

Two bytes saved thanks to @Jakube.

Bogosort.

f!s>VTtT.p

Try it online here.

I don't need the h cuz we are guaranteed no duplicates.

\$\endgroup\$
  • \$\begingroup\$ @Jakube I feel stupid, thanks. \$\endgroup\$ – Maltysen Apr 15 '16 at 13:27
  • \$\begingroup\$ @Suever as I said in my answer, we are guaranteed no duplicates as per OP. \$\endgroup\$ – Maltysen Apr 15 '16 at 13:54
  • \$\begingroup\$ Sorry about that! Missed that point. \$\endgroup\$ – Suever Apr 15 '16 at 13:57
3
\$\begingroup\$

Seriously, 6 bytes

,;l@╨m

Try it online!

This does the same thing as many other answers: generate all permutations, select minimum. I kinda forgot that this would work while I was working on the below solution.

Explanation:

,;l@╨m
,;l@    push len(input), input
    ╨m  minimum permutation

Seriously, 25 bytes (non-competing)

This would be competitive if it wasn't for a bug in the shuffle command that I just fixed.

,1WX╚;;pX@dXZ`i@-0<`MπYWX

Try it online! This implements the best sorting algorithm ever: Bogosort!

Explanation:

,1WX╚;;pX@dXZ`i@-0<`MπYWX
,                          get input
 1W                    WX  do-while:
   X                         discard
    ╚                        shuffle
     ;;                      dupe twice
       pX@dX                 remove first element of first dupe and last element of second dupe
            Z                zip
             `i@-0<`MπY      test if all differences are positive (if any are not, the list is not sorted), negate (1 if not sorted else 0)
\$\endgroup\$
3
\$\begingroup\$

MATL, 17 16 bytes

Saved one byte creating null array thanks to @LuisMendo

vTbtX<-QI$(f8M+q

Bucket sort. Don't try it with a range greater than 231-1.

Try it online!

Explanation

v                  % push an empty array
 T                 % push 1
  b                % bubble the input array up to the top of the stack
   t               % duplicate it
    X<             % find the minimum
      -            % subtract min from input array
       Q           % and increment to adjust for 1-based indexing
        I$(        % resulting array used as indices of empty array 
                   % (the [] way up at the top) that are assigned 1 (from T)
           f       % find the nonzero indices
            8M     % magically retrieve the 4th previous function input :/
                     (aka, the min input array value)
              +    % add it to the indices
               q   % and decrement

TIL:

  • You can initialize an empty array in MATL using [] and grow it, just like in MATLAB
  • How to use ( for assignment indexing
  • How to use the M automatic clipboard

New day, new TIL:

  • vertcat magically creates an empty array when there's nothing on the stack to concatenate
\$\endgroup\$
  • \$\begingroup\$ Add to your TIL: an initial [] can be replaced by v. This is because the default number of inputs of v is the number of elements in the stack \$\endgroup\$ – Luis Mendo Apr 18 '16 at 15:21
  • \$\begingroup\$ @LuisMendo Sooo... if there is one array on the stack... ? Investigating. \$\endgroup\$ – beaker Apr 18 '16 at 15:27
  • \$\begingroup\$ Then it does nothing. Think of it as vertcat(STACK{:}) \$\endgroup\$ – Luis Mendo Apr 18 '16 at 15:30
3
\$\begingroup\$

Julia, 28 27 bytes

x->colon(extrema(x)...)∩x

Try it online!

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

R, 68 Bytes

Takes input i and outputs o which is the sorted list.

o<-i
for(j in 1:length(i)){
x<-(i-min(i))==0
o[j]<-i[x]
i<-i[!x]
}
o

Explanation:

o<-i                      # Defines output as o
 for(j in 1:length(i)){   # Initializes loop for length of input
  x<-(i-min(i))==0        # Generates logical vector by finding the value 0 
                          # of input less the minimum of input. 
   o[j]<-i[x]             # Puts the smallest value at position j
    i<-i[!x]              # Removes the smallest value from input
      }                   # Ends loop
       o                  # Returns sorted list

Avoiding the permutations means it can sort large lists relatively quickly. The "trick" is that subtracting the smallest value from the input leaves a single 0 that determine both the smallest value and the position of the smallest value.

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

Java 8, 112 92 bytes

Here is another selection sort. The input is a List t of integers and the sorted output is printed to standard out.

t->{for(;0<t.size();System.out.println(t.remove(t.indexOf(java.util.Collections.min(t)))));}

Update

  • -20 [16-08-21] Used a lambda
\$\endgroup\$
  • \$\begingroup\$ Hi Nonlinear, and welcome to PPCG! \$\endgroup\$ – isaacg Apr 15 '16 at 21:07
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! It appears your code assumes a variable t to exist, which makes it a snippet; we require submissions to be full programs or functions which utilize our default I/O formats. We also require imports to factor into the byte count. Let me know if you have any questions! \$\endgroup\$ – Alex A. Apr 16 '16 at 6:53
  • \$\begingroup\$ Thanks for the resources! I modified my answer to be a function and to include the import. \$\endgroup\$ – NonlinearFruit Apr 16 '16 at 13:27
2
\$\begingroup\$

Retina, 95

Modified bubble sort. I suspect there are much better ways to do this, even without the retina sort builtin.

-\d+
$*n
\d+
$*11
+`(1+) (n+)
$2 $1
+`\b(n+) (\1n+)|(1+)(1+) \3\b
$2$3 $1$3$4
1(1*)
$.1
n+
-$.&
  • Stage 1 - convert -ve integers to unary with n as the digit; drop the - signs.
  • Stage 2 - convert +ve and zero integers to unary with 1 as the digit; add 1 to each one, so that zero is represented by 1.
  • Stage 3 - Move all -ves to the front.
  • Stage 4 - Sort: move all -ves with the largest magnitude (i.e. smallest numerical) ahead of higher -ves. Move smaller +ves ahead of larger +ves.
  • Stage 5 - Remove 1 from, and convert +ve unaries back to decimal.
  • Stage 6 - convert -ve unaries back to decimal, including sign.

Try it online.

\$\endgroup\$
  • \$\begingroup\$ Just one byte shorter! \$\endgroup\$ – Leaky Nun Apr 16 '16 at 16:37
  • \$\begingroup\$ @LeakyNun That doesn't sort the last element in the list. \$\endgroup\$ – mbomb007 Apr 25 '17 at 20:45
  • \$\begingroup\$ @mbomb007 right, never mind. \$\endgroup\$ – Leaky Nun Apr 26 '17 at 1:24
2
\$\begingroup\$

Ruby, 22 bytes

A quick permutation sort. Runs in O(n!) space and time.

->a{a.permutation.min}
\$\endgroup\$
2
\$\begingroup\$

Clojure, 73 35 bytes

Bogosort :)

#(if(apply < %)%(recur(shuffle %)))

Earlier version:

#(reduce(fn[r i](let[[a b](split-with(partial > i)r)](concat a[i]b)))[]%)

Reduces to a sorted list r by splitting it into "smaller than i" and "larger than i" parts. I guess this is the insertion sort.

\$\endgroup\$
  • \$\begingroup\$ Nice! I did not know you could recur on an anonymous function. Also didn't know about shuffle. \$\endgroup\$ – Matias Bjarland May 22 '18 at 8:47
2
\$\begingroup\$

Ruby, 26 24 bytes

Selection sort, similar to Value Ink's answer, but using a different approach for greater golfiness.

According to the specification: "Input/output can be done in any method you choose, as long as it is human readable". I think this fits the description, output is an array of arrays with a single element.

->l{l.map{l-l-=[l.min]}}

example:

->l{l.map{l-l-=[l.min]}}[[2,4,3,1]]
=> [[1], [2], [3], [4]]
\$\endgroup\$
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\$
  • \$\begingroup\$ I guess that's a kind of en.wikipedia.org/wiki/Counting_sort. \$\endgroup\$ – Peter Cordes Nov 26 '17 at 4:48
  • \$\begingroup\$ @PeterCordes That was kinda the point \$\endgroup\$ – dkudriavtsev Nov 26 '17 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\$ – Peter Cordes Nov 26 '17 at 4:54
  • \$\begingroup\$ True. Thanks @PeterCordes \$\endgroup\$ – dkudriavtsev Nov 26 '17 at 4:55

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.