Sorting Arrays
In some cases, you might want to sort an array. It might be an array of objects or a primitive array. Either way you can use the java.util.Arrays class to sort the array.
This method uses a modified quick sort algorithm that runs in 0(nlogn) time. This is considerably faster than bubble sort and other sort algorithms.
The java.util.Arrays class defines a static sort method for each primitive data type and a method that takes an array of type Object. This allows you to sort an array of any data type you want.
This method is a void method because arrays are based by reference. Thus if the array is modified in the function, then the array is modified outside of the function as well. If you want to retain the array, you must use the Arrays.copyOf method to make a copy of it before you pass it to the sort method.
Examples of sorting:
The for loops are to show you the output to notice, that the arrays are now in ascending order. The String sort takes a bit more explanation though. The strings are sorted by there unicode values. Which is a value for the string by adding all the ASCII values for each character together.Code:int[] v = {3,2,7,4,-1,5}; long[] l = {3,2,5,4,3,2,5,9}; String[] names = {"James","bob","test"}; Arrays.sort(v); Arrays.sort(l); Arrays.sort(names); for (int i=0;i<v.length;i++) { System.out.print(v[i] + " "); } System.out.println(); for (int i=0;i<l.length;i++) { System.out.print(l[i] + " "); } System.out.println(); for (int i=0;i<names.length;i++) { System.out.print(names[i] + " "); } System.out.println();
I'm a bit disappointed in this class that it defines a sort method for each data type. It would be much more maintainable if it used a generic method. However, generic methods don't work with primitives to they are left with no choice.
Example of sorting and retaining the original array:
This allows you to retain the original array, and get a copy that is sorted.Code:int[] v = {3,2,5,7,9,2,4}; int[] copy = v.clone(); // Now we can pass the array to the method Arrays.sort(v);
If you don't know how I copied the array, see my tutorial here: Copying Arrays.
Comparator
To sort objects of a programmer defined data type the data type you supporting must implement the Comparable interface.
Let us first define a class that we can use:
The compareTo method takes an object to compare with and returns 1 if the passed object's i value is less than the other object's i value. It will return 0 if they are equal and -1 otherwise. This is all the Arrays.sort method needs.Code:class nums { int i; nums(int i) { this.i = i; } public int compareTo(Object o) { nums temp = (nums)o; if (temp.i < i) { return 1; } else if (temp.i == i) { return 0; } return -1; } }
Now we are going to create an array of nums with random numbers.
First we allocate an array of 10 nums and then initialize 10 objects. Now if you call Arrays.sort by passing aroNums the array will be sorted based on the i values.Code:nums[] aroNums = new nums[10]; for (int i=0;i<10;i++) { aroNums[i] = new nums((int)(Math.random()*10)+5); }
Output:Code:for (int i=0;i<aroNums.length;i++) { System.out.print(aroNums[i].i + " "); } System.out.println();
This comes in handy with different programming problems, and in the implementation of different data structures.5 5 5 6 10 11 12 14 14 14
Try this problem out:
London Knights. This is an exercise in sorting objects.


LinkBack URL
About LinkBacks





Reply With Quote










Bookmarks
Algorithms and Data Structures
Java tutorials
Algorithms Forum