Sorting data is an integral part of programming. When working with arrays in Java, it is often necessary to sort the elements in a particular order – either ascending or descending. Java provides multiple ways to sort arrays, making it easy for developers to organize data as needed.
In this comprehensive guide, we will explore various methods to sort arrays in Java:
- Using Arrays.sort()
- Using Collections.sort()
- Sorting Primitive Arrays
- Using Comparable and Comparator
- Sorting Multi-Dimensional Arrays
- Custom Sorting Logic
Why Do We Need to Sort Arrays in Java?
Here are some common reasons why sorting arrays is important:
- Organized Data – Sorting arranges data in a logical order, making it easier to search, access and work with.
- Pre-processing – Many algorithms require input data to be sorted first before processing. Eg. binary search.
- Improve Efficiency – Sorting allows optimizing data retrieval and access for efficiency.
- Data Analysis – Sorting helps easily analyze data characteristics like finding max, min values etc.
Overall, sorting transforms disorganized data into structured data for simplified access and analysis.
Sorting Basics in Java
Before looking at specific examples, let‘s understand the fundamentals of sorting in Java:
-
Sorting rearranges data into ascending or descending order based on a certain criteria.
-
The main criteria for sorting primitives is by numerical or lexicographical order. For objects, its by the natural order defined in the class.
-
Java provides in-built methods for sorting as well as allows custom implementations.
-
The time complexity of sorting algorithms indicates their efficiency – like quicksort, merge sort etc.
-
Sorting is an in-place operation in arrays, modifying the actual content.
Now that we know some basic concepts, let‘s start exploring various sorting techniques.
1. Sort Array using Arrays.sort()
Arrays class in Java contains various utility static methods. One of them is the sort() method that allows sorting arrays easily.
Here is the basic syntax:
import java.util.Arrays;
// Sort array
Arrays.sort(array)This method takes the array as argument and sorts the elements in ascending order.
Let‘s see an example:
int[] numbers = {4, 2, 9, 13, 15, 43};
// Before Sorting
System.out.println(Arrays.toString(numbers));
// Sort array
Arrays.sort(numbers);
// After Sorting
System.out.println(Arrays.toString(numbers));
// Output
// [4, 2, 9, 13, 15, 43]
// [2, 4, 9, 13, 15, 43]We simply passed the array to Arrays.sort() which sorted the elements. It used quicksort internally.
Some key points about Arrays.sort():
- Works for all primitive data types like int, float etc. as well as objects.
- For objects, the elements must implement Comparable interface.
- Sorts in ascending order by default.
- Uses dual-pivot Quicksort algorithm internally for best performance.
Time Complexity – O(n*log(n))
Let‘s look at a few more examples of array sorting using Arrays.sort().
1.1 Sort String Array
We can easily sort an array of Strings.
String[] colors = {"Blue", "Red", "green", "Yellow"};
// Sort Colors
Arrays.sort(colors);
// Print Sorted Array
System.out.println(Arrays.toString(colors));
// Output
// [Blue, Red, Yellow, green] Strings implement Comparable by default, so they can be directly sorted.
1.2 Sort Primitive int Array
Sorting primitive integer arrays is similar:
int[] numbers = {5, 2 ,12, 7, 19};
// Sort Array
Arrays.sort(numbers);
// Print sorted array
System.out.println(Arrays.toString(numbers));
// Output
// [2, 5, 7, 12, 19]The method works seamlessly for all primitive data types.
1.3 Sort User-Defined Objects
To sort custom objects by Arrays.sort(), the class must implement Comparable interface which provides the compareTo() method.
For example:
class Person implements Comparable<Person> {
private String name;
private int age;
// Implement CompareTo
public int compareTo(Person other){
return this.age - other.age;
}
}
// Array of custom objects
Person[] people = {new Person(...), new Person(...)..}
// Sort Array
Arrays.sort(people);Here the custom Person class implements Comparable interface. The compareTo method provides logic for sorting by age.
This allows the array of Person objects to be sorted by age.
So in this way, we can sort arrays containing user-defined classes as well.
2. Sort Array using Collections.sort()
Java Collections Framework provides Collections class that contains useful utility methods for collections.
One of them is sort() which we can use for sorting Lists and Arrays.
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
// Sort List
List<Integer> list = new ArrayList<>();
Collections.sort(list);
// Sort array
Integer[] arr = { .. };
Collections.sort(arr);Basic syntax is similar, pass collection/array as argument to sort.
Let‘s see an example of sorting an array using Collections.sort():
import java.util.Collections;
// Array of Integers
Integer arr[] = {3, 1, 5, 4, 2};
// Print array before sorting
System.out.println("Array Before Sorting: " +Arrays.toString(arr));
// Sort using Collections.sort()
Collections.sort(arr);
// Print after sorting
System.out.println("Array After Sorting: " +Arrays.toString(arr));
// Output
// Array Before Sorting: [3, 1, 5, 4, 2]
// Array After Sorting: [1, 2, 3, 4, 5] As we can see, the Collections.sort() method sorted the Integer array.
Some key things:
- Works for all objects like String, Integer etc.
- Objects must implement Comparable interface.
- Cannot directly sort primitive arrays.
The default sorting algorithm internally is timsort for Collections.sort().
3. Sort Primitive Arrays
Earlier we saw Arrays.sort() can be used to sort primitive data type arrays. However, Collections.sort() does not support primitive types directly.
But there is a simple workaround.
Java provides wrapper classes for each primitive type like Integer for int. We can convert primitive array to object array for sorting:
int[] primArr = {...};
// Convert to Integer object array
Integer[] objectArr = ArrayUtils.toObject(primArr);
// Sort using Collections.sort()
Collections.sort(objectArr);
// Convert back to int array (Optional)
primArr = ArrayUtils.toPrimitive(objectArr);Here ArrayUtils is a utility class that converts between the two arrays.
Let‘s take an example:
int[] numbers = {5, 1 ,7 ,3};
// Convert to Integer array
Integer[] wrapped = ArrayUtils.toObject(numbers);
// Sort Integer array
Collections.sort(wrapped);
// Convert back to int (optional)
numbers = ArrayUtils.toPrimitive(wrapped);
System.out.println(Arrays.toString(numbers));
// Output
// [1, 3, 5, 7]So in this way, primitive arrays can also be sorted using Collections.sort().
4. Sort Array using Comparable and Comparator
The java.lang.Comparable and java.util.Comparator interfaces provide alternate ways to control sorting logic.
4.1 Comparable Interface
The Comparable interface contains compareTo() method which defines the natural ordering for a class.
We can implement Comparable in our classes to define custom sorting logic.
For example, here is how we can sort employees by salary:
class Employee implements Comparable<Employee> {
private int salary;
public int compareTo(Employee other){
return this.salary - other.salary ;
}
}
// Array Sorting
Employee[] staff = new Employee[5];
Arrays.sort(staff); The compareTo method compares employees by salary and sorts array accordingly.
So Comparable allows flexible sorting of custom classes. The sorting methods use this ordering logic.
4.2 Comparator Interface
The Comparator interface provides compare() method to define different orderings externally without modifying the class.
We can pass a custom Comparator to alter the sorting logic:
class Employee {
private int salary;
}
// Salary comparator
Comparator<Employee> salaryComp = new Comparator<Employee>(){
public int compare(Employee a, Employee b){
return a.salary - b.salary;
}
};
// Array Sort
Employee[] staff = new Employee[5];
// Sort by Salary (asc)
Arrays.sort(staff, salaryComp);The custom Comparator compares Employee objects by salary. This gets used for sorting instead of the natural order.
Similarly, we can pass different comparators for sorting by age, name etc. without changing Employee class.
This allows flexible sorting without modifying the objects themselves to make them Comparable.
5. Sort Multi-Dimensional Arrays in Java
Up till now, we have seen sorting single dimensional arrays. In real apps, often multi-dimensional arrays are used like 2D or 3D arrays.
Sorting them is a bit different since we need to define which dimension to sort on.
For example:
// 2D Integer Array
int arr[][] = { {3, 6}, {1, 12}, {5, 9} };
// Sort by 1st Column (Index 0)
Arrays.sort(arr, new ColumnSortComparator(0));
// Sort by 2nd Column (Index 1)
Arrays.sort(arr, new ColumnSortComparator(1));Here, ColumnSortComparator is a custom comparator that can sort any column index as passed.
So the steps are:
- Define Multi-dimensional Array
- Create custom Comparator by column index
- Pass Comparator to Arrays.sort()
Similarly, we can sort 3D or higher dimension arrays on any dimension we need.
6. Custom Sorting Logic
Besides using predefined sorting methods, we can implement custom algorithms to sort arrays as per needs.
Some popular sorting techniques are:
Bubble Sort – Simple algorithm that compares adjacent elements and swaps them.
void bubbleSort(int arr[]) {
for(int i = 0; i < arr.length; i++){
// Compare adjacent elements
// Swap if >
}
}Insertion Sort – Builds final sorted array one element at a time.
Merge Sort – Divides array halves, sorts them and merges sorted halves.
Quick Sort – Picks a pivot, partitions elements smaller/greater than pivot and recurs on partitions.
The exact implementations have additional logic for edge cases.
Depending on the use case, custom algorithms may have performance advantages over built-in methods. But they require more coding effort.
Conclusion
Java provides a lot of flexibility for sorting arrays to meet different requirements.
The Arrays.sort() and Collections.sort() methods allow easy sorting with default ordering. For advanced sorting, Comparator and Comparable interfaces help customize the logic.
Sorting multi-dimensional arrays require an additional comparator to define the exact dimension and order.
Finally, for complete control we can even implement custom algorithms like various flavors of quicksort.
So in summary, Java offers simple to advanced APIs for sorting arrays and collections which cater to almost all sorting needs.
