Skip to content

Instantly share code, notes, and snippets.

@TheIronDev
Created September 25, 2013 02:25
Show Gist options
  • Save TheIronDev/6694423 to your computer and use it in GitHub Desktop.
Save TheIronDev/6694423 to your computer and use it in GitHub Desktop.
Having some fun with JavaScript. Quicksort implementation for javascript arrays
// Helper Constructor
var RandomArray = function(size) {
size = size || 10;
var tempArray = [];
for(var count=0,max = size;count<max;count++) {
tempArray.push(~~(Math.random()*100));
}
return tempArray;
};
// Check to see if the array is sorted
Array.prototype.isSorted = function(){
var arrayIndex = this.length;
// Typically I would write a for loop for readability
// But today, we are going for speeeeeeed (yeeeeahhhhhhh)
while(arrayIndex--) {
// Gotta catch that edge case!
if(arrayIndex>0 && this[arrayIndex]<this[arrayIndex-1]) {
return false;
}
}
return true;
};
Array.prototype.quicksort = function() {
// Catching the base case of an empty array or a single value
if(this.length <= 1) {
return this;
}
var left =[], // Left Side array, used to store values less than the pivot
right =[], // Right side array, used to store values greater than the pivot
pivotArr = [], // PivotArr is to catch the duplicate values.
pivot; // Since we are in the business of declaring vars, the pivot can live here
// If its even, then grab the floor(middle), otherwise lets get the real mid!
if(this.length%2 === 0) {
pivot = this.length/2;
} else {
pivot = (this.length+1)/2;
}
for (var i=0, max = this.length;i<max;i++) {
if(this[i] < this[pivot]) {
left.push(this[i]);
} else if(this[i] > this[pivot]) {
right.push(this[i]);
} else {
pivotArr.push(this[i]);
}
}
left = left.quicksort(); // Recursively go down
right = right.quicksort(); // Recursively go down
// Return leftArray + pivotvalueArray + rightArray
return (left.concat(pivotArr)).concat(right);
};
// Test Cases Helper
function expect(value, expected, message) {
message = message || "Test case: ";
if(value !== expected) {
return message + "false ("+value+" did not match "+expected+")";
} else {
return message + "true";
}
}
(function(){
console.log("*** Testing Sort Functionality ***");
console.log(expect([1,2,3].isSorted(), true, "Sorted array is sorted: "));
console.log(expect([3,2,1].isSorted(), false, "Unsorted array is not sorted: "));
console.log("*** Testing Quicksort ***");
var temp = new RandomArray();
var sortedArray = temp.quicksort();
console.log("Unsorted: "+temp);
console.log("Sorted: "+sortedArray);
console.log(expect(sortedArray.isSorted(), true, "The quicksorted array is sorted: "));
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment