In order to sort a static array we can use Arrays.sort() function which sorts the elements of a given array in ascending order (default), descending order or user-defined order.
Similarly, if we want to sort an ArrayList, we can use Collections.sort() which works the same way.
Important: Sorting in reverse or with a specified order using a comparator is possible only if we use objects and not primitives. This means that it will work for Integer[] array, but not on int[], at least not as easy as we think.
Syntax:
Let's see some examples below. Sorting an array of integers in ascending order
int[] numbers = {11, 3, 7, 5, 2};
Arrays.sort(numbers); // numbers becomes [2, 3, 5, 7, 11]
Sorting an ArrayList of Integers in ascending order
List<Integer> arr = new ArrayList<>(List.of(11, 3, 7, 5, 2));
Collections.sort(arr, Collections.reverseOrder()); // numbers becomes [2, 3, 5, 7, 11]
Sorting an array of integers in descending order
int[] numbers = {11, 3, 7, 5, 2};
Arrays.sort(numbers, Collections.reverseOrder()); // compile error!Notice that we have an int[] array, so we won't be able to sort it in reverse directly! We need to transform it into Integer[] array as below:
int[] numbers = {11, 3, 7, 5, 2};
// transform it to Integer[]
Integer[] arr = Arrays.stream(numbers).boxed().toArray(Integer[]::new);
// Now we can sort it
Arrays.sort(arr, Collections.reverseOrder()); //arr becomes [11, 7, 5, 3, 2]
Sorting an array of Strings in descending order
String[] names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};
Arrays.sort(names, Collections.reverseOrder()); // --> ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']
Sort with custom function (comparator):
Arrays.sort() function supports a basic comparison function that we can use to specify how we want to sort:
int compare(Integer a, Integer b) {
return a - b;
}
This can be written as a lambda function (nameless function we can easily pass to sort()) as follows:
(a, b) -> {
return a - b;
}
If the function just returns one thing, we can write it as follows:
(a, b) -> a - b
When the sort() function compares two values, it sends the values to the compare function, and sorts the values according to the returned (negative, zero, positive) value:
a is sorted before b.b is sorted before a.All we need to is using the compare function (as a lambda function) inside the sort() method:
Integer[] numbers = {3, 23, 12};
// using the short version of the lambda function
Arrays.sort(numbers, (a, b) -> a - b); // --> 3, 12, 23
To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. We will be using the length property of each string to compare them.
String words = {"banana", "pie", "Washington", "book"};
Arrays.sort(words, (a, b) -> a.length - b.length); // --> ['pie', 'book', 'banana', 'Washington']
Example: sorting array of pairs
Let's say we want to sort an array, where each element is another array consisting of two numbers.
This time we will be using int[][] since an array int[] is treated as an object so it can be sorted with a compare function
int[][] pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};
Arrays.sort(pairs, (a, b) -> {
// in case the first values of each pair are equal,
// compare them using their second values
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]
Time Complexity:
Sorting an array via Arrays.sort() takes O(n * log n * C) time, where C is the time taken to compare two elements from the array.
It takes O(1) (constant time) to compare two numbers, therefore sorting an array of numbers takes O(n log n).
However, it takes O(L) to compare two strings, therefore sorting an array of strings takes O(n * log n * L), where L is the average length of the strings.
Space Complexity:
The sort() method sorts the elements of an array in place (transforms the array directly, using no auxiliary data structure), so the extra space used for this is O(1).
Assignment
Follow the Coding Tutorial and let's sort some arrays.
Hint
Look at the examples above if you get stuck.
Sorting is a fundamental concept in computer science and programming. It involves arranging data in a particular order, typically ascending or descending. Sorting is significant because it optimizes the efficiency of other algorithms that require sorted data, such as search algorithms. Common scenarios where sorting is useful include organizing a list of names alphabetically, arranging numbers in numerical order, and sorting data based on specific attributes.
Before diving into complex sorting algorithms, it's essential to understand the basic concepts. Sorting can be done on arrays and lists, and Java provides built-in methods like Arrays.sort() and Collections.sort() to facilitate this. These methods use efficient algorithms like Timsort under the hood, which is a hybrid sorting algorithm derived from merge sort and insertion sort.
For example, sorting an array of integers in ascending order can be done using:
int[] numbers = {11, 3, 7, 5, 2};
Arrays.sort(numbers); // numbers becomes [2, 3, 5, 7, 11]
Key concepts in sorting include understanding the difference between primitive and object types, using comparators for custom sorting, and handling different data structures. Java's Arrays.sort() and Collections.sort() methods can sort data in ascending order by default. For descending order or custom sorting, a comparator is required.
For instance, sorting an array of integers in descending order requires converting the array to an Integer[] type and then using a comparator:
int[] numbers = {11, 3, 7, 5, 2};
Integer[] arr = Arrays.stream(numbers).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Collections.reverseOrder()); // arr becomes [11, 7, 5, 3, 2]
Let's explore some examples to understand sorting in various contexts:
1. Sorting an array of strings in descending order:
String[] names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};
Arrays.sort(names, Collections.reverseOrder()); // --> ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']
2. Sorting an array of pairs based on the first element, and if they are equal, then by the second element:
int[][] pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};
Arrays.sort(pairs, (a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
// pairs --> [[1, 3], [1, 5], [10, 1], [12, 5]]
Common mistakes in sorting include not converting primitive arrays to object arrays when using comparators and misunderstanding the default sorting order. Best practices include writing clear and efficient comparator functions, using lambda expressions for simplicity, and ensuring the data structure is appropriate for the sorting method used.
For example, always ensure to convert int[] to Integer[] when using custom comparators:
int[] numbers = {11, 3, 7, 5, 2};
Integer[] arr = Arrays.stream(numbers).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Collections.reverseOrder()); // arr becomes [11, 7, 5, 3, 2]
Advanced sorting techniques involve using custom comparators for complex sorting logic. For instance, sorting strings by their length:
String[] words = {"banana", "pie", "Washington", "book"};
Arrays.sort(words, (a, b) -> a.length() - b.length()); // --> ['pie', 'book', 'banana', 'Washington']
These techniques are useful when the default sorting behavior does not meet the requirements.
Here is a comprehensive example demonstrating various sorting techniques:
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class SortingExamples {
public static void main(String[] args) {
// Sorting an array of integers in ascending order
int[] numbers = {11, 3, 7, 5, 2};
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers)); // [2, 3, 5, 7, 11]
// Sorting an ArrayList of Integers in ascending order
List<Integer> arr = new ArrayList<>(List.of(11, 3, 7, 5, 2));
Collections.sort(arr);
System.out.println(arr); // [2, 3, 5, 7, 11]
// Sorting an array of integers in descending order
Integer[] arrDesc = Arrays.stream(numbers).boxed().toArray(Integer[]::new);
Arrays.sort(arrDesc, Collections.reverseOrder());
System.out.println(Arrays.toString(arrDesc)); // [11, 7, 5, 3, 2]
// Sorting an array of strings in descending order
String[] names = {"Mircea", "Andy", "Xavier", "Michael", "Christina"};
Arrays.sort(names, Collections.reverseOrder());
System.out.println(Arrays.toString(names)); // ['Xavier', 'Mircea', 'Michael', 'Christina', 'Andy']
// Sorting an array of pairs
int[][] pairs = {{1, 5}, {12, 5}, {10, 1}, {1, 3}};
Arrays.sort(pairs, (a, b) -> {
if (a[0] == b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
for (int[] pair : pairs) {
System.out.println(Arrays.toString(pair)); // [[1, 3], [1, 5], [10, 1], [12, 5]]
}
}
}
Debugging sorting algorithms involves checking the intermediate states of the array or list being sorted. Use print statements or a debugger to inspect the values. Writing tests for sorting functions can be done using JUnit or other testing frameworks. Ensure to test edge cases like empty arrays, arrays with one element, and arrays with duplicate values.
Example test case:
import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;
public class SortingTest {
@Test
public void testSortIntegers() {
int[] numbers = {11, 3, 7, 5, 2};
Arrays.sort(numbers);
assertArrayEquals(new int[]{2, 3, 5, 7, 11}, numbers);
}
}
When approaching sorting problems, start by understanding the requirements: should the data be sorted in ascending or descending order? Is a custom order needed? Break down the problem into smaller parts, such as converting data types if necessary. Practice with different types of data and sorting requirements to improve your skills.
Sorting is a crucial skill in programming that enhances the efficiency of other algorithms. Mastering sorting techniques in Java, including using built-in methods and custom comparators, is essential for writing efficient and effective code. Practice regularly and explore advanced sorting scenarios to deepen your understanding.
For further reading and practice, consider the following resources: