Insertion Sort.
Best: O(n), Average: O(n2), Worst: O(n2)
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time.
Visit Wikipedia for more information.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //Programmer: Larry Battle Mar 9, 2011 //Purpose: Insertion sort implemented in Javascript. var insertionSort = function (arr) { var len = arr.length, i = -1, j, tmp; while (len--) { tmp = arr[++i]; j = i; while (j-- && arr[j] > tmp) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; } }; |
Usage
1 2 | insertionSort( [5,4,3,2,1] ); //returns [1,2,3,4,5]; insertionSort( [ "bear", "dog", "cat" ] ) // returns ["bear", "cat", "dog"]; |
Demo
Here’s a great short video tutorial to help those clueless about insertion sort.
Update:
/** * Sorts an array using insertion sort. * * @param {Array} - arr * @param {Boolean} areNumbers indicates whether the array elements should be cast as numbers. * @return {Array} the sorted array. */ var insertionSort = function (arr, areNumbers) { arr = arr.concat(); var len = arr.length, i = -1, j, tmp; while (len--) { tmp = arr[++i]; j = i; while (j-- && areNumbers ? (+arr[j] > +tmp) : (arr[j] > tmp) ) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; } return arr; }; |
// Treat input as array of numbers Input: insertionSort(["1","2","3","4","4","40","20","21"], true); Output: ["1", "2", "3", "4", "4", "20", "21", "40"] // Treat input as array of strings Input: insertionSort(["1","2","3","4","4","40","20","21"]); Output: ["1", "2", "20", "21", "3", "4", "4", "40"] |
Larry Battle
I love to program, and discover new tech. Check out my stackoverflow and github accounts.
Follow Me:
