How to Sort an Array in Java

Sorting is one of the most common and necessary operations in programming. It represents the ordering of some set of elements in a specific order. This article is about standard methods for sorting arrays in Java.

Briefly about sorting

So, sorting is the ordering of a set of data. In our case, arrays. The purpose of sorting arrays or other data structures is to make it easier to find, manipulate, or parse the data in the collection. Programmers need sorting so often that any programming language includes built-in methods for sorting arrays, lists, and other ordered data structures. To use such methods, call them. The operation is simplified as much as possible. Usually, built-in methods are maximally optimized; in most cases, using them for your job or projects is a good idea. However, almost every programmer, during their studies, needs to implement sorting algorithms by themselves. Therefore, these perfect exercises teach you to understand the very essence of programming. In addition, sometimes you need non-standard sorting methods in the work. There are many sorting algorithms. They have strengths and weaknesses depending on the type or size of the data sets. Standard sorting algorithms include bubble sort, selection sort, insertion sort, merge sort, and quicksort.

Built-in method for sorting arrays in Java: Arrays.sort

Let's start with the simplest. Someone has already written a method for sorting arrays in Java for us. This method is in the Arrays class, more specifically java.util.Arrays. This class contains various methods for working with arrays, such as sorting and searching. The Arrays.sort method provides a convenient way to sort array in Java, whether they contain strings, integers, or other elements. There are several variations of the Arrays.sort method in Java. Here are some commonly used sorting methods from the Arrays class:

• Arrays.sort(Array): use it to sort arrays of primitive types or objects in ascending order. It uses the natural ordering of the elements.
• Arrays.sort(Array, fromIndex, toIndex): This overloaded sort method allows you to sort only a portion of the Array specified by the fromIndex and toIndex parameters.
• Arrays.sort(Array, comparator): this one is for sorting arrays of objects using a custom comparator. The comparator defines the ordering of the elements.
• Arrays.parallelSort(Array): This method version sorts the Array in parallel, utilizing multiple threads for improved performance. It's beneficial for sorting large arrays.
• Arrays.parallelSort(Array, fromIndex, toIndex): This overloaded version of the parallelSort method allows sorting a specific range of elements in the Array.

They allow you to quickly arrange the elements based on their natural order or using a custom comparator. Let's explore this method with two examples, one involving strings.

Example 1: Sorting Strings

Suppose we have an array of string musical instruments: "violin", "viola", "cello", and "double bass". We can use the Array.sort method to arrange them alphabetically.

import java.util.Arrays;
//Arrays.sort example 
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

The output is here: In this program, first, we import the java.util.Arrays class to gain access to the Array.sort method. Then we create a string array called instruments containing the musical instrument names. After it, we call Arrays.sort(instruments). So this method gets an array, sorts elements in ascending order based on their natural ordering (alphabetical). Finally, we loop through the sorted Array and print each instrument out.

Example 2: Sorting Integers

Let's consider another example where we sort an array of integers in ascending order.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort 
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Output: Here we create an integer array called numbers with several unsorted elements. Next, we call Arrays.sort(numbers) to sort an array in ascending order. Note that the Array.sort method modifies the original array in-place. So to keep the original Array, make a copy before sorting.

Example 3: descending order

What about descending sort? It's also easy with Arrays.sort. Just use a custom comparator. Here's an example:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example 
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort 
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

The output is next: Here we've got an array of integers named numbers. By passing Comparator.reverseOrder() as the second argument to the Arrays.sort method, we specify a custom comparator that sorts the elements in descending order. The Comparator.reverseOrder() method returns a comparator that reverses the natural ordering of the elements. Note that here, we use the Integer wrapper class instead of the primitive int type because the Comparator.reverseOrder() method requires objects. If you have an array of primitive int values, you'd also need to convert them to Integer objects before using this approach. Using a custom comparator, you can easily sort array in descending order using the Arrays.sort method in Java.

Self-written classical sorting algorithms in Java

You've already seen Array sorting assignments if you're studying Computer Science independently or at university. There are many different sorting algorithms, and we'll implement some of them in this article. Generally, the easier an algorithm is to implement, the less efficient it is. Programmers measure the efficiency of algorithms is measured by the time of its operation and the memory that is spent on resources. That's not the topic of our article, but we mention that Arrays.sort in Java is an effective algorithm.

Bubble Sort

Let's start with the most popular algorithm among students: Bubble sort. It's straightforward: the algorithm compares two elements and then swaps them if they are in the wrong order, and so on until the end of the array. It turns out that smaller elements "float" to the end of the Array, like bubbles in soda pop to the top.

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Here the method takes an array of integers as input. The outer loop goes from 0 to n-1. Here n is the array's size. The inner loop compares adjacent elements. If the order is wrong, the method swaps them. This procedure is repeated until the entire array has been sorted. Here is an output of our program:

Selection Sort

Selection algorithm sorts an array by repeatedly finding the smallest element from the unsorted part and placing it at the beginning. Let’s write it in Java:

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

Here is an output of the program: Let’s explain it step-by-step. The outer loop iterates from the beginning of the Array to the second-to-last element (up to n-1). This loop selects each element one by one as the starting point of the unsorted part of the Array. Inside the outer loop, we initialize minIndex to the current index i, assuming it to be the index of the smallest item in the unsorted part of the Array. The inner loop starts from i+1 and goes up to the last element of the Array. It searches for the index of the smallest item in the unsorted part of the Array by comparing each element with the current minimum element (arr[minIndex]). If we find an element that is smaller than the current minimum element, we update minIndex to the index of the new minimum element. After the inner loop completes, we've found the index of the minimum element in the unsorted part of the Array. We then swap the minimum element with the first element of the unsorted part by using a temporary variable temp. The outer loop continues until all elements are sorted, gradually extending the sorted part of the Array. Finally, the sorted Array is printed in the main method before and after calling the selectionSort method.

Merge Sort

Merge Sort is a divide-and-conquer algorithm that recursively divides the Array into smaller subarrays, sorts them, and then merges them to obtain a sorted array. Merge Sort is stable and widely used, especially when stability and a guaranteed worst-case time complexity are required.

public class MergeSort {
    
      //Merge Sort array  
      public static void mergeSort(int[] myArray) {
        if (myArray.length <= 1) {
            return;
        }

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        while (i < left.length) {
            arr[k++] = left[i++];
        }

        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

The output here is: Let’s explain more precisely how it works. The algorithm divides the Array into two parts recursively until the base case is reached (when the Array has one or zero elements). Then it merges the sorted halves back together using the merge method. The merge method takes three arrays as input: the original Array and the left and right subarrays (left and right). It compares the elements from the left and right subarrays and merges them into the original Array in sorted order.

Insertion sort

Insertion Sort works by repeatedly inserting an element from the unsorted part into its correct position in the sorted part. It performs well for small data sets or nearly sorted data.

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

The output of the program is just like usual: Here the insertionSort method implements the Insertion Sort algorithm. It iterates through the Array and considers each element as a key. It compares the key with the elements before it and moves them one position ahead if they are greater, effectively shifting the elements to make room for the key at the correct position. The outer loop iterates from the second element (i = 1) to the last element of the Array. The inner loop starts from the current element (arr[i]) and goes backward (j = i - 1) until it finds the correct position for the key or reaches the beginning of the Array. Inside the inner loop, if an element (arr[j]) is greater than the key, it is shifted one position ahead (arr[j + 1] = arr[j]) to make room for the key. This process continues until the correct position for the key is found. After the inner loop completes, the key is placed at the correct position (arr[j + 1] = key). In the main method, an example array is created and printed before and after sorting using the insertionSort method.

Quick sort

Quick Sort is a divide-and-conquer algorithm that selects a pivot element and partitions the Array around the pivot. As a rule, Quick Sort is faster than Merge Sort for small and medium-sized data sets due to its low constant factors.

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 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++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

The output is here: So here we've got three methods to implement quick sort. The quickSort method takes three parameters: the Array to be sorted, the low index of the subarray, and the high index of the subarray. Initially, it checks if the subarray has more than one element. If so, it selects a pivot using the partition method, recursively sorts the subarray before the pivot, and recursively sorts the subarray after the pivot. The partition method selects the pivot as the last element of the subarray (arr[high]). It sets the partition index (i) to the low index minus 1. It then iterates from the low index to the high index - 1 and checks if each element is less than or equal to the pivot. If so, it swaps the element with the element at the partition index (i) and increments the partition index. Finally, it swaps the pivot element with the element at the partition index + 1 and returns the partition index. The partition method selects the pivot as the last element of the subarray (arr[high]). It sets the partition index (i) to the low index minus 1. It then iterates from the low index to the high index - 1 and checks if each item is smaller or equal to the pivot. If so, it swaps the element with the element at the partition index (i) and increments the partition index. Finally, it swaps the pivot element with the element at the partition index + 1 and returns the partition index. The swap method is a utility method used to swap two elements in the Array. In the main method, an example array is created and printed before and after sorting using the quickSort method.

Conclusions

From this article you've found out how to sort an array in Java language. You can use a built-in Arrays.sort method or write your own implementations of popular sorting methods such as bubble sort, merge sort and so on. Also you can try to invade your own sorting method. It depends on your task. If you need to solve a sorting problem fast, just use a pre-written method. If you learn programming and try to be better at it, it's a really good idea to write some sorting methods by yourself.