programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Algorithms: Sorting data on basis of three columns

Ranch Hand
Posts: 209
I wanted to sort a few records on the basis of multiple columns. I mean I want the records to be sorted by:
• a particular column
• then sort the resulting sort from above by another column (maintaining the sort result from above)
• and again sort the above resulting sort on the basis of a third colunm

• I have been thinking along the lines of the following data:

I wanted to know if this method is a good one. It sure looks messy to me and I am not convinced of using this method. Are there any better alternatives available?

Ken Blair
Ranch Hand
Posts: 1078
Won't they be in the correct order if you simply sort them three times, starting with the third thing you want it sorted on and moving to the second then the first, each time using the results of the previous sort? you should be able to do each sort using a different Comparator and Collections.sort(List, Comparator).

For example, if I wanted to sort by name, followed by age, followed by income I could do something like this (presuming Employee had all those):

I have absolutely no idea if this will work, but somehow it makes sense to me at 1 AM in the morning. I would test it, but I'm too lazy to figure out where the heck I have a compiler on here since I don't work from home anymore.

Tom Fulton
Ranch Hand
Posts: 96
No, that won't work. If you sort customers by balance (for example), then sort them by name, the name sort will effectively "destroy" the results of the first sort. What you want is compareTo( ) that sorts on the second column if the result of the compareTo( ) method is 0. Then you sort on the third column if the result of that is also 0. Something like this:

It's nasty...you can eliminate the multiple returns, of course, but essentially you have to "nest" the compareTos.

I suppose there is no real reason you couldn't call one comparator from another comparator...I'll have to work that code out.
[ May 05, 2006: Message edited by: Tom Fulton ]

Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Ken is actually right if the sorting algorithm in use is "stable". A "stable" sort preserves the original order of equal items. Unfortunately, most fast sorting algorithms are not stable with the exception of merge sort, which unfortunately uses the most auxillary space of any sorting algorithm. But bubblesort and insertion sort are stable!

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
I'll accept it if you think this is a flaw in me and not your code, but I can't bear "else" after "return".

To avoid the multiple returns, I sometimes do it this way:

Those compareTo() fall down if you have primitive members. Darned hybrid langauges anyhow.

Tom Fulton
Ranch Hand
Posts: 96
Yeah, you're right...especially if there a a LOAD of returns, I would prefer to have a single return at the end, just setting the value to the appropriate one based on the algorithm. I don't have a philosophical problem with multiple returns (even the developers of Structure Programming became less than absolute on that point), but for prototyping I usually write really nasty code, then clean it up.

I get the sense that there is a much more graceful way to do this, and will see if I can present it here...if I ever find it.

Tom Fulton
Ranch Hand
Posts: 96
OK, here we go...much better:

Each individual comparator encapsulates the sorting for a particular field sort, and the overall comparator calls the compare method (I misspoke earlier, not compareTo( ) obviously). This technique has the benefit of being relatively clean, and leaving the existing comparison methods in place if you want to sort on a single field.

If you wanted to be really slick, you could pass a parameter to the constructor of the complex comparator to specify the order of field sorting.

Ken Blair
Ranch Hand
Posts: 1078
Originally posted by Tom Fulton:
No, that won't work. If you sort customers by balance (for example), then sort them by name, the name sort will effectively "destroy" the results of the first sort.

No it won't. As Ernest mentioned it must be "stable", here's an excerpt from Collections.sort() API:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

It's just horribly inefficient, so I wouldn't be using it if I cared at all about performance, which may or may not be a concern depending on how big the List is and how often it needs to be sorted.
[ May 05, 2006: Message edited by: Ken Blair ]