Sorting Data In Java

• Download source files - 6.19 Kb

Introduction

Last week I posted an article on a simple C++ template class, XYDataArray, I used in my system development tool. The main purpose of this template class is to store and sort general data types. I needed to implement the same thing in Java, since the tool I developed has a compatible Java version. I checked the Java SDK documentation before writing my own code, and found that almost everything I needed is already there, like the C++ case.

For example, the java.util.Vector class is the kind of array I want, it can dynamically change its size. There are also various implementations of stable sort algorithms in the java.util.Arrays class. For example, the following line of code will sort a Java Object array in ascending order.

Arrays.sort(myArray);

And the sort is guaranteed to be stable (equal elements will not be reordered). The objects in myArray has to be mutually comparable, of course (implementing the Comparable interface). There are other forms of the Arrays.sort method that can be used to sort primitive data types (int, double, etc.) and even subarrays. What about sorting in descending order (note that sorting in ascending order and then reversing the orders of all elements makes it unstable)? In that case, you have to implement a Comparator class and pass an object of this class along with the data array, into another Arrays.sort method. This is like passing a function pointer to a generic sort function in C++. It is not exactly what I wanted. For example, I don't want to implement a different Comparator class for each different way I want to sort my data. What I really need is sorting the indices instead of the data array itself. For example, I want to get the index of the 10th largest element or the index of the 6th smallest element in my array. The SortIndex method in my C++ code will give me exactly what I needed. The best part about the SortIndex method is, I can use it repeatedly to do multi-column sorting on tabulated data (each column is in a separate array) without rearranging the data elements! So I converted my C++ template class, XYDataArray, into a Java class, XYObjArray.

The XYObjArray class is almost identical to its C++ counterpart except that there is no template or operator overloading in Java. In order to use the sort feature, objects in this class have to be mutually comparable (implementing the Comparable interface). I have included source code and a simple test program. There is no restriction on using the source code. The test program creates an array with randomly generated data and then sorts the array (and also verifies that the sort is done correctly). Here is the command line that runs the test program, assuming you already compiled the code and set the correct ClassPath.

java ArrayTest

Here are the descriptions of the methods in XYObjArray:

Methods

• public XYObjArray( );

  This method constructs an empty array.

• public XYObjArray(Object[ ] pObj, int nGrowBy);

  This method constructs an array with given Object array pObj. The nGrowBy parameter specifies how the array's internal buffer grows or shrinks. The nGrowBy = 64 means that the internal buffer will grow in multiples of 64 elements.

• public final synchronized int Find(Object obj);

  This method returns the index of obj within the array. The return value is -1 if obj is not found. If the array is already sorted, this method will use binary search instead of linear search.

• public final synchronized int Locate(Object obj);

  This method returns the position at which to insert a new element obj. If the array is already sorted, inserting at the returned position will keep the array sorted.

• public final synchronized void SetSize(int nSize, int nGrowBy);

  This method changes the size of the array. If the new size is bigger than the original size, the array will be chopped. Otherwise, null elements will be added if necessary. In any case, the original elements, except the ones being chopped off, will be preserved.

• public final synchronized int GetSize( );

  This method returns the current size of the array.

• public final synchronized Object[ ] GetDataPtr( );

  This method returns the internal data buffer.

• public final synchronized Object GetAt(int nIndex);

  This method returns the element at the position nIndex.

• public final synchronized int Add(Object obj);

  This method adds a new element obj to the array. If the array is already sorted, adding the new element will keep the array sorted. Otherwise, the new element will be appended to the end of the array. The return value is the position of the newly added element.

• public final synchronized int Insert(int nIndex, Object obj);

  This method inserts a new element obj to the array at position nIndex. The return value is -1 if nIndex is invalid (out of the range between 0 and the size of the array). Otherwise, it returns nIndex.

• public final synchronized int Remove(int nIndex);

  This method removes the element at position nIndex from the array. The return value is -1 if nIndex is out of range. Otherwise, it returns the size of the new array.

• public final synchronized int SetAt(int nIndex, Object obj);

  This method assigns the element obj to position nIndex in the array. The return value is -1 if nIndex is out of range. Otherwise, it returns nIndex.

• public final synchronized void Push(Object obj);

  This method adds a new element obj to the end of the array.

• public final synchronized Object Pop( );

  This method removes an element from the end of the array, the return value is the element being removed.

• public final synchronized int GetSort( );

  This method returns 1 if the array is sorted in ascending order, it returns -1 if sorted in descending order. Otherwise, it returns 0.

• public final synchronized void SetSort(int nSort);

  If nSort is 1, it will sort the array in ascending order if not already sorted. If nSort is -1, it will sort the array in descending order if not already sorted.

• public final synchronized virtual void Sort(int nSort);

  This method sorts the array. nSort specifies what order to sort, 1 for ascending, -1 for descending.

• public final synchronized virtual void SortIndex(int[ ] arrayIndex, int nSort);

  This method does not sort the array itself, instead, it sorts an index array according to the specified order. arrayIndex must be an integer array containing integers 0, 1, 2, ..., nSize-1, where nSize is the size of the current array. The Sort method is implemented using this method. The algorithm is a combination of insertion sort and "randomized" quick sort. The performance is as good as the Arrays.sort method in Java JDK for randomly generated data, according to my tests. The Arrays.sort method performs better when the input data is nearly sorted.