Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Algorithms: Sorting data on basis of three columns

 
Shyam Prasad Murarka
Ranch Hand
Posts: 209
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dear Readers,
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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    Marshal
    Pie
    Posts: 24211
    35
    Chrome Eclipse IDE Mac OS X
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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 ]
     
    • Post Reply
    • Bookmark Topic Watch Topic
    • New Topic