Algorithm

[Luc The Perverse]

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?

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

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

 

[Roedy Green]

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.

 

[Roedy Green]

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.

 

[Luc The Perverse]

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.

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.

 

[Roedy Green]

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

 

[Luc The Perverse]

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

Thank you

 

[HalcyonWild]

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.
}