Skip to content

Instantly share code, notes, and snippets.

@russplaysguitar
Last active December 15, 2015 14:59
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save russplaysguitar/5278189 to your computer and use it in GitHub Desktop.
/* 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