Sorting arrays in Java

Sorting is a fundamental operation in computer science and programming. In Java, there are multiple ways to sort arrays, catering to various requirements and performance considerations. In this article, we will delve into the techniques and methods for sorting arrays in Java, covering both built-in and custom sorting approaches.
 

1. Sorting Arrays Using Arrays.sort()

Java provides a convenient built-in method for sorting arrays of various data types, including arrays of objects. This method is part of the java.util package and is called Arrays.sort().

Sorting Arrays of Primitive Data Types

To sort an array of primitive data types like int, double, or char, you can use the Arrays.sort() method directly:

int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
Arrays.sort(numbers);

The Arrays.sort method in Java uses a variation of the merge sort algorithm called TimSort. TimSort is an adaptive sorting algorithm derived from merge sort and insertion sort, and it's specifically designed to perform well on many kinds of real-world data. Here are the time and space complexities for Arrays.sort:

Time Complexity:

• Best Case: O(n log n) - This occurs when the array is already partially ordered, which is quite common in real-world scenarios.
• Average Case: O(n log n) - TimSort typically performs very well on average for various input data.
• Worst Case: O(n log n) - This is the worst-case time complexity when sorting an array.

Space Complexity:

TimSort uses additional memory for temporary storage during the sorting process, making its space complexity O(n). This additional memory usage is primarily for maintaining temporary runs and merge operations.

Sorting Arrays of Objects

To sort an array of objects, ensure that the objects in the array implement the Comparable interface and override the compareTo() method. Here's an example sorting an array of String objects:

String[] names = {"Alice", "Bob", "Charlie", "David"};
Arrays.sort(names);

Output:
The Arrays.sort(names) statement will sort the names array in lexicographic (alphabetical) order, which means it will arrange the names in ascending order based on their lexicographic order (character by character).

So, the output of the sorted names array will be:

2. Custom Sorting with Comparator

What if you want to sort an array of custom objects based on specific criteria that aren't supported by the default compareTo() method? You can achieve this by using a Comparator. A Comparator is an interface that allows you to define custom comparison logic.

Implementing a Custom Comparator

Here's a complete Java program that demonstrates custom sorting using a Comparator for a list of custom objects. In this example, we'll create a list of Employee objects and sort them based on their salary using a custom comparator:
 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Employee {
   private String name;
   private double salary;

   public Employee(String name, double salary) {
       this.name = name;
       this.salary = salary;
   }

   public String getName() {
       return name;
   }

   public double getSalary() {
       return salary;
   }

   @Override
   public String toString() {
       return "Employee [name=" + name + ", salary=" + salary + "]";
   }
}

class SalaryComparator implements Comparator<Employee> {
   @Override
   public int compare(Employee employee1, Employee employee2) {
       // Compare employees based on salary
       return Double.compare(employee1.getSalary(), employee2.getSalary());
   }
}

public class CustomSortingExample {
   public static void main(String[] args) {
       // Create a list of Employee objects
       List<Employee> employees = new ArrayList<>();
       employees.add(new Employee("Alice", 50000));
       employees.add(new Employee("Bob", 60000));
       employees.add(new Employee("Charlie", 55000));

       // Sort the list using the custom SalaryComparator
       Collections.sort(employees, new SalaryComparator());

       // Print the sorted list
       System.out.println("Sorted by salary:");
       for (Employee employee : employees) {
           System.out.println(employee);
       }
   }
}

Output : 
 

1. We define an Employee class with attributes name and salary.
2. We create a custom SalaryComparator class that implements the Comparator interface to compare Employee objects based on their salaries.
3. In the main method, we create a list of Employee objects and add three employees to the list, each with a name and a salary.
4. We sort the list of Employee objects using the custom SalaryComparator, which compares employees based on their salary in ascending order. To sort in descending order, you can modify the comparator by reversing the comparison logic.
5. Finally, we print the sorted list of employees by salary, demonstrating the use of a custom comparator for custom sorting.

2. Sorting in Reverse Order

Sometimes, you may need to sort an array in reverse order. You can achieve this by using the Collections.reverseOrder() method for sorting objects or by manually reversing the array after sorting for primitive data types.

Sorting in Reverse Order for Objects

Arrays.sort(people, Collections.reverseOrder(new AgeComparator()));

Sorting in Reverse Order for Primitive Data Types

import java.util.Arrays;
import java.util.Collections;

public class ReverseSortExample {
   public static void main(String[] args) {
       // Create an array of integers
       Integer[] numbers = {5, 2, 9, 1, 5, 6};

       // Convert the array to a List for reverse sorting
       Arrays.sort(numbers, Collections.reverseOrder());

       // Print the sorted array in reverse order
       System.out.println("Array sorted in reverse order: " + Arrays.toString(numbers));
   }
}

Output:
 

3. Performance Considerations

The performance of sorting algorithms can vary significantly depending on the size and nature of the data. Java's Arrays.sort() method uses a dual-pivot quicksort algorithm for primitive data types, making it highly efficient for most scenarios.

For sorting objects, Arrays.sort() employs TimSort, which is a modified merge sort. TimSort adapts to the data's characteristics, making it efficient and versatile.

Both TimSort and traditional merge sort have a worst-case time complexity of O(n log n), where "n" is the number of elements to be sorted. This makes them equally efficient in the worst case.
 

Conclusion

Sorting arrays is a common and essential task in Java programming. Whether you need to sort arrays of primitive data types or custom objects, Java offers a rich set of tools and techniques to accomplish the task. By understanding the built-in sorting methods, implementing custom comparators, and considering performance factors, you can effectively sort arrays in Java for a wide range of applications. The Arrays.sort() method, in particular, is a powerful and efficient tool for sorting arrays in Java.