What sorting algorithm is this? I thought of this method last night and quickly drew up some code, and to my surprise worked perfectly. I've been looking through the Wikipedia article on sorting algorithms and have searched Stack Overflow but have been unable to find this or similar algorithm.
This is the algorithm's written process:
[3, 1, 0, 4]
^ ^ Check outermost items, swap if necessary
----------------
[3, 1, 0, 4]
^ ^ Check first pair of second farthest apart items, swap if necessary
[0, 1, 3, 4]
----------------
[0, 1, 3, 4]
^ ^ Check second pair of second farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
^ ^ Check first pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
^ ^ Check second pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
^ ^ Check third pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
Cannot compare closer items (adjacent), done.
This is the algorithm in JavaScript:
var unsorted = [4, 9, 10, 2, 9, 4, 0];
var sorted = ianSort(unsorted);
function ianSort(array) {
for(var j = array.length; j > 1; j--) {
for(var i = 0; i < array.length - j + 1; i++) {
if(array[i] > array[i + j - 1]) {
var temp = array[i];
array[i] = array[i + j - 1];
array[i + j - 1] = temp;
}
}
}
return array;
}
(I've called the function IanSort here in the unlikely event that I'm the first person to think this up. ^_^)
1 + 2 + 3 + ... + array.length
, which adds up toO(n^2)
. Have you tested it on an array with a million elements, for example? – IVlad Feb 11 '11 at 2:40