How to Write a Java program for Selection Sort In Java

By | June 9, 2020

Hello Friends,
In this post, we will talk and learn about How to Write a Java program for Selection Sort in Java

Selection sort is considered as faster than bubble sort as the number of swaps is lesser but the comparison is still proportional to N2

How selection sort works

In selection sort usually, we aim is to bring the lowest element to the 0th index in the first pass or iteration. In the next pass or iteration, the second-lowest to the 1st index and so on.

We start from the 0th index and consider it is as the lowest. Then compare it with the other elements, if any element is smaller than the first element then that element becomes the lowest for further comparisons in that pass or iteration. That way we have the lowest element at the end of the pass or iteration it is then swapped with the element at the 0th index.

Similarly, in the next pass or iteration, We start with the element at the 1st index and consider it is the second-lowest element and then compare it with all the elements on its right, in between if any element smaller than this element is found then further comparisons are done using this smallest element.

For example, if we have an array [50, 20, 60, 10] then in the first iteration-

Initially, We will start with 50 (element at 0th index) and compare it with elements on its right. Since 20 is smaller than 50 so now 20 is considered the lowest.

Then 20 is compared with 60. Still, 20 is the lowest.

Then 20 is compared with 10 since 10 is smaller so it is now the lowest element and the end of the array is also reached. Swap 10 with 50 so after the first iteration array is [10, 20, 60, 50].

In the next pass or iteration, we will start with 20 (element at the 1st index) and compare it with elements on its right using the same logic for sorting.

The logic used in the Selection Sort Java Program:

There are two nested for loops, the outer loop starts from the leftmost element and goes till the one less than the number of elements in the array.

In the inner loop, we start at the index one more than the current index of the outer loop and loop until the end of the array.

Within the inner loop, elements are compared with the element currently pointed by the outer loop to get the lowest element within that iteration. Once the element is found it is swapped with the element at the current index of the outer loop.

Below is the complete source code.

Sample input/output of the above program

Enter 6 Array Elements:
123
23
45
67
10
29
Original Array::
[123, 23, 45, 67, 10, 29]
Sorted Array::
[10, 23, 29, 45, 67, 123]

Time and space complexity of Selection sort:

In the selection sort, We use two nested loops that go through the elements that make the complexity of n*n i.e. time complexity of the Selection sort is O(n^2) and the total number of comparisons is n*(n-1)/2.

In selection sort, the number of swaps is usually less in comparison to the bubble sort that makes it faster than the bubble sort.

Selection sort is also an example of “in place” sorting algorithm so apart from the input array there is no auxiliary space requirement so the space complexity of Selection sort is O(1)

You May Also Like:

That’s all about How to Write a Java program for Selection sort using the Iterative Approach?
If you have any feedback or suggestion please feel free to drop in below comment box.