Skip to content

Instantly share code, notes, and snippets.

@scriptonian
Created December 14, 2017 15:35
Show Gist options
  • Save scriptonian/16f7d20cd43679378b45779c81a64c2d to your computer and use it in GitHub Desktop.
Save scriptonian/16f7d20cd43679378b45779c81a64c2d to your computer and use it in GitHub Desktop.
Javascript Shell Sort
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