Created
December 14, 2017 15:35
-
-
Save scriptonian/16f7d20cd43679378b45779c81a64c2d to your computer and use it in GitHub Desktop.
Javascript Shell Sort
This file contains hidden or 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
function ScriptoniteSort() { | |
this.arr = []; | |
} | |
ScriptoniteSort.prototype = { | |
swap: function(arr, index_one, index_two) { | |
//swap | |
var temp = arr[index_one]; | |
arr[index_one] = arr[index_two]; | |
arr[index_two] = temp; | |
}, | |
validateCollection: function(datalist) { | |
if(arguments.length === 0 || !Array.isArray(this.arr)) { | |
throw new Error('Either No Arguments Passed, Or Passed Param is not an Array'); | |
} | |
}, | |
//use this insertion sort when working with shell sort | |
insertionSortGap: function(datalist, startIndex, increment) { | |
//set length of array | |
var dataLength = datalist.length; | |
//create sub lists and do sorting | |
for (var i = startIndex + increment; i < dataLength; i += increment) { | |
var temp = this.arr[i]; | |
//placeholder is where we will insert | |
var placeHolderIndex = i; | |
//like the insertion sort method we do the same here only using the increment values | |
while( (placeHolderIndex >= increment) && (this.arr[placeHolderIndex - increment] > temp) ) { | |
//if condition is met then keep shifting the values | |
this.arr[placeHolderIndex] = this.arr[placeHolderIndex - increment]; | |
placeHolderIndex -= increment; | |
} | |
//after shifting is all done, insert the value into right location | |
this.arr[placeHolderIndex] = temp; | |
} | |
}, | |
//this method uses two for loops instead of a while within a loop | |
insertionSortGapAlternative: function(datalist, startIndex, increment) { | |
//set length of array | |
var dataLength = datalist.length; | |
//create sub lists and do sorting | |
for(var i = startIndex; i < dataLength; i += increment) { | |
//console.log(this.arr[i]); | |
for(var j = Math.min(i + increment, dataLength - 1); j - increment >= 0; j = j - increment) { | |
if(this.arr[j] < this.arr[j - increment]) { | |
this.swap(this.arr, j, j - increment); | |
} else { | |
break; | |
} | |
} | |
} | |
}, | |
shellSort: function(datalist) { | |
//assign the data property to the passed in datalist | |
this.arr = datalist; | |
//check if passed in is an array | |
this.validateCollection(this.arr); | |
//set the increment | |
var increment = Math.floor(this.arr.length / 2); | |
//a long as increment is greater than 1 call the modified insertion sort with gap | |
while(increment >= 1) { | |
for(var i = 0; i < increment; i++) { | |
this.insertionSortGap(datalist, i, increment); | |
//or call the other method insertion sort method | |
//this.insertionSortGapAlternative(datalist, i, increment); | |
} | |
increment = Math.floor(increment / 2); | |
} | |
//display or return final array | |
console.log("---->" + this.arr.toString()); | |
} | |
}; | |
var myArr = [9, 11, 5, 1, 7, 2, 15, 1, 8, 6]; | |
//var myArr = [1, 7, 4, 0, 5, 3]; | |
//var myArr = [64, 25, 12, 22, 11]; | |
var collection = new ScriptoniteSort(); | |
collection.insertionSort(myArr); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment