Last active
March 23, 2018 11:54
-
-
Save alpgul/d1841eb9d2cba5e6daf50c14701239b7 to your computer and use it in GitHub Desktop.
Insertion Sort with Javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Best Case:N | |
Average Case:N^2 | |
Worst Case:N^2 | |
*/ | |
(function(){ | |
let comparisons=0; | |
let arr2=[28, 31, 43, 97, 49, 11, 33, 71, 41, 80, 86, 38, 53, 54, 7, 67, 96, 52, 29, 25, 56, 77, 73, 42, 62, 84, 21, 68, 2, 44, 9, 94, 66, 78, 6, 57, 20, 89, 1, 55, 65, 85, 51, 23, 70, 32, 12, 27, 18, 90, 4, 82, 5, 35, 58, 69, 22, 83, 37, 61, 79, 34, 81, 30, 72, 95, 91, 48, 88, 46, 3, 26, 60, 39, 17, 24, 74, 99, 10, 16, 87, 98, 76, 13, 36, 45, 59, 100, 50, 93, 19, 75, 92, 40, 8, 47, 14, 15, 63, 64]; | |
let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]; | |
function insertion_Sort(A){ | |
var start = Date.now(); | |
let holePosition,valueToInsert; | |
for(let i in A){ | |
valueToInsert = A[i]; | |
holePosition = i; | |
while (holePosition > 0 && A[holePosition-1] > valueToInsert){ | |
comparisons++; | |
A[holePosition] = A[holePosition-1] | |
holePosition = holePosition -1 | |
} | |
A[holePosition] = valueToInsert | |
} | |
var end = Date.now(); | |
var elapsed = end - start; | |
console.log("Elapsed Time:"+elapsed); | |
console.log("Total comparisons:"+comparisons); | |
comparisons=0; | |
return A; | |
} | |
insertion_Sort(arr2)//Total comparisons:2429 | |
console.log(insertion_Sort(arr)); | |
})(); |
Author
alpgul
commented
Mar 23, 2018
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment