Java Program to implement Selection Sort

         In previous post, we implemented the Bubble Sort algorithm. In this, we can implement the Selection Sort algorithm and it's time complexity.       
 
         The selection sort is a combination of searching and sorting. During each stage, the unsorted element with the smallest (or largest) value is moved to its proper position in the array. The number of times the sort passes through the array is one less than the number of items in the array. In the selection sort, the inner loop finds the next smallest (or largest) value and the outer loop places that value into its proper location.

See the below example explained with diagram,

SelectionSort.java,

package com.test;

public class SelectionSort {

      public static int[] sortArray(int[] arr){
        
           for (int i = 0; i < arr.length - 1; i++) {
                int index = i;
                for (int j = i + 1; j < arr.length; j++) {
                     if (arr[j] < arr[index]) {
                        index = j;

                     }

                }

      
                int minNumber = arr[index];  
                arr[index] = arr[i];
                arr[i] = minNumber;
           }
           return arr;
      }
 

      public static void printArray(int[] arr) {
           for (int i=0; i<arr.length; i++) {
                System.out.print(arr[i]+" ");
           }
      }
     
      public static void main(String a[]){
         
             int[] arr1 = {8,10,2,43,12,92,58,62};
             System.out.println("Array before Sorting,");
             printArray(arr1);
             System.out.println("");
             int[] arr2 = sortArray(arr1);
             System.out.println("Array after sorting,");
             printArray(arr2);
      }
}

Output :-
Array before Sorting,
8 10 2 43 12 92 58 62
Array after sorting,
2 8 10 12 43 58 62 92


Complexity:--

         Selecting the lowest element requires scanning all n elements (this takes n - 1 comparisons) and then swapping it into the first position.

Finding the next lowest element requires scanning the remaining n - 1 elements and so on,
= (n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2
= O(n^2) comparisons.

Best Case :    O(n^2) 
Worst Case :   O(n^2) 

Average Case : O(n^2)

     Note :--  Selection sort is faster and more efficient compared to bubble sort, because this sort performs less number of swaps compared to bubble sort process therefore even both the sorting methods are of O(n^2).

Related Post :-
1) Java Program for Bubble Sort in Ascending and Descending order
2) Java Program to Sort ArrayList of Custom Objects By Property using Comparator interface
3)  Difference between Comparable and Comparator Interface in Java