Selection Sort in Java and its Working Procedure in 2024

Selection Sort in Java is the popular topic that people search on online. In our previous article, we have learned about the Bubble Sort Algorithm. That was a very simple and classic algorithm. Today we are going to learn another simple sorting algorithm which name is the Selection Sort Algorithm.

What is Selection Sort in Java?

Selection Sort in Java Algorithm is a comparison sorting algorithm like Bubble Sort Algorithm. It is used for sorting a random list of items. This algorithm divides the input collection or list into two parts: one is for sorted items and another part is for unsorted items. The goal of this algorithm is similar to the Bubble Sort Algorithm. But the working procedure is different.

How Selection Sort in Java Works?

This algorithm proceeds by selecting the largest or the smallest (according to the sorting order) item in the unsorted part of the list and swap the selected item with the leftmost or rightmost unsorted item (near the sorted portion of the list). And then the boundary of the sorted and unsorted item is shifted by one to the unsorted item.
For example, let’s consider an unsorted list where the last portion is sorted and the first portion is unsorted. But at the very beginning, the whole list is unsorted.

For explaining the working procedure, let’s consider a unsorted list is below:

[32, 30, 55, -10, 50, 5]

As at the very beginning the whole list is unsorted, let’s consider the last unsorted item’s position is 5. And as this algorithm proceeds by selecting the largest or smallest item to shift to the right position, first we consider the position 0 is containing the largest number (we are ordering the list ascending). Now we compare the value of position 0 with the value of position 1. Still, the value of position 0 (32) is greater than the value of position 1 (30).

Now, again, we compare the value of position 0 with the value of position 2 (55). And we have found that the value of position 2 is greater than position 0. So, now the largest value is situated in the 2nd position. The largest value, value of position 2, is compared with the value of position 3, position 4, and position 5. In this loop, finally, the largest value is situated in position 2. Now the value of position 2 will be swapped with the last unsorted item. And the last unsorted item’s position will be decreased by one (the boundary of sorted and unsorted portions shifted to left by one).

Now the list looks like this:

[32, 30, 5, -10, 50, 55]

Now the 2 parts are visible, the first part is from position 0 to position 4 which is unsorted and the second part is just containing 1 item, 55, which is sorted.
If we iterate the same procedure again in the unsorted part, we will see the last unsorted item and the largest item are the same. In this case, this value could remain in the same position. And the boundary between the two parts will shift to the left by one.
But for the case of 3rd iteration, the last unsorted position is 3 and the item is -10. Here, 32 will be swapped with -10 and the boundary between sorted and unsorted lists will be shifted to left by one. And this iteration will be repeating until the whole list is sorted. Finally, we will get the output list as like below:

[-10, 5, 30, 32, 50, 55]

Example of Selection Sort in Java Algorithm using Java

This is one of the implementations of the Selection Sort in Java Algorithm. There are many ways to implement the Selection Sort algorithm other than this.
In our above program, we always identify the last unsorted item’s position with whom the largest item will be replaced. After each iteration, the position of the last unsorted item is decreased by one. Initially we consider the first item of the unsorted list is largest (largestItemsPosition = 0) and inside the inner loop, we start comparing this largest item with 1 to last unsorted item (int i = 1; i <= lastUnsortedItem; i++).

Time complexity of Selection Sort in Java

For sorting an entire array using this sorting algorithm, we must traverse through the array once for each value of the unsorted list. That does mean, if we have n number of items in an input list used for this algorithm, the time complexity of this algorithm will be n * n . So, the time complexity of this algorithm is O(n²). Even if the whole input list is already sorted, we must need to traverse through the array. Consequently, we can say, for the best-case, worse-case and the average case, the time complexity of the Selection Sort in Java Algorithm is O(n²).