[ProgSoc] Multi-index sorting algorithms

Nicholas FitzRoy-Dale wzdd at progsoc.org
Sun Dec 26 13:32:06 EST 2010


On 21 Dec 2010, at 00:57, James Ducker wrote:

> I'm trying to write a sorting algorithm that can sort a set of data
> (the usual, lowest to highest, A-Z, etc), but when it encounters a tie
> condition between two values, will defer sorting to another set of
> data, which I call the "tiebreaker" set.

Conceptually what you are doing is sorting 2-tuples of (datum, tiebreaker). Thus any sorting algorithm will work: it will sort by <datum> first, and then by <tiebreaker>.

This is how you'd do it in Python inefficiently, by eagerly creating a new list of 2-tuples:

sortme = [(element, get_tiebreaker(element)) for element in data]
sortme.sort()

... a more efficient method doesn't create an intermediate list:

def tiebreakingcmp(lhs, rhs):
	if lhs == rhs:
		return cmp(get_tiebreaker(lhs), get_tiebreaker(rhs))
	else:
		return cmp(lhs, rhs)

data.sort(cmp = tiebreakingcmp)

... "cmp" as used in tiebreakingcmp is a Python function that returns -1 if lhs < rhs, 0 if lhs == rhs, and 1 if lhs > rhs. There are lots of ways to make tiebreakingcmp smaller.

This second example looks like it's very close to what JavaScript supports. Looks like you can do something like:

function tiebreakingsort(lhs, rhs) {
	if (lhs == rhs) {
		return get_tiebreaker(lhs) - get_tiebreaker(rhs);
	} else {
		return lhs - rhs;
	}
}

data.sort(tiebreakingsort);

Any sort algorithm comes down to comparing two elements and deciding whether element A is greater than, equal to, or less than (for some definition of...) than element B, so you can use any sort algorithm and plug your tie-breaking sort into it. 

N




More information about the Progsoc mailing list