sort : Java Glossary

Internal Sort

In the JDK 1.2 there are built-in sorts such as Arrays.sort and Collections.sort See java.util.Comparator and java.util.Comparable for different sorting orders. For String sorting in various international orders see java.text.Collator, java.text.RuleBasedCollator, and java.text.CollationKey.

In the simplest case, you can sort an array like this:

import java.util.Arrays;
//...
// works for:
// int[] myArray;
// Object[] myArray;
// Dog[] myArray;
// byte[] myArray;
// etc.
Arrays.sort( myArray );

import java.util.ArrayList;
import java.util.Collections;
...
Collections.sort( myArrayList );

Note that there is no such method as ArrayList.sort.

Gotchas

• Though it is called Collections.sort, the fool thing cannot sort arbitrary Collections. It can only sort Lists. It should have been called Lists.sort.
• The sort method is not part of the Collection interface. It lives in the Collections class. So you cannot say myCollection.sort(). You must say Collections.sort( myCollection ); However, sort will not work on Collections generally, only Lists.
• Collections.sort will not work on arrays. You must use Arrays.sort.

Comparators

return -( (String )a ).compareTo( (String)b );

Comparables

Sorting Speed

In the following table, speed is measured relative to RadixSort on a 100,000 item set of 5-character random keys of the form A9999 where SunSort is arbitrarily assigned 100. Tests done under Java 1.4.1 java.exe on a 233 MHz Pentium 128 MB RAM. Bigger is better.

External Sort

Abundance uses Op-Tech sort. It rolls itself out to disk, calls in Opt-Tech sort, giving it all of RAM, then rolls itself back in.

Merge Sort

You might experiment with a merge sort to use on a dual core CPU. You split the data in two. Sort each on a separate thread then merge the results in a single pass.

Tag Sort

1. Combine the two arrays into one, with objects having two or more fields. Write a Comparator or implement Comparable for these new combined objects.
2. Sorts don’t actually sort the records, they just order an array of references. The objects themselves don’t move. If the things you are sorting are not collected nicely together into objects you can use a tag sort. Tag records are short records consisting of the sorting key fields plus a reference back to the original record. This reference may be an array index or a pointer to the original object. The tag records need not contain any data at all, just a way to find it when the comparator is called.
3. Use the cern.colt.GenericSorting class.

Bad Sorts

One is a selection sort:

1. Select the largest of the N keys and move its record to the output area.
2. Select the largest of the remaining N-1 keys and move its record to the output area. etc.

A variant of the bubble sort, that is a tiny bit faster is the bi-directional sort that percolates the smallest element to the bottom and the biggest element to the top in alternating direction passes, gradually working toward the middle. Sun has built an

Another is the insertion sort, where you create a new list and gradually add to it, always keeping the new list in sorted order by inserting the new element in the place where it belongs. You find the place by binary search, and slide all the subsequent elements down to make room for it. You sometimes have to use this type of sort when you don’t have all the elements at the start of the sort. They are just given to you one at a time, and you want a sorted list immediately output after each element is added.

Ordered Collections

Descending/Inverse/Reverse Order with reverseOrder

If you have a Comparator or Comparable of some kind, you can convert it into one that sorts into the reverse of the usual order. E.g. if the original sorts alphabetically, the new one will sort in reverse alphabetical order. Here is how you use it:

If you don't have a suitable base Comparator, just write an ordinary Comparator from scratch and reverse the operands to each compare inside it, or return - result instead of result.

Ascending/Descending Arrow Indicators

• Up is ascending because ascending means climbing up. It has nothing to do with the order of the items on the page.
• Up is ascending because up connotes normal and happy and so does ascending.
• Up is ascending because the indicator represents the keyword the programmer gave to the SQL sort to get items to paint top to bottom. He did not actually paint bottom to top for descending order. By default, you get ascending. When you talk of up and down, usually up is the default. So the two are associated by both being the default.
• Up is ascending because when things on the page are ordered in ascending order, you see the small easy numbers first then work toward the more difficult. Climbing up, i.e. ascending stairs, is the difficult direction.
• Up is ascending because ascending elevators and escalators go up.

• Down is ascending because the bigger items are at the bottom of the page.
• Down is ascending because down is the direction you read to see ever-bigger items.
• Down is ascending, because the indicator means the direction of flow and of pull of gravity. It points downward toward the logical gravitation point attracting the bigger/heavier items.

• Whatever you think it is, it should be the opposite, because the arrow does not tell you how things are, but how they will be if you click the icon. The icon represents a command to sort, not an indictor of how things are.

Perhaps some day the association and icon choices will be a configurable part of look an feel so users will have consistent conventions across all the apps they use. Consistency is the problem.

I have found the majority up application use an upward arrow to indicate that items are displayed in ascending order.

My convention is to use an arrow pointing up and to the right to indicate the data are sorted in ascending order. This helps break the connection with reading direction, and suggests the climbing association.

No matter what you do, you are going do it “backwards” for some people, and irritate them. So you might use indicators that don’t have any arrows or at least no confusing up/down arrows. Let the user figure out what your colours or letters A/D mean for example.

Generic Sorts

However, because of Java’s lack of orthogonality, your List sort won’t work for arrays of such Objects. You need to write very similar code to do that. Even that array version won’t sort an array of primitives such as long, int or byte. You have to write yet another slightly different version of the sort to handle each type of primitive.

Complete Example

Learning More