Wednesday, August 13, 2014

4 Examples to Sort Array in Java

You can use Arrays.sort() method to sort both primitive and object array in Java. This method sorts given array into ascending order, which is numeric order for primitives and defined by compareTo() or compare() method for objects. For primitive arrays e.g. int,  short, character, float, double or long this method uses  dual-pivot Quicksort sorting algorithm implemented by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloach (author of Effective Java) . This algorithm offers O(n log(n)) performance on many data sets that cause other quicksort algorithms to degrade into their worst quadratic performance e.g. O(n^2), and is typically faster than traditional (one-pivot) Quicksort implementations. That's why I always said that prefer library method your own, you can get it right but amount of exposure library method gets, you will never get for your implementations. On the other hand object array is sorted using stable MergeSort algorithm, which ensures that equal elements keep their original position in sorted array. Implementation of mergesort used in sort(Object[]) is stable, adaptive, and iterative that requires much lesser than O(n log(n)) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. In best case, when input array is almost sorted, this implementation requires approximately O(n) comparisons. By the way temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays. In order to sort different types of array in Java, you can use any of the overloaded version of sort() method from Arrays class. It also has two special method for sorting object array, one sorts the array in natural order, while other sort them in custom order of provided comparator. Since two dimensional array is also array of array in Java, you can use any this method to sort multi dimensional array in Java also. We will see step by step examples of sorting all kinds of array in Java in subsequent section.


Sorting Array in Ascending Order

Sorting any primitive or object array in ascending order is very easy, all you need to know is sort() method from java.util.Arrays class. It provides overloaded method to sort byte, short, char, int, long, float, double and object arrays. This method sorts given array in increasing order using two pivot quicksort algorithm. You can use this method to sort any array of objects which implements either Comparable or Comparator method. It has and overloaded version, which accept Comparator for custom sorting. Here is an example to sort an int primitive array in ascending order in Java.

int[] random = { 33, 22, 11, 21, 55, 32, 3, 4 };
System.out.println("Array before sorting : " + Arrays.toString(random));
Arrays.sort(random);
System.out.println("Array after sorting in ascending order : " + Arrays.toString(random));

Output:
Array before sorting : [33, 22, 11, 21, 55, 32, 3, 4]
Array after sorting in ascending order : [3, 4, 11, 21, 22, 32, 33, 55]


How to Sort Integer Array in Java
Let's see one more example of sort() method, this time we will sort an array of Integer object instead of int primitives. First line may look similar, but remember autoboxing will convert each int value to Integer, but it can not convert an int[] to Integer[]. That's why sort method used here is sort(Object[]) and not sort(int[]), this is also obvious when we sort Integer array into reverse order, and passed a reverse order comparator from Collections class.
Integer[] elevens = { 44, 22, 55, 11, 33, 66, 77 };         
Arrays.sort(elevens);
System.out.println("increasing order : " + Arrays.toString(elevens));
Arrays.sort(elevens, Collections.reverseOrder());
System.out.println("reverse order : " + Arrays.toString(elevens));

Output:
increasing order : [11, 22, 33, 44, 55, 66, 77]
reverse order : [77, 66, 55, 44, 33, 22, 11]

Sorting String Array in Java - Ascending and Descending Order

String is not a numeric data, it defines it's own order which is called lexicographic order, also known as alphabetic order. When you sort an array of String using sort() method, it sorts array into natural order defined by Comparable interface, as shown below :

Increasing Order
String[] names = {"John", "Steve", "Shane", "Adam", "Ben"};
System.out.println("String array before sorting : " + Arrays.toString(names));
Arrays.sort(names);
System.out.println("String array after sorting in ascending order : " + Arrays.toString(names));

Output:
String array before sorting : [John, Steve, Shane, Adam, Ben]
String array after sorting in ascending order : [Adam, Ben, John, Shane, Steve]
        
Decreasing Order
Arrays.sort(names, 0, names.length, Collections.reverseOrder());
System.out.println("String array after sorting in descending order : " + Arrays.toString(names));

Output:
String array after sorting in descending order : [Steve, Shane, John, Ben, Adam]


Sorting Object Array in Java

In order to sort an object array, all elements must implement either Comparable or Comparator interface to define an order. You can use either use sort(Object[]) method to sort an object array on its natural order, you must ensure that all elements in the array must implement Comparable. Furthermore, they must be mutually comparable as well, for example e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the array. Alternatively you can sort an Object array on custom order using sort(T[], Comparator) method. as shown in following example.
// How to Sort Object Array in Java using Comparator and Comparable
Course[] courses = new Course[4];
courses[0] = new Course(101, "Java", 200);
courses[1] = new Course(201, "Ruby", 300);
courses[2] = new Course(301, "Python", 400);
courses[3] = new Course(401, "Scala", 500);
       
System.out.println("Object array before sorting : " + Arrays.toString(courses));
       
Arrays.sort(courses);
System.out.println("Object array after sorting in natural order : " + Arrays.toString(courses));
       
Arrays.sort(courses, new Course.PriceComparator());
System.out.println("Object array after sorting by price : " + Arrays.toString(courses));
       
Arrays.sort(courses, new Course.NameComparator());
System.out.println("Object array after sorting by name : " + Arrays.toString(courses));

Output :
Object array before sorting : [#101 Java@200 , #201 Ruby@300 , #301 Python@400 , #401 Scala@500 ]
Object array after sorting in natural order : [#101 Java@200 , #201 Ruby@300 , #301 Python@400 , #401 Scala@500 ]
Object array after sorting by price : [#101 Java@200 , #201 Ruby@300 , #301 Python@400 , #401 Scala@500 ]
Object array after sorting by name : [#101 Java@200 , #301 Python@400 , #201 Ruby@300 , #401 Scala@500 ]

How to sort Array in reverse order in Java

How to Sort Array in Java with Example
Sorting an object array in descending order is easy because Java API provides a sort() method which takes both array and Comparator, which can be used to sort array in reverse order. For example you can sort a String array in reverse order by using Collections.reverseComparator() method, which is a built-in reverse comparator from Collections utility class. You can sort all numeric arrays e.g. Integer, Double or Float using same technique. But, when it comes to sort primitive array in reverse order, you left with nothing. You can not sort primitive array with reverse comparator and Java doesn't provide a direct method for sorting in descending order. You can do two things, write your own method using any efficient sorting algorithm e.g. quicksort, to sort the array in descending order, or just sort the array using Arrays.sort() method and reverse it. Former can be a clean approach but you would likely going to get efficiency which comes with a library method like Arrays.sort(), which is a double pivot quicksort implementation and offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance. Second approach is better but will cost you additional O(n) performance. There is one more way, going via Collection route, you can convert array to list and sort the list on reverse order, but you will not get any performance benefit.


How to Sort Two dimensional Array in Java

There is no easy way to sort a multi-dimensional array in Java, Java API provides no direct method to sort a two or three dimensional array, may be because it's not clear how do you want to sort a multi-dimensional array. If you want to sort your two dimensional array on columns then you can use our ColumnComparator class which implements Comparator interface to sort column data. You can see the full code of this class in our program section. It also uses Java enum to define sorting order e.g. ASCENDING and DESCENDING, which is much better than a blank boolean variable. In following examples, we first sort a two dimensional array in ascending order on first column, while in second example we sort it on increasing order but  this time only second column. If you want to sort all columns of a multidimensional array, you can just extend this program to iterate over array, and passing column index to ColumnCompartor.

Ascending Order on First Column
Integer[][] numbers = { {9, 6, 5}, {3, 2, 4}, {1, 5, 7} };
System.out.println("Two dimensional array before sorting : " + Arrays.deepToString(numbers));
Arrays.sort(numbers, new ColumnComparator(0, SortingOrder.ASCENDING));
System.out.println("2D array after sorting in ascending order on first column : " + Arrays.deepToString(numbers));

Output
Two dimensional array before sorting : [[9, 6, 5], [3, 2, 4], [1, 5, 7]]
2D array after sorting in ascending order on first column : [[1, 5, 7], [3, 2, 4], [9, 6, 5]]

Ascending Order on Second Column
Arrays.sort(numbers, new ColumnComparator(1,SortingOrder.DESCENDING));
System.out.println("Sorting two dimensional String array in Java, Second column, Ascending order : " + Arrays.deepToString(numbers));

Output
Sorting two dimensional String array in Java, Second column, Ascending order : [[9, 6, 5], [1, 5, 7], [3, 2, 4]]


Java Program to Sort Array in Java

Here is our complete Java program, which you can just copy paste and run in Eclipse by right click. Alternatively you can copy the source in a text file with name same as main class, compile it using javac command and run it by using java command directly from command prompt. This contains code to sort a primitive array on increasing order, sorting integer and string array in ascending and descending order, sorting object arrays and sorting 2D array columns. If you have any questions or face any problem while running this sample program, please let us know.
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * Couple of examples of Multi-dimensional array in Java. It shows how to
 * declare multidimensional array in Java, how to initialise them both inline
 * and using for loop and how to access particular elements from two dimensional
 * array.
 *
 * @author Javin Paul
 */

public class ArraySorter {

    public static void main(String args[]) {

        // How to sort Integer array in Java - ascending order
        int[] random = { 33, 22, 11, 21, 55, 32, 3, 4 };
        System.out.println("Array before sorting : " + Arrays.toString(random));
        Arrays.sort(random); // sorts primitive array using quicksort algorithm
        System.out.println("Array after sorting in ascending order : "
                + Arrays.toString(random));

       
        // How to sort String array in Java
        String[] names = {"John", "Steve", "Shane", "Adam", "Ben"};
        System.out.println("String array before sorting : " + Arrays.toString(names));
       
        Arrays.sort(names); // sorts object array using mergesort algorithm
        System.out.println("String array after sorting in ascending order : "
                + Arrays.toString(names));
       
       
        // How to sort String array in descending order in Java
        Arrays.sort(names, 0, names.length, Collections.reverseOrder());
        System.out.println("String array after sorting in descending order : "
                + Arrays.toString(names));
       
       
        // How to Sort Object Array in Java using Comparator and Comparable
        Course[] courses = new Course[4];
        courses[0] = new Course(101, "Java", 200);
        courses[1] = new Course(201, "Ruby", 300);
        courses[2] = new Course(301, "Python", 400);
        courses[3] = new Course(401, "Scala", 500);
       
        System.out.println("Object array before sorting : " + Arrays.toString(courses));
        Arrays.sort(courses);
        System.out.println("Object array after sorting in natural order : " + Arrays.toString(courses));
       
        Arrays.sort(courses, new Course.PriceComparator());
        System.out.println("Object array after sorting by price : " + Arrays.toString(courses));
       
        Arrays.sort(courses, new Course.NameComparator());
        System.out.println("Object array after sorting by name : " + Arrays.toString(courses));

        // How to sort two dimensional array in Java on first column, increasing order
        Integer[][] numbers = { {9, 6, 5}, {3, 2, 4}, {1, 5, 7} };
        System.out.println("Two dimensional array before sorting : " + Arrays.deepToString(numbers));
        Arrays.sort(numbers, new ColumnComparator(0, SortingOrder.ASCENDING));
        System.out.println("2D array after sorting in ascending order on first column : " + Arrays.deepToString(numbers));
       
        // sorting 2D array on second column in descending order
        Arrays.sort(numbers, new ColumnComparator(1,SortingOrder.DESCENDING));
        System.out.println("Sorting two dimensional String array in Java, Second column, Ascending order : " + Arrays.deepToString(numbers));

    }

}

/*
 * Simple Enum to represent sorting order e.g. ascending and descending order
 */
enum SortingOrder{
    ASCENDING, DESCENDING;
};

/*
 * Utility Comparator class to sort two dimensional array in Java
 */
class ColumnComparator implements Comparator<Comparable[]> {
    private final int iColumn;
    private final SortingOrder order;

    public ColumnComparator(int column, SortingOrder order) {
        this.iColumn = column;
        this.order = order;
    }

    @Override
    public int compare(Comparable[] c1, Comparable[] c2) {
        int result = c1[iColumn].compareTo(c2[iColumn]);
        return order==SortingOrder.ASCENDING ? result : -result;
    }
}

class Course implements Comparable<Course>{
    int id;
    String name;
    int price;
   
    public Course(int id, String name, int price){
        this.id = id;
        this.name = name;
        this.price = price;
    }

    @Override
    public int compareTo(Course c) {
        return this.id - c.id;
    }
   
    @Override
    public String toString() {
        return String.format("#%d %s@%d ", id, name, price);
    }

    public static class PriceComparator implements Comparator<Course>{
        @Override
        public int compare(Course c1, Course c2) {
            return c1.price - c2.price;
        }       
    }
   
    public static class NameComparator implements Comparator<Course>{
        @Override
        public int compare(Course c1, Course c2) {
            return c1.name.compareTo(c2.name);
        }
    }
   
}
That's all about how to sort an array in Java. We have learned sorting both primitive and object array in both ascending and descending order. Only piece which is bit tricky is sorting primitive arrays in reverse order because their is no direct method to do that in Java. You need to go through steps like first sorting them in increasing order and then reversing or writing your method to do the job or converting array to list and vice-versa. In any case, use library method to do sorting for performance and robustness, as you know how using a two pivot quicksort method on Arrays sort() method gives better performance for arrays for which other similar sorting algorithm result in O(n^2). Autoboxing can not help to convert an int[] to Integer[] so there is no short-cut also. Prefer List over array due to this reason but for performance critical code use primitive array to save memory and reduce GC cost.

4 comments:

  1. how you write code in colorfull texyt please tell

    ReplyDelete
  2. What is the complexity of sorting using Arrays utility?

    ReplyDelete
    Replies
    1. It's two pivot quicksort algorithm for primitives and a stable mergesort for refernece types. which means on average you get performance of O(nlogn) while sorting array using Arrays.sort() method.

      Delete
  3. vishal shingote ..use the Eclipse tool i hope it will help you.

    ReplyDelete

Java67 Headline Animator