multi-column sorting algorithms

[Structural Integrity]

I'm looking for a sorting algorithm that can sort multiple columns of a matrix. Very much like the ORDER BY statement in SQL.

1 3
2 4
1 4
2 3
2 4
1 3

resulting in:

1 3
1 3
1 4
2 3
2 4
2 4

I've been using a shellsort algorithm but when sorting the second column it does not keep the first sorted column. I sorted column 2 first, then column 1 but that wouldn't work. In the example above it would mess up the sorting of column 2 again.
I managed to get around this problem using an awfully complicated mechanism that involved scanning the sorted column and sorting only a subset the next column... recursively...

My question is if there is a sorting algorithm that naturally keeps previously sorted columns the way they were? Google hasn't been my friend in this, giving me many SQL tutorials.

[Gayle29uk]

This is a little outside my league (my days of reading Knuth are loooong gone) but wouldn't a Postmans sort work there?

[mbushell]

I may have misunderstood completely but is it possible to calculate the worth of each row and use that value in the shellsort? For example, which could be easily modified to handle matrixes of varied size. edit: only on testing on a large file of data my code doesn't really work, but it could!

[mist]

being a little rusty, is it not possible to use a modified quicksort, in that you use the basic algorithm, but once each 'group' gets to be all the same numbers you start sorting on column b instead. that way the searches are kindof integrated in to each other.

alternativly, if your data variation isn't too large you could use a multi dimensional array, and have each line of the matrix navigate through it and increment the number of like's by 1. then search through it at the end to get the values out. this should be very fast (and avoid recursion) if the data set is large and the data space small.

-mist

[queball]

Gah!

For quicksort etc, you sort a list by defining a compare operation on two elements of the list. In this case you compare two rows. You compare two rows by comparing the first number, then if they are equal, the second.

Along the same lines, think about how you would implement a string compare.

So that's the basic answer. But with all algorithms, the more you know about the data, the faster you can be. Hence the postman's sort.

[queball]

http://en.wikipedia.org/wiki/Sorting_algorithm might be useful, in particular take note that quicksort is unstable.

By the way, your example input isn't a permutation of the output.

[Structural Integrity]

Originally Posted by queball

By the way, your example input isn't a permutation of the output.

Now you mention it... edited for great numerical justice.

Reading up on your linkage now.

[mist]

what language are you coding in?

-mist

[Structural Integrity]

Originally Posted by mist

what language are you coding in?

-mist

C/C++

Why?

[mist]

curiosity - i should really code one for a site i'm working on, but it'd be in php anyway

[djbass]

From Robert Sedgewick - Algorithms*

A characteristic of sorting methods which is sometimes important in practice is stability. A sorting method is called stable if it preserves the relative order of equal keys in the file. For example, if an alphabetized class list is sorted by grade, then a stable method produces a list in which students with the same grade are still in alphabetical order, but a non-stable method is likely to produce a list with no vestige of the original alphabetic order. Most of the simple methods are stable, but most of the well-known sophisticated algorithms are not. If stability is vital, it can be forced by appending a small index to each key before sorting or by lengthening the sort key in some other way. It is easy to take stability for granted: people often react to the unpleasant effects of instability with disbelief. Actually, few methods achieve stability without using significant extra time or space.

* quite an awesome book covering algorithms in C++ for pretty much any situation.