Sorting?

[Alex Buell]

HI,

What would be the best way to sort a table of strings stored in a
array list. For example:

Col1 Col2 Col3 Col4
item item item item
item item item item

I'd like to be able to order the table on Col1, then Col3, then Col4.
I thought of using Map but it can't handle what I have in mind.

Cheers,
Alex.

 

[Antti S. Brax]

HI,

What would be the best way to sort a table of strings stored in a
array list. For example:

Col1 Col2 Col3 Col4
item item item item
item item item item

I'd like to be able to order the table on Col1, then Col3, then Col4.
I thought of using Map but it can't handle what I have in mind.

You need to store each row in it's own container (array, ArrayList,
etc). Then you put those containers to a list and sort that list
using your own comparator. In this comparator, you first test the
item in first column and if those are equal you test the item in
the third column and so on.

 

[bugbear]

HI,

What would be the best way to sort a table of strings stored in a
array list. For example:

Col1 Col2 Col3 Col4
item item item item
item item item item

You appear to be storing a 2 diminsional
object in a 1 dimensional data structure
(assuming by "array list" you mean ArrayList)

I suspect this is not the ideal approach.

BugBear

 

[Alex Buell]

You appear to be storing a 2 diminsional
object in a 1 dimensional data structure
(assuming by "array list" you mean ArrayList)

What I had in mind was four strings per item that needed sorting into
order on first string then third string, finally fourth string.
Perhaps I wasn't too clear.

Cheers,
Alex.

 

[bugbear]

What I had in mind was four strings per item that needed sorting into
order on first string then third string, finally fourth string.
Perhaps I wasn't too clear.

In that case Antti S. Brax has given
an excellent approach.

BugBear

 

[steepyirl]

Another way you can do this is to use a stable-sort algorithm to sort
the list first based on Col5, then sort based on Col4, etc. until you
get to Col1. When you're done, the items will be in the correct order.

 

[Alex Buell]

Another way you can do this is to use a stable-sort algorithm to sort
the list first based on Col5, then sort based on Col4, etc. until you
get to Col1. When you're done, the items will be in the correct order.

Sounds like a good idea, thanks.

Cheers,
Alex.

 

[ridvansg]

The fastest way is to store the items not in array but tree, it is
sorted by default. I think there are HashTree and other kind of
implementations of tree within java which can substitude the array.
Ridvan

 

[bugbear]

The fastest way is to store the items not in array but tree, it is
sorted by default. I think there are HashTree and other kind of
implementations of tree within java which can substitude the array.

Sequential insertion into a sorted structure
is not quicker than bulk sorting.

In the case of a tree, it's effectively insertion
sort, which is O(N^2) as opposed to quicksort or merge sort
which are O(NlogN)

BugBear

 

[Lasse Reichstein Nielsen]

Sequential insertion into a sorted structure
is not quicker than bulk sorting.

Indeed. It can't be, since bulk sorting can be O(NlogN), which
is as fast as a comparison based sort can be.

In the case of a tree, it's effectively insertion
sort, which is O(N^2) as opposed to quicksort or merge sort
which are O(NlogN)

If the tree is a balanced tree (like a red/black tree, which I believe
TreeSet uses), you can guarantee both finding the place to insert and
doing the insertion in logaritmic time, so it will never be O(N^2).

The "problem" for insertion sort into an ordered sequence is that
insertion into an array can take linear time (because you have to move
the rest of the list to make room for one element). Insertion into a
linked list is fast, but finding the place to insert is slow instead.

/L

 

[Esmond Pitt]

Sequential insertion into a sorted structure
is not quicker than bulk sorting.

In the case of a tree, it's effectively insertion
sort, which is O(N^2) as opposed to quicksort or merge sort
which are O(NlogN)

Where do you get this? In the case of a tree it is effectively heapsort
or red-black or AVL or 2-3 or B-tree or +-tree orB*-tree or any of a
large number of other tree insertion algorithms all of which are O(N log
N). Quicksort is still quicker on the average but only by small constant
factors, not by any O() differences, and the worst case bounds are much
higher than for trees.