Created
September 25, 2013 02:25
-
-
Save TheIronDev/6694423 to your computer and use it in GitHub Desktop.
Having some fun with JavaScript. Quicksort implementation for javascript arrays
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
// 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