 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / October 2005Algorithm
There are two parts to this question. The first is directly Java related, the second is an algorithm issue. I would like to use the built in quicksort functionality, but have different input parameters that can be used to sort it. Am I going to require a derived class for each and every sort criterion? In this particular instance I would like to be able to sort by path, file name, size, extension and checksum. Is the "correct" answer to write my own quicksort function which takes a parameter detailing which item is being sorted? Second, I would like to store sorted lists of all the files, presorted by each criterion in arrays. What is the best method to "link" these together? It feels like an OOP violation to put the intelligence of an outside container in the object. Should I use a container class with an array of indices to each of the sorted items? -- LTP :) > I would like to use the built in quicksort functionality, but have different > input parameters that can be used to sort it. Am I going to require a > derived class for each and every sort criterion? No. See java.util.Comparator. Daniel Sjöblom On Sat, 29 Oct 2005 11:04:02 -0600, "Luc The Perverse" <sll_noSpamlicious_z_XXX_m@cc.usu.edu> wrote, quoted or indirectly quoted someone who said : >I would like to use the built in quicksort functionality, but have different >input parameters that can be used to sort it. Am I going to require a >derived class for each and every sort criterion? In this particular >instance I would like to be able to sort by path, file name, size, extension >and checksum. Is the "correct" answer to write my own quicksort function >which takes a parameter detailing which item is being sorted? Look at how Sun solves this problem using a Comparable and Comparator interface. see http://mindprod.com/jgloss/sort.html http://mindprod.com/jgloss/comparator.html http://mindprod.com/jgloss/comparable.html You do end up writing a tiny class for nearly every sort, but you don't need whole new sort class.  SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. On Sat, 29 Oct 2005 11:04:02 -0600, "Luc The Perverse" <sll_noSpamlicious_z_XXX_m@cc.usu.edu> wrote, quoted or indirectly quoted someone who said : >Second, I would like to store sorted lists of all the files, presorted by >each criterion in arrays. What is the best method to "link" these together? >It feels like an OOP violation to put the intelligence of an outside >container in the object. Should I use a container class with an array of >indices to each of the sorted items? You sort three arrays or ArrayLists each containing the references to the objects to be sorted. There is one set of objects but three sets of references to them, each in a different order. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > On Sat, 29 Oct 2005 11:04:02 -0600, "Luc The Perverse" > <sll_noSpamlicious_z_XXX_m@cc.usu.edu> wrote, quoted or indirectly [quoted text clipped - 10 lines] > the objects to be sorted. There is one set of objects but three sets > of references to them, each in a different order. Yes that was the plan. My problem is coming when I want to delete the same object from each of the three arrays at the same time. (I will have found it by looking through only one of the arrays. However, I had a bit of time to ponder it, and I came up with a few ways. The object itself could have a "Deleted" variable, and I could just ignore entries with this flag set. Although it will be cluttered after a time, I never expect to have so many objects that it becomes a serious issue (efficiency only, I was never planning on shrinking the array). My original idea was to have an array listing the index in every array, with a copy for every object. Several variations on this theme, but they all did basically the same thing. But I was overlooking an exceptionally relevant fact. All of these arrays are going to have already been sorted. I don't need a linear search for them, I could just use a binary search. :) -- LTP :) On Sat, 29 Oct 2005 19:59:36 -0600, "Luc The Perverse" <sll_noSpamlicious_z_XXX_m@cc.usu.edu> wrote, quoted or indirectly quoted someone who said : >Yes that was the plan. My problem is coming when I want to delete the same >object from each of the three arrays at the same time. (I will have found >it by looking through only one of the arrays. Sorted arrays are not insert/delete friendly. They are a batch-think tool. Have a look at the ArrayList.remove method. You can do it by index or by object. By object requires a linear scan of each of the three arrays. There is then a block move to shuffle all high elements down one in each array. If this is something you don't do often, delete the object from the original pool, recreate the three arrays and resort them. This may sound extravagent, but the same code will work no matter how many arrays and sub collections you create. You don't need to carefully maintain the delete logic. Another approach is instead of removing the object, just invalidate it so that it is ignored ever after, including any rebuild of the array where it will be permanently dropped. You might be interested in my SortedArray class that handles many of these things for you. See http://mindprod.com/products1.html#SORTED SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > On Sat, 29 Oct 2005 19:59:36 -0600, "Luc The Perverse" > <sll_noSpamlicious_z_XXX_m@cc.usu.edu> wrote, quoted or indirectly [quoted text clipped - 28 lines] > > See http://mindprod.com/products1.html#SORTED Thank you -- LTP :) > There are two parts to this question. The first is directly Java related, > the second is an algorithm issue. > > I would like to use the built in quicksort functionality, but have different > input parameters that can be used to sort it. [ snipped ] Read up on comparable interface, and use Arrays.sort() method. Like { ArrayList a = new ArrayList(); //fill up the arraylist Arrays.sort(a.toArray()); //this is a quicksort impl provided by java. } Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.