What sorting algorithm is this 3 liner?

Question

Given array

a=[4,6,9,3,1,5,9,1,4,2,8]
[4, 6, 9, 3, 1, 5, 9, 1, 4, 2, 8]

Sorting algorithm

Note that in case anybody doesn't know. To swap 2 numbers 'a' and 'b' you can do a=a+b b=a-b a=a-b (can be done with * or / too).

for(i=0;i<a.length;i++)
   for(j=i+1;j<a.length;j++)
     if(a[i]>a[j]) {a[i]=a[i]+a[j]; a[j]=a[i]-a[j]; a[i]=a[i]-a[j];  }

or more concise, with += and -=

for(i=0;i<a.length;i++)
   for(j=i+1;j<a.length;j++)
     if(a[i]>a[j]) {a[i]+=a[j]; a[j]=a[i]-a[j]; a[i]-=a[j];  }

Resultant array

[1, 1, 2, 3, 4, 4, 5, 6, 8, 9, 9]

so it works, tested in C and javascript console. I saw somebody do it from his head in C and I was struck by that, because when I did sorting algorithms I remembered them as being tricky things you study and afterwards you can know back to front, write mathematical statements describing how it works, don't memorize it, and then forget it or look it up or use a third party one anyway. But this is an easy 3 lines one can type out blindfolded.

I thought about what sorting algorithms i'd heard of.. I know what it isn't. bubble sort is long winded and scans multiple times so definitely not that.. mergesort and quicksort involve recursion so it's not that. And I thought it's either insertion sort or selection sort. But looking at them on wikipedia, none of them seem that small..

I understand how it works. Scanning forwards from i at the right of the sorted section of the array, looks for the first smallest swaps with a[i] then next smallest and swaps it, and so a[i] then contains the smallest in the unsorted and i++

There is one on wikipedia for insertion sort which has more lines and may be similar but seems to have a different 'logic'

for i = 1 to length(A) - 1
    x = A[i]
    j = i
    while j > 0 and A[j-1] > x
        A[j] = A[j-1]
        j = j - 1
    end while
    A[j] = x
 end for

it doesn't look anywhere near as concise (though perhaps it can be made to be), and the inner loop counts down rather than up.

or (still on the wikipedia insertion sort page)

for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

I tried to make a concise form (partly to test how similar the logic is), but it doesn't do it

a=[4,6,9,3,1,5,9,1,4,2,8]

for(i=1;i<a.length-1;i++)
  for(j=i;j>0;j--)
      if(a[j-1]>a[j]) {a[j-1]+=a[j]; a[j]=a[j-1]-a[j]; a[j-1]-=a[j]; }

produces

[1, 1, 2, 3, 4, 4, 5, 6, 9, 9, 8] <-- spot the 8 at the end!

And putting aside my failure in my lame attempt at making that sorting algorithm for insertion sort on wikipedia as concise as the one I had, and similar in structure..

It suggests to me that it's different in nature.. So if the 3 lines algorithm I gave at the start isn't inserion sort, then what is it.. and why is it different from the one on wikipedia, the inner loop is counting the other way and it's not going into an equivalent 3 lines, which tells me the logic behind the algorithms are a bit different too.

I see selection sort on wikipedia looks not very concise as well. So i'm sure my algorithm isn't that.

I see how the insertion sort on wikipedia works.. it's incrementing i, adding the element into the sorted portion then scanning down the sorted portion from right to left, and the first biggest item > a[i] (that'd also be the biggest in the sorted portion), gets swapped with a[i] So now again everything from 0..i is sorted and i++. But that logic is quite different. Counting down through the sorted portion is quite different to counting up through the unsorted portion. And I can see how the wikipedia one is quite efficient, breaking when it swaps in the inner loop, which is more efficient than my one that does potentially many swaps to grow the sorted portion by one.

so I guess my questions are.. what's the name of my one? I wouldn't call it crap sort 'cos it's quite concise in terms of lines..i'm thinking it must have a proper name. They even gave bubble sort a name and that's not exactly efficient.

can the wikipedia insertion sort be made as concise..(or near as concise) in terms of lines, as the one I did?

Amendment

moreon spotted a typo, where i'd done i<a.length-1 now amended to i<a.length or i<=a.length-1 as it obviously should be, so now the 3 line inefficient version of insertion sort works. I have made an efficient concise version of it though, see my answer.

Answer 1

Insertion sort can be made efficient and be concise

Insertion sort

for(i=1;i<a.length;i++)
   for(j=i;j>0;j--)
     if(a[j-1]>a[j]) {a[j-1]+=a[j]; a[j]=a[j-1]-a[j]; a[j-1]-=a[j]} else break;

Insertion sort involves and must involve, multiple swaps as it shifts all larger numbers to the right by continually swapping the new number with its neighbour until it's in order. see this for a diagram with explanation "Algorithms Lesson 2: Insertion Sort" https://www.youtube.com/watch?v=c4BRHC7kTaQ

Selection sort https://www.youtube.com/watch?v=6nDMgr0-Yyo shouldn't be done with multiple swaps though, that's very inefficient. It should find the index of the smallest of the unsorted and do one swap. You can do it in 4 lines + braces,

And you can't do a+=b b=a-b a-=b here because where i==minius you're "swapping" a[i] with a[i] which works ok with a temp variable but with the arithmetical hack you get a[i]==0 Also somebody points out that if your numbers are near the limit(s) for the data type e.g. for int, then adding and subtracting could cause an overflow.

And swaps instead of shifts is inefficient as well, as gregg points out

Selection sort

// minius is min index in unsorted/unplaced

for(i=0;i<a.length;i++)  
{
  minius=i;  // min index in unsorted/unplaced   
  for(j=i+1;j<a.length;j++) if(a[minius]>a[j]) minius=j;   
  temp=a[i]; a[i]=a[minius]; a[minius]=temp;   
}

Answer 2

It's actually a poorly coded selection sort. The i'th pass selects the minimum element from the subarray a[i..n-1] and puts it in a[i] for i=0...n-1. (The last pass is considering a zero-length subarray and does nothing.) It just finds the minimum with a lot of useless swapping.

The swap itself is an old trick to avoid use of a temporary variable. Most times you see it with XOR as the operation, but subtraction works as well. It's actually more efficient in nearly all circumstances to use a temp.

There are dumb variations of most of the O(n^2) sorts that amount to rejiggering of the loops. Insertion sort is:

for (i = 1; i < n; i++)
  for (j = i; j > 0; j--)
    if (a[j] < a[j-1]) swap(a[j], a[j-1])

This is dumb because though it can stop when it finally inserts the i'th element at the right location in the sorted subarray a[0..i-1], it keeps going. It's also swapping rather than just shifting elements upward, which a "real" insertion sort would do.

Answer 3

The double for loop is a hint that it is O(N^2) running time. It is good old-fashioned selection sort. The innermost three statements (a[j-1]...) are a way of performing swap.

Besides being interesting too look at, I would in general recommend against using this code. Just about any language has sorting routines in its standard library that will be faster. Additionally, doing swap by addition/subtraction is unnecessary and reduces the range of integers allowed (due to overflow).