Sorting is an operation of utmost significance in computer science which plays an important role in a plethora of applications. Within the Java programming language, the task of sorting numbers can be achieved through many techniques. Whether you are a beginner or an experienced Java developer, you must acquire the knowledge of sorting numbers.
In this blog we will explore some of the most prominent methods for sorting numbers within Java. We will see approaches and sample problems to practice them all. Now, we should begin our journey of gaining knowledge on how to sort numbers in Java.
Why is sorting numbers in java is needed?
There are some reasons why is sorting numbers in Java is needed:
- Efficient Searching: When it comes to optimizing searching algorithms, sorting numbers is a crucial step. By sorting the numbers, it becomes easier to locate a specific value within a massive dataset, resulting in faster search times.
- Improved Performance: Sorting numbers can improve algorithm performance. This is especially true when working with large data.
- Better User Experience: Sorting numbers is highly beneficial in user interface design. By sorting the data, it becomes more readable and easier to comprehend.
- Data Storage: Sorting numbers can also assist in optimizing data storage. This is particularly true in databases, where sorting data can significantly enhance the performance of queries that rely on sorting.
How To Sort Numbers In Java
There are the six different approaches to sorting numbers in java:
- Using Merge Sort
- Using Insertion Sort
- Using a TreeSet
- Using Quick Sort
- Using Heap Sort
- Using Bubble Sort
Let’s dive in more with examples to each approach.
Approach 1: Using Merge Sort
Merge sort is a divide and conquer algorithm that recursively splits an array into halves until each sub-array contains only one element. It then merges the sub-arrays in a sorted order until the entire array is sorted.
Pros:
- Merge sort has a guaranteed worst-case time complexity of O(n log n), making it efficient for sorting large sets of data.
- Merge sort is stable, meaning that the relative order of equal elements is preserved.
- Merge sort can be parallelized to take advantage of multi-core processors, which can further improve its performance.
Cons:
- Merge sort requires additional memory to store the sub-arrays during the sorting process.
- Merge sort has a higher overhead than other sorting algorithms, which can make it less efficient for small sets of data.
- The merge operation in merge sort can be computationally expensive for very large sets of data.
Sample Code:
public class Main {
public static void main(String[] args) {
int[] numbers = { 10, 5, 8, 3, 2, 7, 1, 6, 9, 4 };
mergeSort(numbers, 0, numbers.length - 1);
for (int i = 0; i < numbers.length; i++) {
System.out.println(numbers[i]);
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[arr.length];
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= mid) {
arr[k] = temp[i];
k++;
i++;
}
}
}
Output:
1
2
3
4
5
6
7
8
9
10
Code Explanation:
- We define an array of unsorted integers.
- We call the mergeSort method, passing in the array, the starting index (0), and the ending index (the length of the array minus one).
- In the mergeSort method, we check if the starting index is less than the ending index. If it is, we divide the array into two halves and recursively call the mergeSort method for each half.
- Once the two halves are sorted, we merge them together into a single sorted array using the merge method.
- The merge method takes in the original array, the starting index of the left sub-array, the middle index of the sub-arrays, and the ending index of the right sub-array.
- We copy the elements of the original array into a temporary array so that we can modify the original array during the merge operation.
- We initialize three variables, i, j, and k, to keep track of the indices of the left, right, and merged arrays, respectively.
- We compare the elements at indices i and j of the temporary array and copy the smaller element into the original array at index k. We then increment either i or j and continue this process until one of the sub-arrays has been fully merged.
- Once we have merged one of the sub-arrays, we copy any remaining elements from the other subarray into the original array.
- The mergeSort method eventually returns to the main method, where we print out the sorted array.
Approach 2: Using Insertion Sort
Insertion sort is a simple sorting algorithm that works by inserting each element of the unsorted portion of the array into its correct position in the sorted portion of the array. It is an in-place algorithm, which means that it does not require additional memory to perform the sorting.
Pros:
- Simple and easy to implement
- Works well for small data sets or partially sorted arrays
- Good for online sorting where new data is continuously added to the array
Cons:
- Inefficient for large data sets or highly unsorted arrays
- Worst-case time complexity is O(n^2)
- Not suitable for real-time applications where sorting needs to be done quickly
Sample Code:
import java.util.Arrays;
public class Main {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements greater than key to the right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert the key into its correct position
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {4, 2, 9, 6, 23, 12, 34, 0, 1};
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}
Output:
[0, 1, 2, 4, 6, 9, 12, 23, 34]Code Explanation:
- The insertion sort algorithm works by iterating through the array from index 1 to n-1.
- For each element, it compares it with the previous elements in the sorted portion of the array.
- If the element is smaller than the previous element, the previous element is shifted to the right to make space for the current element.
- This process continues until the current element is in its correct position in the sorted portion of the array.
- The time complexity of insertion sort is O(n^2) in the worst case and O(n) in the best case when the array is already sorted.
- Insertion sort is a good choice for small data sets or partially sorted arrays, but not suitable for large data sets or highly unsorted arrays.
Approach 3: Using a TreeSet
A TreeSet is a class in Java that implements the Set interface and provides a sorted, navigable set of elements. It uses a red-black tree data structure to store the elements in a sorted order, which allows for efficient search, insertion, and deletion operations.
Pros:
- Automatically maintains a sorted order of elements.
- Provides efficient search, insertion, and deletion operations.
- Supports additional operations such as finding the first and last elements, and retrieving elements in a range.
Cons:
- Only stores unique elements, duplicates are not allowed.
- Can be less efficient than other data structures for certain use cases, such as large-scale data processing.
- Requires elements to implement the Comparable interface or a custom Comparator to determine their order.
Sample Code:
import java.util.TreeSet;
public class Main{
public static void main(String[] args) {
// create a TreeSet of integers
TreeSet<Integer> numbers = new TreeSet<>();
// add some numbers to the set
numbers.add(5);
numbers.add(2);
numbers.add(9);
numbers.add(1);
numbers.add(3);
// print the sorted set
System.out.println(numbers);
}
}
Output:
[1, 2, 3, 5, 9]Code Explanation:
- Import the TreeSet class from the java.util package.
- Create a new instance of the TreeSet class, specifying the type of elements to be stored (in this case, Integer).
- Add some numbers to the set using the add() method.
- When the set is printed using System.out.println(), the elements are automatically sorted in ascending order due to the implementation of the TreeSet class.
Approach 4: Using Quick Sort
Quick sort is a divide-and-conquer sorting algorithm that works by selecting a pivot element from the input array, partitioning the array into two halves – elements smaller than the pivot go to one half and elements larger than the pivot go to the other half, and recursively sorting the two halves.
Pros:
- Efficient on large data sets.
- In-place sorting algorithm.
- Time complexity of O(n log n).
Cons:
- Worst-case time complexity of O(n^2) can occur.
- Not a stable sorting algorithm.
- Not suitable for complex data structures.
Sample Code:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {5, 7, 2, 8, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
Output:
[1, 2, 5, 7, 8]Code Explanation:
- The quickSort() function takes an array of integers, a low index, and a high index as input.
- The function selects a pivot element from the input array and partitions the array into two subarrays – elements smaller than the pivot go to the left subarray and elements larger than the pivot go to the right subarray.
- The function then recursively sorts the left and right subarrays.
- The partition() function takes an array of integers, a low index, and a high index as input.
- The function selects the last element as the pivot and rearranges the elements such that all elements smaller than the pivot are to the left and all elements larger than the pivot are to the right.
- The function returns the index of the pivot element.
- The worst-case time complexity of quick sort is O(n^2) when the input array is already sorted or nearly sorted. However, the expected time complexity is O(n log n) on average.
- Quick sort is not a stable sorting algorithm as the relative order of equal elements may change after sorting. However, it is an in-place sorting algorithm that does not require extra memory.
- Quick sort is efficient on large data sets and is commonly used in practice. However, it is not suitable for sorting complex data structures such as linked lists.
Approach 5: Using Heap Sort
Heap sort is a comparison-based sorting algorithm that works by creating a binary heap from the input array, repeatedly extracting the maximum element from the heap, and inserting it into a sorted array.
Pros:
- Efficient on large data sets.
- In-place sorting algorithm.
- Guaranteed time complexity of O(n log n).
Cons:
- Not a stable sorting algorithm.
- Less efficient than quicksort for small data sets.
- Requires extra space for the heap data structure.
Sample Code:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 7, 1 };
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
}
Output:
[1, 2, 5, 7, 8]Code Explanation:
- The heapSort() function takes an array of integers as input.
- The function first creates a binary heap from the input array using the heapify() function.
- The function then repeatedly extracts the maximum element from the heap and inserts it into a sorted array.
- The heapify() function takes an array of integers, the size of the heap, and an index as input.
- The function first finds the largest element among the nodes at the given index and its children.
- If the largest element is not the node at the given index, the function swaps the two elements and recursively calls itself on the child node.
Approach 6: Using Bubble Sort
Bubble sort is a simple comparison-based sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order until the array is sorted.
Pros:
- Easy to implement.
- Works well on small data sets.
- In-place sorting algorithm.
Cons:
- Time complexity of O(n^2) makes it inefficient on large data sets.
- Not suitable for complex data structures.
- Not a stable sorting algorithm.
Sample Code:
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 7, 1 };
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
Output:
[1, 2, 5, 7, 8]Code Explanation:
- The bubbleSort() function takes an array of integers as input.
- The function iterates over the array n-1 times where n is the size of the array.
- For each iteration, the function compares adjacent elements and swaps them if they are in the wrong order.
- The function terminates when the array is sorted.
Best Approach for sorting numbers in Java
Merge sort is the best approach to sort numbers in java. Here are the some key features of Merge Sort:
- Efficiency: Merge sort has a worst case time complexity of O(n log n), which makes it an efficient algorithm for sorting large sets of data.
- Stability: Merge Sort is a stable sorting algorithm, which means that the relative order of equal elements is preserved in the sorted array.
- Parallelization: Merge sort can be parallelized to take advantage of multi-core processors, which can further improve its performance.
This method is an exceptionally reliable and efficient method for sorting numbers in Java.
Sample Problems To Sort Numbers In Java
Sample Problem 1:
Scenario: You are working on a project where you need to sort a list of numbers that represents the scores of students in a class. The list is unsorted and you need to sort it in ascending order so that you can identify the top performers in the class. You decide to use merge sort as it is an efficient algorithm for sorting large sets of data.
Problem: Sort the following list of numbers using insertion sort: { 70, 85, 60, 90, 75, 80, 95, 65}
Solution Steps:
- Define an array of integers to represent the scores of the students in the class.
- Call the mergeSort method passing the array, the starting index and the ending index as parameters.
- In the mergeSort method, check if the starting index is less than the ending index.
- If the starting index is less than the ending index, divide the array into two halves and recursively call the mergeSort method for each half.
- Merge the two sorted halves into a single sorted array using the merge method.
- Return the sorted array.
Code:
public class Main {
public static void main(String[] args) {
int[] scores = { 70, 85, 60, 90, 75, 80, 95, 65 };
mergeSort(scores, 0, scores.length - 1);
for (int i = 0; i < scores.length; i++) {
System.out.println(scores[i]);
}
}
public static void mergeSort(int[] scores, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(scores, start, mid);
mergeSort(scores, mid + 1, end);
merge(scores, start, mid, end);
}
}
public static void merge(int[] scores, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (scores[i] <= scores[j]) {
temp[k] = scores[i];
i++;
} else {
temp[k] = scores[j];
j++;
}
k++;
}
while (i <= mid) {
temp[k] = scores[i];
i++;
k++;
}
while (j <= end) {
temp[k] = scores[j];
j++;
k++;
}
for (k = 0; k < temp.length; k++) {
scores[start + k] = temp[k];
}
}
}
Output:
60
65
70
75
80
85
90
95
Sample Problem 2:
Scenario: Imagine you are working on an application that involves processing large amounts of data, including numeric data. You need to sort the data efficiently to optimize the performance of your application.
Problem: Sort the following list of numbers using insertion sort: {12, 56, 34, 7, 90}
Solution steps:
- Initialize an array of integers with five elements: 12, 56, 34, 7, and 90.
- Call the insertionSort function and pass the array as an argument.
- In the insertionSort function, iterate over the array starting from the second element.
- For each iteration, store the current element in a variable called key and initialize a variable called j with the index of the previous element.
- Compare the key with the elements on the left of it and move the larger elements to the right.
- Insert the key in the correct position in the array.
- Continue the iterations until the entire array is sorted in ascending order.
- Print the sorted array of integers.
Code:
public class Main{
public static void main(String[] args) {
int[] numbers = {12, 56, 34, 7, 90};
insertionSort(numbers);
for (int number : numbers) {
System.out.print(number + " ");
}
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
Output:
7 12 34 56 90Sample Problem 3:
Scenario: Imagine you are working on a Java program that involves managing customer orders. You need to sort the orders by the order number to make them easier to manage.
Problem: Sort the following list of order numbers using a TreeSet: {104, 102, 101, 105, 103}
Solution steps:
- Import the TreeSet class from the java.util package.
- Create a new TreeSet object of integers named orders.
- Add several integer elements to the orders set using the add() method.
- Iterate over the orders set using a for-each loop and print each element in ascending order.
- The TreeSet automatically sorts the elements in ascending order as they are added to the set.
- Compile and run the code to see the sorted set of integers printed to the console.
Code:
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
TreeSet<Integer> orders = new TreeSet<>();
orders.add(104);
orders.add(102);
orders.add(101);
orders.add(105);
orders.add(103);
for (int order : orders) {
System.out.print(order + " ");
}
}
}
Output:
101 102 103 104 105Sample Problem 4:
Scenario: Imagine you are working on a stock market application that involves analyzing stock prices. You need to sort the stock prices in descending order to find the most profitable investments.
Problem: Sort the following list of stock prices using quick sort: {100.50, 200.25, 50.75, 75.00, 300.10}
Solution steps:
- The main method initializes an array of double values named “prices”.
- The quickSort method is called with the “prices” array, the lowest index (0) and the highest index (prices.length – 1) as arguments.
- The quickSort method checks if the low index is less than the high index. If so, it calls the partition method to find a pivot index and sorts the elements on either side of the pivot recursively.
- The partition method initializes the pivot value as the last element of the array.
- It sets a variable “i” to the index before the first element of the array.
- It then iterates through the array using a for loop, comparing each element with the pivot value.
- If an element is greater than the pivot value, the “i” variable is incremented and the element at the “i” index is swapped with the element at the current index “j”.
- After the loop completes, the pivot value is swapped with the element at the “i+1” index.
- The partition method returns the “i+1” index as the pivot index.
- The quickSort method continues to sort the sub-arrays on either side of the pivot index until the entire array is sorted.
- Finally, the main method prints the sorted array of double values.
Code:
public class Main {
public static void main(String[] args) {
double[] prices = {100.50, 200.25, 50.75, 75.00, 300.10};
quickSort(prices, 0, prices.length - 1);
for (double price : prices) {
System.out.print(price + " ");
}
}
public static void quickSort(double[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(double[] arr, int low, int high) {
double pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] > pivot) {
i++;
double temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
double temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
Output:
300.1 200.25 100.5 75.0 50.75 Sample Problem 5:
Scenario: Imagine you are working on a mobile application that involves sorting large amounts of data. You need to sort the data efficiently to ensure that the application runs smoothly on mobile devices.
Problem: Sort the following list of numbers using heap sort: {10, 30, 50, 40, 20}
Solution steps:
- The main method initializes an array of integer values named “numbers”.
- The heapSort method is called with the “numbers” array as an argument.
- The heapSort method first initializes a variable “n” to the length of the array.
- It then iterates through the first half of the array, calling the heapify method for each index to build a max heap.
- The heapify method takes an array, the size of the heap, and an index as arguments.
- It first initializes the “largest” variable to the current index “i”.
- It then calculates the left and right child indices of the current index.
- If either the left or right child index is within the heap size and the value at that index is greater than the value at the current index, it updates the “largest” variable to that index.
- If the “largest” variable is not equal to the current index “i”, it swaps the values at the two indices and recursively calls the heapify method on the “largest” index to maintain the heap property.
- After building the max heap, the heapSort method iterates through the array in reverse order, swapping the largest element at index 0 with the current element at index “i” and calling heapify on the reduced heap size to maintain the heap property.
- Finally, the main method prints the sorted array of integer values.
Code:
public class Main{
public static void main(String[] args) {
int[] numbers = {10, 30, 50, 40, 20};
heapSort(numbers);
for (int number : numbers) {
System.out.print(number + " ");
}
}
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
}
Output:
10 20 30 40 50Sample Problem 6:
Scenario: Imagine you are working on a survey application that involves sorting survey results by the number of votes received. You need to sort the survey results in ascending order to determine the most popular choices.
Problem: Sort the following list of survey results using bubble sort: {5, 2, 8, 1, 3}
Solution steps:
- The main method initializes an array of integers named “results”.
- The bubbleSort method is called with the “results” array as an argument.
- The bubbleSort method initializes a variable “n” to the length of the array.
- It then iterates through the array using two nested for loops.
- The outer for loop iterates from the first element to the second last element of the array.
- The inner for loop iterates from the first element to the element before the current iteration of the outer for loop.
- It compares the current element with the next element and swaps them if the current element is greater than the next element.
- After the loop completes, the largest element is moved to the end of the array.
- The outer loop repeats until the entire array is sorted in ascending order.
- Finally, the main method prints the sorted array of integers.
Code:
public class Main{
public static void main(String[] args) {
int[] results = {5, 2, 8, 1, 3};
bubbleSort(results);
for (int result : results) {
System.out.print(result + " ");
}
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
Output:
1 2 3 5 8Conclusion
In conclusion, as we discussed six different approaches, among all Merge Sort is the best approach for sorting the number in java.This approach is the most efficient for sorting large numbers of data. It is also stable and efficient.
We also looked at the other approaches like Insertion sort, TreeSet, Quick sort, Heap sort and Bubble sort. Those are also good but the use of them depends as per the need.
24×7 Live Java Homework Help From Expert Tutors!
