Sorting an integer array is organizing the array’s members in a certain order, generally ascending or decreasing. In Java, you can sort integer arrays using the sort() method. The sort() method takes the integer array to be sorted as an argument and returns the sorted array.
To accomplish this, several sorting algorithms such as bubble sort, selection sort, insertion sort, merge sort, quick sort, and heap sort can be utilized. In terms of time and space complexity, stability, and ease of implementation, each method has advantages and downsides.
The method to choose is determined by the precise needs of the situation at hand and the characteristics of the data to be sorted. Sorting is a fundamental process in computer science that is frequently utilized in a variety of applications including searching, data analysis, and database administration.
Why sorting of integer array is required
Array sorting in java has multiple applications in the real world. Java provides a range of options for sorting data and any programmer can benefit from its object oriented programming structure. Sorting an integer array is an essential for any program because:
- Data Analysis: Having a huge set of data arrays, and then sorting them may help you perform technical analysis in a better manner.
- Search: When you want to search for an element in a very large data set, sorting is an easier and more efficient way to perform the search function.
- Ranking: If the user wants to categorize the data into ranks for a better understanding of the data, they can use the sort function available in java.
- Visualization: If the user wants to provide graphical or any other visualization type of output, then the data can be sorted.
So it is necessary to understand how to sort integer array in java.
How to sort an integer array in java
There are several approaches to sorting an integer array in Java:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
Approach 1: Bubble Sort for sorting an integer array
This is an in-place comparison sorting technique that works by exchanging nearby components if they are in the wrong order frequently. Here is an example of using the bubble sort method from the main class to sort an integer array in ascending order:
import java.util.Scanner; // Importing the scanner function for scanning input
class BubbleSort{
public static void main(String[] args){
// Initialising the scanner function for scanning input
Scanner scn = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
// Asking the user to provide the size of the array
int size = scn.nextInt();
int[] arr = new int[size];
System.out.printf("Enter the elements in the array: ");
// Creating an array
for(int i = 0; i < size;i++){
arr[i] = scn.nextInt();
}
// Displaying an array
System.out.printf("Initial Array: ");
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
//sorting array elements using bubble sort
for(int i = 0; i < size;i++){
for(int j = i + 1; j < size;j++){
//swaping elements
if(arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(" ");
System.out.println("\t ***** ");
System.out.printf("After Bubble sort: ");
// Displaying the sorted array
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
}
}Output:
Enter the size of the array: 5
Enter the elements in the array: 18 13 24 98 1
Initial Array: 18 13 24 98 1
*****
After Bubble sort: 1 13 18 24 98Code Explanation for sorting in bubble sort:
- Begin by populating the array to be sorted.
- To signify that a swap has occurred, set a flag variable to true.
- Iterate over the array from the first to the second-to-last entry while the flag is set to true.
- Each pair of neighboring elements in the array is compared. Swap the elements if the element on the left is smaller than the element on the right.
- Set the flag to false after each iteration.
- Set the flag back to true if a swap occurred during the current iteration.
Approach 2: Insertion Sort for sorting an integer array
This is another in-place comparison sorting method that sorts an array by continually identifying the smallest element in the unsorted section of the array and inserting it at the beginning of the array. Here is an example of using the Insertion sort() method from the main class to sort the integers in ascending order:
import java.util.Scanner; // Importing the scanner function for scanning input
class InsertionSort{
public static void main(String[] args){
// Initialising the scanner function for scanning input
Scanner scn = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
// Asking the user to provide the size of the array
int size = scn.nextInt();
int[] arr = new int[size];
System.out.printf("Enter the elements in the array: ");
// Creating an array
for(int i = 0; i < size;i++){
arr[i] = scn.nextInt();
}
// Displaying an array
System.out.printf("Initial Array: ");
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
//sorting array elements using insertion sort
for(int i = 0; i < size;i++){
int key = arr[i];
int j = i - 1;
// Moving the greater integer in the array
//ahead of its position
while(j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
System.out.println(" ");
System.out.println("\t ***** ");
System.out.printf("After Insertion sort: ");
// Displaying the sorted array
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
}
}Output:
Enter the size of the array: 5
Enter the elements in the array: 19 22 54 43 95
Initial Array: 19 22 54 43 95
*****
After Insertion sort: 19 22 43 54 95Code Explanation for sorting in insertion sort:
- Begin by populating the array to be sorted.
- Iterate over the array starting with the second element (index 1) and ending with the last element.
- Compare each element to the components that came before it (starting from the element at index i-1 and moving backwards).
- Swap the two items if the current element is less than the preceding element.
- Continue to compare the current element to the previous elements until the right place for the current element is found.
- Steps 2-4 must be repeated for each element in the array, from the second to the last.
- The array is now ordered ascendingly.
Approach 3: Selection Sort for sorting an integer array
This is also a straightforward in-place sorting method that works by iterating through an array and placing each element into its correct location in a sorted subarray. Here is an example of using the selection sort() method from the main class to sort the integers in ascending order:
import java.util.Scanner; // Importing the scanner function for scanning input
class SelectionSort{
public static void main(String[] args){
// Initialising the scanner function for scanning input
Scanner scn = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
// Asking the user to provide the size of the array
int size = scn.nextInt();
int[] arr = new int[size];
System.out.printf("Enter the elements in the array: ");
// Creating an array
for(int i = 0; i < size;i++){
arr[i] = scn.nextInt();
}
// Displaying an array
System.out.printf("Initial Array: ");
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
//sorting array elements using selection sort
for(int i = 0; i < size;i++){
// The index will take the value of the
// least value from the array and places
// it in the beginning
int index = i;
for(int j = i + 1; j < size;j++){
if(arr[j] < arr[index]){
index = j;
}
}
int smallNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallNumber;
}
System.out.println(" ");
System.out.println("\t ***** ");
System.out.printf("After Selection sort: ");
// Displaying the sorted array
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
}
}Output:
Enter the size of the array: 5
Enter the elements in the array: 23 25 27 98 20
Initial Array: 23 25 27 98 20
*****
After Selection sort: 20 23 25 27 98Code Explanation for sorting in selection sort:
- Begin by populating the array to be sorted.
- Starting from the first element in the array (index 0), iterate through each element in the array.
- For each element, find the minimum element in the remaining unsorted part of the array.
- Swap the current element with the minimum element found in step 2.
- Move to the next unsorted element in the array and repeat steps 2-3 until the entire array is sorted.
- The array is now sorted in ascending order.
Approach 4: Quick Sort for sorting an integer array
This common divide-and-conquer sorting method works by splitting an array into two subarrays and then sorting each subarray recursively. Here is an example of using the quick sort() method from the main class to sort the integers in ascending order:
import java.util.Scanner;
public class QuickSort{
// Driver Code
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
int size = sc.nextInt();
int[] arr = new int[size];
System.out.println("Enter " + size + " elements:");
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}
quickSort(arr, 0, size - 1);
// TO Display an array
System.out.println("\nAfter Quick Sort:");
for (int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int partitionIndex = partition(arr, start, end);
// Separately sort elements before
// partition and after partition
quickSort(arr, start, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, end);
}
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; 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[end];
arr[end] = temp;
return i + 1;
}
}Output:
Enter the size of the array: 5
Enter 5 elements:
100 45 95 25 75
After Quick Sort:
25 45 75 95 100Code Explanation for sorting in quick sort:
- Select one of the array’s pivot elements. This can be any element, although it is usually the last element in the array.
- Divide the array into two subarrays: one with elements smaller than the pivot, and the other with elements greater than the pivot.
- This may be accomplished by iterating through the array and comparing each element to the pivot, with elements less than the pivot being moved to the left of the pivot and elements bigger than the pivot being moved to the right of the pivot.
- Apply steps 1,2 and 3 to each subarray recursively until the subarrays are of length 0 or 1.
- To acquire the final sorted array, combine the sorted subarrays.
Best Approach for Sorting in Java
While wondering “how to sort an integer array in java” you may find multiple methods but when we speak about the best approach, the Quick Sort method can be said as one of the best methods to conduct sorting because:
- Flexibility: Quick sort has an average-case time complexity of O(n log n), making it an excellent choice for huge arrays. As a result, it is one of the quickest sorting algorithms in use.
- Memory: Quick sort is an in-place sorting algorithm, which means it doesn’t require any more space in addition to the array being sorted.
- Efficiency: Quick sort is a divide-and-conquer algorithm, which means it divides the issue into smaller sub-problems that are easier to solve
- Simplicity: Quick sort is simple to set up and has a tiny code footprint. It just takes a few lines of code to implement, and the algorithm is simple to comprehend and follow.
- Performance: Quick sort provides high cache performance because it accesses contiguous chunks of memory that the CPU can cache quickly.
Sample Problems for Sorting in Java
Problem 1: Write a code to take an array of integers from the user and sort it in descending order. [Any approach can be used]
Solution:
- Begin by populating the array to be sorted.
- To signify that a swap has occurred, set a flag variable to true.
- Iterate over the array from the first to the second-to-last entry while the flag is set to true.
- Each pair of neighbouring elements in the array is compared. Swap the elements if the element on the left is smaller than the element on the right.
- Set the flag to false after each iteration.
- Set the flag back to true if a swap occurred during the current iteration.
- Steps 3-6 must be repeated until the array is traversed without any swaps.
- The array is now ordered descendingly.
import java.util.Scanner; // Importing the scanner function for scanning input
class Sort{
public static void main(String[] args){
// Initialising the scanner function for scanning input
Scanner scn = new Scanner(System.in);
System.out.print("Enter the size of the array: ");
// Asking the user to provide the size of the array
int size = scn.nextInt();
int[] arr = new int[size];
System.out.printf("Enter the elements in the array: ");
// Creating an array
for(int i = 0; i < size;i++)
arr[i] = scn.nextInt();
}
// Displaying an array
System.out.printf("Initial Array: ");
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
//sorting array elements using bubble sort
for(int i = 0; i < size;i++){
for(int j = i + 1; j < size;j++){
//swaping elements
if(arr[i] < arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(" ");
System.out.println("\t ***** ");
System.out.printf("After Bubble sort: ");
// Displaying the sorted array
for(int i = 0;i < size;i++){
System.out.print(arr[i] + " ");
}
}
}Output:
Enter the elements in the array: 12 13 23 36 41
Initial Array: 12 13 23 36 41
*****
After Bubble sort: 41 36 23 13 12Problem 2: Write a code to take two arrays of integers and merge them. Later, sort them in ascending order.[Any approach can be used].
Solution:
- Create a new array with the combined length of the two input arrays.
- Copy the elements of the first array into the new array starting at index 0.
- Copy the elements of the second array into the new array starting at the end of the first array.
- Perform Bubble Sort on the new array to sort the elements in ascending order.[Refer to above]
- Return the sorted array.
import java.util.Scanner;
public class ProgramQuestion{
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// Get the first array
System.out.print("Enter the size of the first array: ");
int size1 = input.nextInt();
int[] arr1 = new int[size1];
System.out.print("Enter the elements of the first array: ");
for (int i = 0; i < size1; i++) {
arr1[i] = input.nextInt();
}
// Get the second array
System.out.print("Enter the size of the second array: ");
int size2 = input.nextInt();
int[] arr2 = new int[size2];
System.out.print("Enter the elements of the second array: ");
for (int i = 0; i < size2; i++) {
arr2[i] = input.nextInt();
}
// Merge the arrays and sort them
int[] mergedArr = new int[size1 + size2];
for (int i = 0; i < arr1.length; i++) {
mergedArr[i] = arr1[i];
}
// Copy the elements of the second array into the merged array
for (int i = 0; i < arr2.length; i++) {
mergedArr[arr1.length + i] = arr2[i];
}
// Displaying the merged array
System.out.print("Merged array: ");
for(int i = 0;i < mergedArr.length;i++) {
System.out.print(mergedArr[i] + " ");
}
// Using the bubble sort to sort the array
for(int i = 0; i < mergedArr.length;i++){
for(int j = i + 1; j < mergedArr.length;j++){
//swaping elements
if(mergedArr[i] > mergedArr[j]){
int temp = mergedArr[i];
mergedArr[i] = mergedArr[j];
mergedArr[j] = temp;
}
}
}
// Print the sorted merged array
System.out.print("Sorted merged array: ");
for(int i = 0;i < mergedArr.length;i++) {
System.out.print(mergedArr[i] + " ");
}
}
}Output:
Enter the size of the first array: 5
Enter the elements of the first array: 100 45 95 25 75
Enter the size of the second array: 5
Enter the elements of the second array: 18 13 24 98 1
Merged array: 100 45 95 25 75 18 13 24 98 1
Sorted merged array: 1 13 18 24 25 45 75 95 98 100Conclusion:
When you are trying to look for “ how to sort an array of integers in java “, there are various built-in and custom implementations of sorting algorithms available in Java. Bubble sort, selection sort, insertion sort and quicksort are some of the most often used methods for sorting numeric arrays.
While selecting a sorting algorithm, it is critical to examine the algorithm’s time and space complexity, as well as the unique needs of the situation at hand.
24×7 Live Java Homework Help From Expert Tutors!
