Friday Puzzler: Sort Type for: http://www.raymondcamden.com/index.cfm/2013/3/29/Friday-Puzzler-Sort-Type
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
/* Friday Puzzler: Sort Type | |
http://www.raymondcamden.com/index.cfm/2013/3/29/Friday-Puzzler-Sort-Type | |
This solution should be appropriate for large data-sets. Time complexity is O(n). | |
It utilizes short-circuiting logic to stop testing a list for sortability as soon as a pair of items that break the sort are found. | |
It also stops testing different sort functions once a suitable match has been found. | |
Requirements: Underscore.js | |
*/ | |
inputs = [ | |
"1,4,8,12,90", | |
"99,88,70,3,-2", | |
"Apple,Banana,Cherry,Donut,anna,berry,cherry", | |
"anna,Apple,Banana,berry,cherry,Cherry", | |
"Zed,Xymox,Joy Division,Cure", | |
"Zed,zip,Xymox,xoom", | |
"apple,banana,aardvark", | |
"9,2,9,1,99,-21" | |
]; | |
function isCasefulTextAsc(first, second) { | |
return !parseInt(first, 10) && first <= second; | |
} | |
function isCasefulTextDesc(first, second) { | |
return !parseInt(first, 10) && first >= second; | |
} | |
function isCaselessTextAsc(first, second) { | |
first = first.toLowerCase(); | |
second = second.toLowerCase(); | |
return !parseInt(first, 10) && first <= second; | |
} | |
function isCaselessTextDesc(first, second) { | |
first = first.toLowerCase(); | |
second = second.toLowerCase(); | |
return !parseInt(first, 10) && first >= second; | |
} | |
function isNumericAsc(first, second) { | |
return parseInt(first, 10) <= parseInt(second, 10); | |
} | |
function isNumericDesc(first, second) { | |
return parseInt(first, 10) >= parseInt(second, 10); | |
} | |
// sort functions in order of complexity | |
sortFunctions = [isNumericAsc, isNumericDesc, isCasefulTextAsc, isCasefulTextDesc, isCaselessTextAsc, isCaselessTextDesc]; | |
// returns an iterator for find() that will short-circuit the search by returning true once a non-sorted item is found. | |
function isSortedByIterator(sortFunc) { | |
var first = null; | |
return function (second) { | |
if (first !== null) { | |
var result = !sortFunc(first, second); | |
first = second; | |
return result; | |
} | |
else { | |
first = second; | |
return false; | |
} | |
}; | |
} | |
// returns true if the array is sorted by the given function | |
function isSortedBy(array, sortFunc) { | |
// here, find() is searching for any array items that are not sorted according to sortFunc() | |
return !_.find(array, isSortedByIterator(sortFunc)); | |
} | |
// returns the name of the sort type used for the array or "none". | |
// short-circuits once a matching sort function is found. | |
function getSortType(array) { | |
var matchingFunction = _.find(sortFunctions, function (sortFunc) { | |
return isSortedBy(array, sortFunc); | |
}); | |
return matchingFunction ? matchingFunction.name : "none"; | |
} | |
// returns an array of sort types corresponding to the given lists | |
function getSortTypes(arrayOfLists) { | |
return _.map(inputs, function (list) { | |
var array = list.split(','); | |
return getSortType(array); | |
}); | |
} | |
results = getSortTypes(inputs); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment