Skip to content

Instantly share code, notes, and snippets.

@alpgul
Last active March 23, 2018 13:34
Show Gist options
  • Save alpgul/b7ff6897f45d08d0086c673237c9f7cb to your computer and use it in GitHub Desktop.
Save alpgul/b7ff6897f45d08d0086c673237c9f7cb to your computer and use it in GitHub Desktop.
Shell Sort with Javascript
/*
Best Case:N
Average Case:n*(logn)^2 OR (n)^(1.5)
Worst Case:(n)^(1.5)
*/
(function(){
let comparison=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 Shell_sort(array){
let i, j, increment, temp;
var start = Date.now();
increment = 3;
while (increment > 0)
{
for (i=0; i < array.length; i++)
{
j = i;
temp = array[i];
comparison++;
let comparison2=0;
while ((j >= increment) && (array[j-increment] > temp))
{
comparison++
array[j] = array[j - increment];
j = j - increment;
}
array[j] = temp;
}
if (Math.floor(increment/2) !== 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
var end = Date.now();
var elapsed = end - start;
console.log("Elapsed Time:"+elapsed);
console.log("Total comparison:"+comparison);
comparison=0;
return array;
}
Shell_sort(arr2);//Total comparison:1239
console.log(Shell_sort(arr));
})();
@alpgul
Copy link
Author

alpgul commented Mar 23, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment