Created
July 3, 2013 22:28
-
-
Save jaredlewis/5923392 to your computer and use it in GitHub Desktop.
Matrix sorter
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
| // Create the class takes a single argument of the matrix to sort | |
| var MatrixSorter = function(matrix){ | |
| this.matrix = matrix || []; | |
| return this.init(); | |
| }; | |
| // Prototype the Class | |
| MatrixSorter.prototype = { | |
| /** | |
| * Init the sorter | |
| */ | |
| init: function(){ | |
| this.numPasses = 0; | |
| }, | |
| /** | |
| * Sort the matrix into a flat array | |
| * @returns {Array} | |
| */ | |
| sort: function(){ | |
| var matrix = this.matrix.slice(0); | |
| var solutionArray = []; | |
| var matrixLength = matrix.length; | |
| this.numPasses = 0; | |
| for(var i = 0; i < matrixLength; i++){ | |
| var arrayGroup = matrix[i]; | |
| var item = null | |
| var smallerItem = null; | |
| // Get the first element of the array until we are empty | |
| while(item = arrayGroup.shift()){ | |
| this.numPasses++; | |
| var foundSmallerItem = true; | |
| // Loop over the other elements in all arrays looking for | |
| // a smaller or equal sized item until none are found | |
| while(foundSmallerItem){ | |
| smallerItem = this.findSmallerItem(item, matrix); | |
| if(smallerItem){ | |
| solutionArray.push(smallerItem); | |
| } | |
| else { | |
| foundSmallerItem = false; | |
| } | |
| } | |
| // Append the item as no smaller ones were found | |
| solutionArray.push(item); | |
| } | |
| } | |
| // Return the sorted array | |
| return solutionArray; | |
| }, | |
| /** | |
| * Loop over the available arrays looking for an item equal | |
| * or smaller thant he passed item, if found return it | |
| * @param item | |
| * @param arrays | |
| * @returns {*} | |
| */ | |
| findSmallerItem: function(item, arrays){ | |
| var arraysLength = arrays.length; | |
| for(var i = 0; i < arraysLength; i++){ | |
| this.numPasses++; | |
| var arrayGroup = arrays[i]; | |
| var arrayLength = arrayGroup.length; | |
| for(var k = 0; k < arrayLength; k++){ | |
| this.numPasses++; | |
| var smallerItem = arrayGroup[k]; | |
| if(smallerItem <= item){ | |
| return arrayGroup.splice(k, 1)[0]; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| }; | |
| var matrix = [ | |
| [1, 2, 2, 3], | |
| [2, 3, 3, 14], | |
| [2, 4, 24, 25], | |
| [2, 4, 2, 27, 49] | |
| ]; | |
| var s = new MatrixSorter(matrix); | |
| var sorted = s.sort(); | |
| console.log("Sorted: " + sorted + " in " + s.numPasses + " passes"); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment