Selection Sort in Java - The Java Programmer

In this tutorial you will learn about selection sort in Java with example.

It will sort the input elements in ascending or descending order by taking small or large element among the input elements and swap that element with the element in 1^st position. Then it picks second small or large element and swap it with the element in second position. Likewise it will sort all the elements in the input in n-1 passes if our input size is n. While doing this process the input will be seemed as two parts one is sorted and other one is unsorted.

Now we will see the selection sort algorithm with an example.

Let us apply selection sort algorithm on an array with 7 elements.

This is our input.

Pass 1: picking the smallest element. It will scan entire array from left to right and picks the smallest element.

After that it will swap the small element with the element at first index.

After 1^st pass our array will look like this. And after 1^st pass 1 element will be sorted from left hand side.

Pass 2: In second pass it will start from the 2^nd index and start searching for smallest element in the remaining array. First smallest element is already sorted in 1^st pass. Now it will get second smallest element. It will swap with the second element from the left.

After 2^nd pass the first 2 elements are sorted.

Pass 3: In third pass it will start form 3^rd element and scan the remaining array for the smallest element. It will swap this element with the third element from the left.

After 3^rd pass first three elements will be sorted from left.

Pass 4: In 4^th pass it will start form 4^th element and scan the remaining array for smallest element and swap with the 4th element.

After 4^th pass 4 elements are sorted.

Pass 5: In 5^th pass it will start from 5^th element and scan the remaining array for smallest element. It will swap with the 5^th element form left.

After 5^th pass 5 elements will be sorted.

Pass 6: In pass 6 it will start with 6^th element and scan the remaining array for next smallest element and it will swap with the 6^th element.

After swapping 6 elements are sorted.

Here n-1 passes are completed. Our array is completely sorted. We need not to go for one more pass.

Program for Selection Sort in Java

public class SelectionSort
{
	// function for selection sort.
    void selectionsort(int arr[], int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		int min = arr[i];
    		int ind=i,j=0;
    		
    		for ( j = i+1; j < n; j++)
    		{
    			if (arr[j] < min)
    			{
    				// finding min element form remaining array.
    				min = arr[j];
    				ind=j;
    			}
    		}
    		//swapping elements.
    		int temp=arr[i];
    		arr[i] = arr[ind];
    		arr[ind] = temp;
    	}
    }
    
    public static void main(String args[])
    {
    	int a[] = {4,5,6,7,1,2,3};
    	int i;
    	
    	SelectionSort obj = new SelectionSort();
    	System.out.println("array before sorting");
    	
    	// printing array before sorting
    	for (i=0;i<7;i++)
    	{
    		System.out.print(a[i]+" ");
    	}
    	
    	obj.selectionsort(a,7);
    	System.out.println("\n\narray after sorting");
    	
    	//printing array after sorting using selection sort.
    	for (i=0;i<7;i++)
    	{
    		System.out.print(a[i]+" ");
    	}
    }
}

public class SelectionSort

{

// function for selection sort.

void selectionsort(int arr[], int n)

{

for (int i = 0; i < n; i++)

{

int min = arr[i];

int ind=i,j=0;

for ( j = i+1; j < n; j++)

{

if (arr[j] < min)

{

// finding min element form remaining array.

min = arr[j];

ind=j;

}

//swapping elements.

int temp=arr[i];

arr[i] = arr[ind];

arr[ind] = temp;

}

public static void main(String args[])

{

int a[] = {4,5,6,7,1,2,3};

int i;

SelectionSort obj = new SelectionSort();

System.out.println("array before sorting");

// printing array before sorting

for (i=0;i<7;i++)

{

System.out.print(a[i]+" ");

}

obj.selectionsort(a,7);

System.out.println("\n\narray after sorting");

//printing array after sorting using selection sort.

for (i=0;i<7;i++)

{

System.out.print(a[i]+" ");

}

Output

array before sorting
4 5 6 7 1 2 3

array after sorting
1 2 3 4 5 6 7

Time Complexity Analysis

For sorting n elements it is taking n-1 passes. In each pass it will scan entire array it will take O(n) time. Total n*O(n) that is O(n^2).

Importance of Selection Sort

It is a comparison based sort. It is famous for simplicity of algorithm and implementation. It always outperforms bubble sort. If we observe selection sort algorithm it will take O (n^2) time. But for smaller inputs it is better than other sorting which have time complexity O (nlogn). Some of n(logn) algorithms now shifting towards selection sort and insertion sort when the input is less than some threshold.

In selection sort, swapping will be always O(n) only. If we want to minimize the writes to memory then selection sort will give us better results.

Disadvantages

Always even if array is already sorted then also comparisons will be in O(n^2) only.

Comment below if you have doubts related to selection sort in Java.

Program for Selection Sort in Java

Related Posts

Leave a Comment Cancel Reply