Insertion Sort Code Challenge

Question

My task for you this time is to implement an insertion sort algorithm. Sure, everyone and his dog can do it; but how easy is it to do in the fewest characters? One must take an array (or suitable alternative in your language) of 32-bit integers and sort them by value via the insertion sort method, then return the sorted array as a copy (not damaging the original).

Examples:

Input: {20, 45, 3, 62 }
Output: {3, 20, 45, 62 }

Input: {5, 2, 3, 1, 5, 4}
Output: {1, 2, 3, 4, 5, 5}

Misc:

• No using builtin or existing implementations of any kind of sorting in libraries.
• Only the code for the actual algorithm counts; it's up to you to output the results.
• The page i specified covers all the details of insertion sort so look there if you have any questions about the algorithm.

Answer 1

C#: 140 chars. Pre-golfed before asking, but i only spent 15 minutes or so on it.

Up to 163 after modifying it to make sure the list is not damaged and a sorted copy is returned.

Down to 162 after correcting an error and adding a using.

Down to 153 thanks to mtrw.

using n=List<Int>;static n InsertionSort(n s){n l=s;int i,j,t;for(i=2;i<l.Count;i++){for(j=i;j>1&&l[j]<l[--j];){t=l[j];l[j]=l[j+1];l[j+1]=t;}}return l;}

Answer 2

Python, 71 characters.

My original version is below but @RCIX changed the rules (oops, I mean clarified the specifications) to insist the original list was preserved, so here at 71 characters:

def f(o):
 t=o[:];n=[]
 while t:v=min(t);n+=[v];t.remove(v)
 return n

s=[20, 45, 3, 62];print s;print f(s);print s;print "==="
s=[5, 2, 3, 1, 5, 4];print s; print f(s);print s;print "==="

which gives:

[20, 45, 3, 62]
[3, 20, 45, 62]
[20, 45, 3, 62]
===
[5, 2, 3, 1, 5, 4]
[1, 2, 3, 4, 5, 5]
[5, 2, 3, 1, 5, 4]
===

You can see that the original list is preserved.

Here's the original version if you don't care about preserving the original list - I'm leaving it here just for historical purposes (64 characters):

def f(o):
 n=[]
 while o:v=min(o);n+=[v];o.remove(v)
 return n

s=[20, 45, 3, 62];print s;print f(s);print s;print "==="
s=[5, 2, 3, 1, 5, 4];print s; print f(s);print s;print "==="

This produces:

[20, 45, 3, 62]
[3, 20, 45, 62]
[]
===
[5, 2, 3, 1, 5, 4]
[1, 2, 3, 4, 5, 5]
[]
===

Answer 3

haskell 58 characters excluding the main function i used to test, including newlines.

i=foldl s []
s (x:y) i=min x i:s y (max x i)
s _ i=[i]

main = print $ map i [[20, 45, 3, 62], [5, 2, 3, 1, 5, 4]]

haskell is non-descructive as well and returns a new list.

49 characters

i=foldl s[];s[]i=[i];s(x:y)i=min x i:s y(max x i)

as per ephemients comment. the difference is in the base case and removing a bunch of unnecessary white space.

Answer 4

Perl in 80 chars (sorry, it's the best I can do when the language doesn't have a built-in min() function):

sub f{while(@_){$x=0;$_[$x]>$_[$_] and$x=$_ for 0..$#_;push@r,splice@_,$x,1;}@r}

Answer 5

MATLAB in 101 chars.

function L=g(L),for m=2:length(L),for k=m:-1:2,if L(k)<L(k-1),p=L(k);L(k)=L(k-1);L(k-1)=p;end;end;end

As gnibbler pointed out, my first attempt was selection sort, and much shorter. Oh well.

Previous: WRONG MATLAB in 62 chars. Yay for implied pass by reference:

function M=g(L),M=[];for c=L,[v,k]=min(L);L(k)=Inf;M=[M v];end

Answer 6

PLT Scheme in 131 chars. (Shaved of some chars using nested ifs instead of cond).

(define(f v)(define(i h v t)(if(null? t)`(,@h,v)(if(< v(car t))`(,@h,v,@t)(i`(,@h,(car t))v(cdr t)))))(foldl(λ(v l)(i'()v l))'()v))

PLT Scheme in 137 chars.

(define(f v)(define(i h v t)(cond((null? t)`(,@h,v))((< v(car t))`(,@h,v,@t))(#t(i`(,@h,(car t))v(cdr t)))))(foldl(λ(v l)(i'()v l))'()v)

Pretty:

(define (f v)
  (define (i h v t)
    (cond ((null? t) `(,@h ,v))
          ((< v (car t)) `(,@h ,v ,@t))
          (#t (i `(,@h ,(car t)) v (cdr t)))))
  (foldl (λ (v l) (i '() v l)) '() v))

Answer 7

C89, 109 chars

C isn't known for its low golf scores, but here's an earnest effort. It requires the caller to pass in the destination array, which must be large enough. The order of parameters is the same as the various mem/str standard library functions, namely dest, source, size.

// Unobfuscated
sort(b, a, s)
    int *b, *a;
{
    int *c, t;
    memcpy(b, a, 4*s);
    for(c = b; c < b+s; )
        for(a = c++; a > b; )
            t = *--a,
            a[1] < t ? (*a = a[1], a[1] = t)
                   : 0;
}

// Compressed
sort(b,a,s)int*a,*b;{int*c,t;memcpy(b,a,4*s);for(c=b;c<b+s;)for(a=c++;a>b;)t=*--a,a[1]<t?(*a=a[1],a[1]=t):0;}

Example usage:

int a[5] = {3, 1, 5, 2, 4}, b[5];
sort(b, a, 5);
// b is now {1, 2, 3, 4, 5}, a is unchanged

Answer 8

J

38 characters.

(([<.{.@]),}.@]$:~[>.{.@])`[@.(0=#@])/

Explanation:

   NB. given two arguments, return the left argument
   insert0 =: 4 : 'x'
   insert0 =: [
   NB. given two arguments, return the lesser of left and head of right
   insert1min =: 4 : 'x <. {. y'
   insert1min =: [ <. {.@]
   NB. given two arguments, return the greater of left and head of right
   insert1max =: [ >. {.@]
   NB. recurse with insert1max and tail of right, and prepend insert1min
   insert1 =: 4 : 'x insert1min y , (x insert1max y) insert }. y'
   insert1 =: insert1min , insert1max insert }.@]
   insert1 =: insert1min , }.@] insert~ insert1max
   NB. if right has zero length, insert0, else insert1
   NB. the recursive reference to insert in insert1 can be replaced by $:
   insert =: insert1 ` insert0 @. (0 = #@])
   NB. apply insert between all elements of argument
   sort =: insert/

Imagining the step-by-step evaluation,

   sort 5 2 3 1 5 4
=> 5 insert 2 insert 3 insert 1 insert 5 insert 4
=> 5 insert 2 insert 3 insert 1 insert 4 5
=> 5 insert 2 insert 3 insert 1 4 5
=> 5 insert 2 insert 1 3 4 5
=> 5 insert 1 2 3 4 5
=> 5 insert1 1 2 3 4 5
=> (5 insert1min 1 2 3 4 5) , (5 insert1max 1 2 3 4 5) insert (}. 1 2 3 4 5)
=> 1 , 5 insert 2 3 4 5
=> 1 , 2 , 5 insert 3 4 5
=> 1 , 2 , 3 , 5 insert 4 5
=> 1 , 2 , 3 , 4 , 5 insert 5
=> 1 , 2 , 3 , 4 , 5 , 5 insert >a:
=> 1 , 2 , 3 , 4 , 5 , 5 insert0 >a:
=> 1 , 2 , 3 , 4 , 5 , 5
1 2 3 4 5 5

Answer 9

Ruby 68 - I definitely improved on my first attempt

def s a;b=[];until(c=a.shift).nil?;c<=(a.min||c)?b<<c:a<<c;end;b;end

Original: Ruby ~114 - There are probably better ways of doing this in ruby. shrug

def s(a=[])
a.size.times {|i|
v=a[i];j=i-1
while j>=0 && a[j]>=v
a[j+1]=a[j]
j-=1
end
a[j+1]=v
}
a
end

Answer 10

Golfscript - 24 chars

~:A,,{).A\<$A@>+:A}%-1=

Runs from the command line

$ echo -n [5 4 3 2 1 6] |../golfscript.rb insertsort.gs 
123456

Verify that it is insertion sort by printing at each iteration

~:A,,{).A\<$A@>+:A.p}%-1=

The first iteration the 4 is inserted before the 5, selection sort for example would move the 1 to the start for the first iteration

$ echo -n [5 4 3 2 1 6] |../golfscript.rb insertsort.gs 
[5 4 3 2 1 6]
[4 5 3 2 1 6]
[3 4 5 2 1 6]
[2 3 4 5 1 6]
[1 2 3 4 5 6]
[1 2 3 4 5 6]
123456

And for the examples given, i also added a p to the end here to stop the numbers getting squashed together. Golfscript's default way of printing arrays is to just print the contents without any spaces.

$ echo -n [20 45 3 62] |../golfscript.rb insertsort.gs 
[20 45 3 62]
[20 45 3 62]
[3 20 45 62]
[3 20 45 62]
[3 20 45 62]

$ echo -n [5 2 3 1 5 4] |../golfscript.rb insertsort.gs 
[5 2 3 1 5 4]
[2 5 3 1 5 4]
[2 3 5 1 5 4]
[1 2 3 5 5 4]
[1 2 3 5 5 4]
[1 2 3 4 5 5]
[1 2 3 4 5 5]

How it works
~ converts the command line args into an array of int
:A creates a variable A which is the list to be sorted
, gets the length of A
, create a list [0 1 .. len(A)]
{}% executes a map over the list we just created. The output of the map is a list of all the partially sorted states.
-1= pulls the last item off the result of the map (which is the sorted list)
fin. so golfscript prints whatever is left on the stack, which is just our sorted list

inside the map
) increments the number
.A\< takes sorted lhs part of the list + the next element
$ inserts the new element into the correct place (This is the step that Aaron says is a little cheaty)
A@> get the unsorted part
+ join the sorted and unsorted parts together
:A store the result back in A for the next iteration

Answer 11

Haskell, 45 characters:

i=foldl(\x i->let(a,b)=span(<i)x in a++i:b)[]

Or, more analogous to barkmadley's entry (same 45 characters):

i=foldl s[];s x i=a++i:b where(a,b)=span(<i)x

Key is using span instead of rolling your own...

(also, could you arguably drop the "i=", to cut it to 43 characters?)

Answer 12

Lua, 111 characters

function f(a)b={}for i=1,#a do p=#b v=a[i]while p>0 and
v<b[p]do b[p+1]=b[p]p=p-1 end b[p+1]=v end return b end

--test code

a={20, 45, 3, 62}
print(table.concat(f(a), "\t"))

a={5, 2, 3, 1, 5, 4}
print(table.concat(f(a), "\t"))

a={...}
print(table.concat(f(a), "\t"))

Answer 13

Clojure - 150 chars

Someone can probably make it shorter.

(def ! #(if(seq%)(let[f(first%)](if(>=(nth%2%3 f)f)(recur(next%)(apply
conj(into[](take%3%2))f(nthnext%2%3))0)(recur%%2(inc%3))))%2))(def ? #(!%[]0))

And pretty:

(defn sort-it
  ([coll] (sort-it coll [] 0))  
  ([in out ndx]
    (if (seq in)
      (if (>= (nth out ndx (first in))
              (first in))
        (do 
          (println out)
          (recur (next in)
                 (apply conj 
                        (into [] (take ndx out))
                        (first in)
                        (nthnext out ndx))
                 0))
       (recur in out (inc ndx)))
      out)))

Fun time, as always.

Answer 14

F#, 69 chars based on comingstorm's solution:

let g L=Seq.fold(fun s x->let a,b=List.partition((>)x)s in a@x::b)[]L

It's almost an exact translation, and it's hard for me to imagine this one getting any shorter soon. I tried making the parameter L implicit by currying, but F#'s type inference system says no.

If you want to see the intermediate stages (the sorted accumulator s in the code), replace Seq.fold by Seq.scan. For example:

let h L=Seq.scan(fun s x->let a,b=List.partition((>)x)s in a@x::b)[]L

[5;2;3;1;5;4] |> h |> Seq.iter (printfn "%A")

Output:

[]
[5]
[2; 5]
[2; 3; 5]
[1; 2; 3; 5]
[1; 2; 3; 5; 5]
[1; 2; 3; 4; 5; 5]

Edit: Here's barkmadley's Haskell transmuted into F#. I had to use foldBack instead of fold, since that allows me to use function|..->.. instead of Match param with |..->.. to save a few chars:

let rec s i=function|h::t->min h i::(s(max h i)t)|_->[i]
let f L=List.foldBack s L []

85 chars, including the newline.

Answer 15

Javascript - 90 characters Nothing particularly clever here, though it does take advantage of semicolon insertion and uses global variables. The version which passes JSLint is about 103 characters.

function s(a){
  b=[];
  for(i in a){
    x=0;
    while(b[x]&&b[x]<a[i]){
      x++
    }
    b.splice(x,0,a[i])
  }
  return b
}

Answer 16

C++, 102 characters

void f(int*i,int*o,int s){int j,k;for(j=0;j<s;j++){for(k=j;k&&i[j]<o[k-1];k--)o[k]=o[k-1];o[k]=i[j];}}

Answer 17

F#: 105 chars

let s l=l|>Seq.fold(fun a v->let rec l=function[]->[v]|x::xs->if v<x then v::x::xs else x::l xs in l a)[]

Expanded:

let sort input=
    input
    |> Seq.fold(fun acc value ->
        let rec insert = function
            | [] -> [value]
            | x::xs -> if value < x then value::x::xs else x::insert xs
        in insert acc
        ) []

Explanation:

For each value in the input list, the internal function insert pushes value into an accumulator list in the first spot place where value is greater than its neighbor. Since it builds up a new list, this function is non-destructive.

Answer 18

Java - 154 chars, not including spaces :)

static void s(int[] i) {
    int a, b, k, t = 0;
    int n = 1;
    while (n <= i.length - 1) {
        a = n;
        b = n-1;
        do {
            if (i[a] < i[b]) {
                k = i[b];
                i[b] = i[a];
                i[a] = k;
                t = 1;
            }
            --a;
            --b;
        } while (t == 1 && a >= 1);
        t = 0;
        ++n;
    }
}