Select Page

Selection Sort in Java

Selection sort is also a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion of the input array, and placing it in the sorted portion of the array. Thus, selection sort maintains two subarrays, one is sorted and another one is not sorted. In every iteration, the size of the sorted subarray increases, and the size of the unsorted subarray decreases.

Algorithm and Pseudo Code

Selection Sort Java Program

The following Java program implements the selection sort algorithm.

FileName: SelectionSortExample.java

Output:

Explanation: In the above program, the first iteration of the outer loop finds the minimum element of the array, and the minimum element is placed at the first index, i.e., the 0th index, the second iteration of the outer loop finds the second minimum element of the array and puts the second minimum at the 1st index, the third iteration find the third minimum, places it on the 2nd index and so on for rest of the iteration. Thus, virtually dividing the array into the sorted and unsorted parts. The following diagram depicts the same.

It is the inner for-loop that does the searching of minimum elements. The outer loop tells the inner loop from where it should start the search of minimum element.

Analysis of the Selection Sort

If we observe, we find that selection sort is nothing but the reverse process of bubble sort. In bubble sort every, every iteration finds the maximum elements of the array and places those maximum elements at the rightmost side. In selection sort, every iteration finds the minimum elements of the array and places those minimum elements at the leftmost side. Thus, the behavior of the selection sort is almost similar to the selection sort.  The good thing about selection sort is it never makes more than n swaps to do the sorting, where n is the size of the array or list.

Time Complexity

Selection sort never cares about the arrangement of elements, i.e., even if a sorted array is provided as the input, the selection sort goes on to find the minimum element for the sorted array. Because of the nesting of two for loops, the time complexity of the selection sort is O(n^2), where n is the number of elements present in the list/ array. Since this sorting algorithm is independent of element arrangements, the best, average, or in the worst case, the time complexity remains the same, i.e., O(n^2).

Space Complexity

The selection sort does the in-place sorting. Therefore, the space complexity for the selection sort turns out to be O(1), i.e., constant space for sorting the input array or list.

Conclusion

Similar to bubble sort, this sorting algorithm should not be used for large lists or arrays because of the time complexity O(n^2). For a small list, one can go with the selection sort.