Sorting functions in Java

Sorting is a class of algorithms in Java that helps in arranging the position of elements in an array in either an ascending or descending manner. Sorting helps in arranging the elements within an array in such a manner that order is maintained. An optimized sorting algorithm also needs to ensure that elements having the same value don’t change their locations in the sorted array. This should be done keeping in mind the time taken to do the optimization in rearranging the elements.

Types of Sorting in Java

The following are the different ways of doing sorting in Java:

• Using sort() method

  • The Arrays class in java.util package provides a sort() method to arrange the elements of an array in ascending order. It accepts arrays of type int, float, double, long, char and byte.

  • The Collections class also provides the sort() method to sort an array. But this method is applicable for sorting objects like LinkedList and ArrayList.

• Without using sort() method

  • In this case, we use ‘for loop’ to initialize data types and sort them in ascending or descending order. We can also formulate user-defined methods to sort the elements in an array.

Examples of how to do sorting

The following examples show how sorting can be achieved in different ways:

Quick Sort

Let’s consider the following case where we have to convert an unsorted array into a sorted array. There are two important keywords, in this case, pivot and partnership. The pivot is a central point around which the sorting will be implemented. Partitioning is the process of partitioning or arranging the elements around this pivot. The pivot of an array can be assigned in any of the following four ways:

• A random element can be made a pivot.

• The median of all the elements can be designated as a pivot.

• The first element can be made as a pivot.

• The last element can be made as a pivot.

Usually, we will take the last element as a pivot and sort the elements in the array.

​8

5

11

6

3

10

Here, all the elements smaller than the pivot come in one partition. So, 10 becomes the pivot, and elements smaller than the pivot get partitioned on one side and the elements larger than the pivot becomes partitioned on the other side. So one partition reads as [8,5,6,3] and the other partition reads as [10, 11]. The largest number is 11, and the pivot is 10. Now take 3 as the pivot in the first partition and put the larger number after that. So the first partition now reads as [3, 8, 5, 6]. Following these recursive sorting steps, we will take 6 as the pivot in the next step and sort it out. This tree will result in the sorted array as follows:

​3

5

6

8

10

11

Example of QuickSort function

The output of QuickSort function

Merge Sort

We have an unsorted array. The approach of using merge sort is based on a divide and conquer approach to sort out an array.

8

5

9

4

3

7

The first step is to divide this array into two smaller arrays, [8,5,9] and [4,3,7]. We can further subdivide these two arrays into [8,5], [9], [4,3] and [7]. We further subdivide them into single elements which is the last level of sorting as individual elements cannot be sorted further. For the array [8,5] and [9] we overcome or conquer it by sorting it as [5,8,9]. Similarly, we get [3,4,7] from the other half. We finally sort these two partially sorted arrays and merge them into the final sorted array [3,4,5,7,8,9]. This is shown in the pictorial form below:

Example of MergeSort function

Bubble Sort

For arranging elements in ascending order through bubble sort, we choose the highest value element and push it towards the end of the array. If the number of elements is n then the bubble sort will run a loop through the array n-1 times and arrange them with the greatest at the end and preceded by smaller elements. Adjacent elements will be compared and swapped with each other depending on their ascending order. For arranging in descending order, the opposite order of arrangement will be followed.

Example of bubble sort

Selection Sort

In selection sort, we sort out the smallest element and bring it to the front of the array. The inner loop picks the minimum element from the array and moves it to its correct index as indicated by the outer loop. In every iteration of the outer loop, one element is shifted to its correct location in the array. If the current element in the inner loop is smaller than the marked minimum element, then the value of the minimum element is changed to the current element.

Example of selection sort

Insertion Sort

First, the array is divided into two parts, the sorted part consisting of the key element and the rest of the elements also called the unsorted part. If the key element is smaller than its predecessor, it is shifted to its current location in the array. Keep moving the elements from the sorted section of the array till the correct location of the key is found.

Example of insertion sort

The time complexity of sorting algorithms

Time complexity is the amount of time taken by an algorithm to run as a function of the length of its input and statements. It gives information about the increase or decrease in execution time when the number of operations varies in an algorithm. Understanding the time complexities of sorting algorithms helps in picking out the most optimised sorting technique to solve a given problem.

Summary

There are different types of sorting functions available in Java. Merge sort implements the same number of sorting steps in different kinds of cases and sometimes is considered an optimized approach to solving sorting problems. Considering the amount of big data being generated, we need effective and optimized algorithms to handle data structure-related problems. Knowing the time complexity involved in obtaining the output along with the data input size helps organisations effectively deploy their time and resources.