• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

need to find quicksort that sorts in descending order ..ARG

 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey everyone, i have just been going back through some of the code i have written for my current project and realized i used alot of slow algorithms for sorting and started going back to change them, but for a certain segments of code i need to sort a vector of objects, containg double values, in descending order.Seems that i can only find a quicksort algorithm that sorts in ascending order.And by looking at the code i have for that algoirthm it seems like it owuld be easy to change, but it hasnt been.Deadline is coming up here next week and wouldnt mind a hand improving the speed with this algorithm.

Ill post the code i have written..(well changed to suit my needs) for the quicksort, now i just need it in descending order.Any help would be great
***just a note.the utility packet's getMean() method returns a double value



i have tryed swapping a few of the comparison signs and figured that might work..but i keep gettin an array index outa bounds error...so something is messing up.Anyways if anyone has time to take a gander it would be great.thanks
P.S-this is the code for the ascending order....works just perfect
-luc
[ March 21, 2005: Message edited by: luc comeau ]
 
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
There's no reason to write your own sorting routines, They're notoriously hard to get right, first of all, and they obviously add a maintenence burden. Worst of all, unmodified QuickSort has some serious worst-case performance issues.

To sort a Vector, you can simply use the static sort(List) method in java.util.Collections. There's a version that takes a Comparator as a second argument, and so you can control the sort order simply by supplying an appropriate Comparator object. These sort methods perform very well in real-world situations and avoid the worst-case behavior.
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hey Ernest,
You make a valid point about not writing my own sorting routine.I am considering your request about using the sort method in that class, but i have a problem, its going to use the compareTo method to compare the obejcts in the list i pass to it...but how is it going to know if my UtilityPacket 1, is greater then UtilityPacket 2....if i have writen that class myself?What exactly does it compare?I need it so that it only compares the means of each UtilityPacket then swaps the entire obejct itself based on the comparison.

If i passed it a list with just the means in it, and it ordered that list of means(double values) that does me no good because now the utilityPackets name and standard deviation are no longer attached.Do you see my problem? Again i could be completly wrong about the compareTo thing becuase i am by no means a java expert.See if you can understand what iv said and try to straighten me out lol.Thanks again
P.S- in the mean time ill look at this "comparator" class, never used it before.
-luc
[ March 21, 2005: Message edited by: luc comeau ]
 
Stefan Willi
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi!

If you want to sort your object ina natural order, then the compareTo Method will fit to you. You have to implement the interface java.lang.Comperable and code your logic of comparing 2 objects.

If you want to sort your objects about different rules, then the java.lang.Comperator class will be the right for you.

Generally, each method wich compares tho object is returning an int value, which indicates the order. Have a look at API Comparable

stefan

and now, my leisure time is starting...
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hey,ok i remember now about writing your own compareTo method.Im prety sure i can do that easily.But in order to use the java.util.collections sort method for sorting in descending order i have to use the sort(list,comparator) method, and i dont know how to use this comparator class yet.Can any one maybe point to a direction that has some good examples of using this class, or maybe if its not hard think one up for how i would use it.No stress if its too hard dont worry about it.Thanks
-luc
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
heres the compareTo method, works fine.

can i use this somehow with comparator?Bah i just need an example lol
 
Horatio Westock
Ranch Hand
Posts: 221
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

To create a comparator, you simply need to create a class that implements the Comparator interface, that is, implements the method "public int compare(Object o1, Object o2)"

So, since you have a compareTo method for your type, you can basically use that in you implementation:



Now, to give yourself control over the sort order, you just need to add a constructor to TestComparator that allows you to pass in a value indicating the order (this could be a simple boolean, or some enumerated type). In the constructor, store this value somewhere. Then in the compare method, change the sort order based upon the value. In the case of a simple ascending/descending order, you can simply negate the value from compareTo.
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi horatio, first off cool name
Second
In the case of a simple ascending/descending order, you can simply negate the value from compareTo.


This is kind of unclear to me.
Say i write a constructor something like...
//have a private variable descending, if its true then the ordering should be //in descending
public TestComparator(Boolean descendingIn){
descending=descendingIn;
}
now say if i construct this class with TestComparator(true),how exactly am i to use that input value of true to make sure the list sorts in descending order?I kindof get the idea that i would say somewhere in my compare method
if(descending)
then..somehow make sure it sorts in descending order...but i duno how to do this.
If you can be a little more clear that would be awesome.Thanks again for your help.
-luc
 
Horatio Westock
Ranch Hand
Posts: 221
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about:

 
Manish Malik
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by luc comeau:
now say if i construct this class with TestComparator(true),how exactly am i to use that input value of true to make sure the list sorts in descending order?I kindof get the idea that i would say somewhere in my compare method
if(descending)
then..somehow make sure it sorts in descending order...but i duno how to do this.


If you check the Java Documentation for

Comparable Interface and the description of compareTo method there, you'll see that the way sort is done depends upon the return value of the compareTo method.

Reverse the return value (positive <-> negative) based upon the boolean flag passed in the constructor, and experiment this way forward.
 
Horatio Westock
Ranch Hand
Posts: 221
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I might just point out, that while this is a nice little discussion about creating comparators, since your type implements comparable (has compareTo), you can just use Collections.reverseOrder() to get a comparator that reverses the natural order. E.g.



It is good to know how to create customer comparators (for more complex sort conditions), but if you just want to get the reverse of the natural order, you can use the above.
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Excellent discussion, i think i understand whats goin on now, and infact i have tryed this both ways that Horatio has suggested.I wrote my own class...basically like his and that works, also tryed with the reverseOrder() as well and it works too.So i guess this thread has answered my question and in record breaking time!!Much apprieciated folks!Time to see how speedy this is comparative to the sorting method i had in the very first post(even though it didnt exactly dowhat i wanted lol).I noticed this sort method in the Collections class uses a variation of the merge sort...and since i know that the quick sort is a variation or the merge sort...minus the merge, it must be relatively close in the test times.
Anyways thanks everyone!
-Luc
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As EFH points out above, the implementation of Collections.sort() might actually run quicker than your implementation (once you fix it). The difference is that Collections.sort() is fine-tuned so that it is guaranteed to always run in O(n*log(n)). However, in the worst case, a unmodified quick sort can degrade to O(n^2). IIRC, the worst case for quick sort is an already-sorted array, however you should look this up to be sure. Sorting is a well-known topic and there is information all over the Web about it.

I apologize if this is a bit too technical. If you are unfamiliar with Big-Oh notation, I suggest that you do some research, either through Google or a text. In particlar, Big-Oh notation is part of the broader topic of Analysis of Algorithms.

Keep Coding!

Layne
 
luc comeau
Ranch Hand
Posts: 97
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks layne!Yes i am familiar with the Big Oh , but non the less possibly when other people read this thread they may learn something, right?, thats what these forums are for .Thanks.

P.S-i got the hole shabang working and its just as fast as the origianl quicksort i was using(which was way too complicated to post on here for people to try to help me fix).I am doing many other recursive calls and calculation in my program and it still managed to sort 2^18 elements in a little under ten seconds.Although 2^19 i run out of memory lol...its not a big deal though considering i don't think my program will ever have to sort any more then 2^10 elements so all in all it works terrific!
-luc
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic