Selection Sort in Java | Selection Sort Program in Java

What is Selection Sort?

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort in Java is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Worst case performance : О(n²)
Best case performance : O(n²)
Average case performance : О(n²)

Selection Sort Algorithm:

selectionSort(array, size)
 repeat (size - 1) times
  set the first unsorted element as the min element
  for each unsorted element, if element is less than currentMin
       set the element as the newmin
 swap min with the first unsorted position
end selectionSort

Problem Solution

1. Starting from the beginning pick one number.
2. Compare it with others one by one.
3. Replace if the other number is lesser than this one.
4. Display the result.

Selection Sort Example:

If we have the array as {40,10,50,70,30}
and we apply selection sort to sort the array,
then the resultant array after each iteration will be as follows:

               Original array: {40, 10, 50, 70, 30}

Array after first  iteration         10  ->    40  ->    50  ->    70  ->    30
Array after second iteration         10  ->    30  ->    50  ->    70  ->    40
Array after third iteration          10  ->    30  ->    40  ->    70  ->    50
Array after fourth iteration         10  ->    30  ->    40  ->    50  ->    70
Array after fifth iteration          10  ->    30  ->    40  ->    50  ->    70
            
               Sorted array is  10  30  40  50  70

Program/Source Code

Here is source code of the Java Program to implement Selection Sort. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
/*
```

 * Java Program to Implement Selection Sort

```
 */
```
```
 
```
```
import java.util.Scanner;
```
```
 
```
```
/* Class SelectionSort */
```
```
public class SelectionSort 
```
```
{
```
```
    /* Selection Sort function */
```

    public static void sort( int arr[] ){

```
        int N = arr.length;
```
```
        int i, j, pos, temp;
```
```
        for (i = 0; i < N-1; i++)
```
```
        {
```
```
            pos = i;
```
```
            for (j = i+1; j < N; j++)
```
```
            {
```
```
                if (arr[j] < arr[pos])
```
```
                {
```
```
                    pos = j;
```
```
                }
```
```
            }
```

            /* Swap arr[i] and arr[pos] */

```
            temp = arr[i];
```
```
            arr[i] = arr[pos];
```
```
            arr[pos]= temp;            
```
```
        }        
```
```
    }
```
```
    /* Main method */
```

    public static void main(String[] args)

```
    {
```

        Scanner scan = new Scanner( System.in );

```
 
```

        System.out.println("Selection Sort Test\n");

```
        int n, i;
```
```
        /* Accept number of elements */
```

        System.out.println("Enter number of integer elements");

```
        n = scan.nextInt();
```

        /* Create integer array on n elements */

```
        int arr[] = new int[ n ];
```
```
        /* Accept elements */
```

        System.out.println("\nEnter "+ n +" integer elements");

```
        for (i = 0; i < n; i++)
```
```
            arr[i] = scan.nextInt();
```
```
        /* Call method sort */
```
```
        sort(arr);
```
```
        /* Print sorted Array */
```

        System.out.println("\nElements after sorting ");

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

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

        System.out.println();

```
    }
```
```
 
```
```
}
```

Program Explanation:

1. The program defines a class named SelectionSort. Inside the class, there is a sort method that takes an integer array arr as its parameter.
2. The method begins by determining the length of the array N.
3. It uses nested loops to perform the selection sort:

The outer loop runs from i = 0 to N-2, as the last element will be in its correct position after the other elements are sorted.
For each i, it initializes pos as i.

4. The inner loop, with index j, runs from i+1 to N-1, comparing each element with the element at pos to find the smallest element.
5. If an element at index j is smaller than the element at pos, it updates pos to j.
6. After the inner loop completes, the program swaps the elements at arr[i] and arr[pos] to place the smallest element in its correct position at the beginning of the unsorted portion.
7. This process repeats until the entire array is sorted in ascending order.
8. In the main method, the program takes user input for the number of elements and the elements themselves.
9. It then calls the sort method (Selection sort algorithm) to sort the array and prints the sorted array to the console.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Runtime Test Cases

Testcase 1: In this case, all sorted elements are entered in reverse order.

Selection Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
999 921 823 816 767 712 698 657 532 412 391 323 287 256 225 162 123 64 24 6
 
Elements after sorting
6 24 64 123 162 225 256 287 323 391 412 532 657 698 712 767 816 823 921 999

Testcase 2: In this case, we are entering all sorted elements.

Selection Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991
 
Elements after sorting
12 34 68 79 123 145 178 213 253 276 298 301 498 512 633 792 888 912 950 991

Testcase 3: In this case, we are entering all unsorted elements.

Selection Sort Test
 
Enter number of integer elements
20
 
Enter 20 integer elements
54 135 23 75 1 576 234 928 13 84 631 1283 748 124 54 6 24 485 1024 0
 
Elements after sorting
0 1 6 13 23 24 54 54 75 84 124 135 234 485 576 631 748 928 1024 1283

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

If you find any mistake above, kindly email to [email protected]

» Next - Java Program to Implement Insertion Sort

Related Posts:

Recommended Articles: