Introduction on Selection Sort in Java
Selection Sort in Java is a sorting method that continually finds the smallest element in the unsorted part and keeps it in the beginning (for sorting in ascending order). The process will be repeated until the input array is sorted. Also, in Selection Sort, we will be dividing the input array into two subarrays where one array is used for sorted elements and other array is for unsorted elements. In the beginning, there won’t be any elements in the sorted subarray. Let us see the working of the selection sort in detail in the following section.
How Selection Sort Works in Java
Selection sort works in a simple manner where it keeps two subarrays from the input array. They are:
- Sorted subarray to keep the sorted elements
- Unsorted subarray to keep the unsorted elements.
Algorithm
Following is the algorithm that is used for Selection sort
- Set the minimum (MIN) pointer to location 0.
- Find the smallest element from the list of elements in the array
- Swap the minimum element with the location 0
- Move the MIN pointer to next position
- Repeat the process until the input array is sorted.
Let us understand the selection sort with an example. Following is the input array that has to be sorted. The elements in Bold Blue color will be as part of the sorted array.
Step 1: Set the MIN pointer to the first location. So, the MIN pointer points to 15.
Smallest: = 15
Step 2: Find the smallest element by comparing it with the rest of the elements. Comparing 15 and 21, 15 is the smallest. So, the smallest won’t change in this case.
4.8 (7,057 ratings)
View Course
Smallest: = 15
Comparing 15 and 6, 6 is the smallest.
Smallest: = 6
Comparing 6 and 3, 3 is the smallest.
Smallest: = 3
3 will be smaller in this case also, as 19 is greater than 3.
Smallest: = 3
Smallest: = 3
Finally, in this iteration, 3 is found to be the smallest.
Step 3: Swap the smallest element with the element in location 0.
Step 4: Increment the MIN pointer to the next position.
Step 5: Find the next smallest element by comparing it with the rest of the elements.
Smallest: = 21
Smallest: = 6
Smallest: = 6
Smallest: = 6
Smallest: = 6
Step 6: Swap the smallest element with the element in location 1.
Repeat the process until a sorted array is formed as shown below.
Examples to Implement Selection Sort in Java
As already mentioned above, selection sort is based on finding the minimum and swapping. Now, let us see how to implement the selection sort using Java.
Java Program to Sort the Elements in an Array using Selection Sort
Code:
import java.util.*;
public class SelSortExample {
//Method that implements Selectionsort
public static void selsort(int[] arr)
{
int n=arr.length; //length of the array
for(int i=0;i<n-1;i++)
{
int MIN=i; //set the first position as minimum
System.out.println("Sorting based on Number "+(i+1));
//Find the smallest element by comparing with the element in MIN position
for(int j=i+1;j<n;j++)
{
System.out.println("Comparing "+ arr[MIN] + " and " + arr[j]);
if(arr[j]<arr[MIN])
{
System.out.println(arr[MIN] + " is greater than " + arr[j] );
MIN=j;
}
}
//Swap the smallest element with element in MIN position
int temp=arr[i];
arr[i]=arr[MIN];
arr[MIN]=temp;
}
}
public static void main(String[] args) {
int[] arr= {15,21,6,3,19,20}; // input array
System.out.println("Elements in the array before Sorting: "+ Arrays.toString(arr));
selsort(arr);//calling the selection sort method
System.out.println("Elements in the array after Sorting: "+Arrays.toString(arr));
}
}
Sample Output:
In the above program, we have two methods-main methods and sell sort method. Main method calls the sell sort method passing the input array as the argument. The minimum element will be identified and swapped with the element pointed by MIN.
The selection sort can be also used where the input array is not defined in code. Let us see how it works using the below program.
Java Program to Sort the Elements using Selection Sort
Code:
import java.util.*;
public class SelectionSortExample
{
public static void main(String args[])
{
int n, i, j, tempvar;
Scanner sc = new Scanner(System.in); //To take the input from user
System.out.print("Enter the size of array : \n");
n = sc.nextInt();
int array[] = new int[n]; //initialising the array
System.out.print("Enter the elements that need to be inserted in the array : \n");
//inserting the elements to the array
for(i=0; i<n; i++)
{
array[i] = sc.nextInt();
}
System.out.print("array before Sorting: \n"+ Arrays.toString(array));
System.out.print("\nSorting begins here..\n");
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(array[i] > array[j])
{
tempvar = array[i];
array[i] = array[j];
array[j] = tempvar;
}
}
}
System.out.print("Array after Sorting is :\n");
for(i=0; i<n; i++)
{
System.out.print(array[i]+ " ");
}
}
}
Sample Output:
Here, the input elements given by the user will be compared with the temporary variable and swapped. The process will be repeated until a sorted array is formed.
Performance of Selection Sort
This sorting technique is used for its simplicity and certain other performance advantages over other more sorting techniques.
Conclusion
The selection sort does not work efficiently on large lists as it consumes more time for comparison. Selection sort is a method in which an input array will be divided into two subarrays in order to keep them sorted and unsorted elements. The minimum element in the array will be swapped with the element in the first position and the process continues until a sorted array is formed.
Recommended Articles
This is a guide to Selection Sort In Java. Here we discuss the Introduction, Working, and Performance of Selection Sort along with some Examples. You may also look at the following articles to learn more –
