|
5 Jan 2005, 21:49
|
#1
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
multi-column sorting algorithms
I'm looking for a sorting algorithm that can sort multiple columns of a matrix. Very much like the ORDER BY statement in SQL.
Code:
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.
__________________
"Yay"
Last edited by Structural Integrity; 6 Jan 2005 at 18:51.
|
|
|
5 Jan 2005, 23:08
|
#2
|
Bitch
Join Date: Jun 2002
Location: North Yorkshire
Posts: 3,848
|
Re: multi-column sorting algorithms
This is a little outside my league (my days of reading Knuth are loooong gone) but wouldn't a Postmans sort work there?
__________________
ACHTUNG!!!
Das machine is nicht fur gefingerpoken und mittengrabben. Ist easy
schnappen der springenwerk, blowenfusen und corkenpoppen mit
spitzensparken. Ist nicht fur gewerken by das dummkopfen. Das
rubbernecken sightseeren keepen hands in das pockets. Relaxen und vatch
das blinkenlights!!!
|
|
|
5 Jan 2005, 23:44
|
#3
|
Registered User
Join Date: Jul 2000
Location: :noitacoL
Posts: 1,200
|
Re: multi-column sorting algorithms
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!
Last edited by mbushell; 6 Jan 2005 at 00:12.
|
|
|
6 Jan 2005, 01:41
|
#4
|
Jolt's best friend
Join Date: Feb 2003
Posts: 2,101
|
Re: multi-column sorting algorithms
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
__________________
<Karmulian> subtle as a kick in the nuts as always
|
|
|
6 Jan 2005, 02:36
|
#5
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Re: multi-column sorting algorithms
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.
|
|
|
6 Jan 2005, 03:36
|
#6
|
Ball
Join Date: Oct 2001
Posts: 4,410
|
Re: multi-column sorting algorithms
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.
|
|
|
6 Jan 2005, 18:52
|
#7
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
Re: multi-column sorting algorithms
Quote:
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.
__________________
"Yay"
|
|
|
6 Jan 2005, 22:56
|
#8
|
Jolt's best friend
Join Date: Feb 2003
Posts: 2,101
|
Re: multi-column sorting algorithms
what language are you coding in?
-mist
__________________
<Karmulian> subtle as a kick in the nuts as always
|
|
|
7 Jan 2005, 17:44
|
#9
|
Rawr rawr
Join Date: Dec 2000
Location: Upside down
Posts: 5,300
|
Re: multi-column sorting algorithms
Quote:
Originally Posted by mist
what language are you coding in?
-mist
|
C/C++
Why?
__________________
"Yay"
|
|
|
7 Jan 2005, 18:45
|
#10
|
Jolt's best friend
Join Date: Feb 2003
Posts: 2,101
|
Re: multi-column sorting algorithms
curiosity - i should really code one for a site i'm working on, but it'd be in php anyway
__________________
<Karmulian> subtle as a kick in the nuts as always
|
|
|
8 Jan 2005, 10:34
|
#11
|
mmm.. pills
Join Date: Apr 2000
Location: Australia
Posts: 2,152
|
Re: multi-column sorting algorithms
From Robert Sedgewick - Algorithms*
Quote:
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.
__________________
CSS : the result of letting artists design something only an engineer should touch.
|
|
|
|
All times are GMT +1. The time now is 13:09.
| |