Selection Sort

The selection sort is a combination of searching and sorting. During each pass, 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.

NOTE: You should never write your own sort. Use the java.util.Arrays.sort(...) orjava.util.Collections.sort(...).

Two nested loops. Like all simple sorts, selection sort is implemented with two nested loops.

Simple selection sort

The basic idea is to look at each element in the array, and for each element look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.

public static void selectionSort1(int[] x) {
    for (int i=0; i<x.length-1; i++) {
        for (int j=i+1; j<x.length; j++) {
            if (x[i] > x[j]) {
                //... Exchange elements
                int temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            }
        }
    }
}

More efficient selection sort - Move every value only once

This more efficient variation of selection sort remembers the index of the smallest element that it finds in each pass. At the end of each pass it makes one exchange, if necessary. This is more efficient, but you shouldn't be writing your own sort - use java.util.Arrays.sort(...)!

public static void selectionSort2(int[] x) {
    for (int i=0; i<x.length-1; i++) {
        int minIndex = i;      // Index of smallest remaining value.
        for (int j=i+1; j<x.length; j++) {
            if (x[minIndex] > x[j]) {
                minIndex = j;  // Remember index of new minimum
            }
        }
        if (minIndex != i) { 
            //...  Exchange current element with smallest remaining.
            int temp = x[i];
            x[i] = x[minIndex];
            x[minIndex] = temp;
        }
    }
}

ANOTHER CODE ON SELECTION SORT

// Java program for implementation of Selection Sort

class SelectionSort

{

    void sort(int arr[])

    {

        int n = arr.length;



        // One by one move boundary of unsorted subarray

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

        {

            // Find the minimum element in unsorted array

            int min_idx = i;

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

                if (arr[j] < arr[min_idx])

                    min_idx = j;



            // Swap the found minimum element with the first

            // element

            int temp = arr[min_idx];

            arr[min_idx] = arr[i];

            arr[i] = temp;

        }

    }



    // Prints the array

    void printArray(int arr[])

    {

        int n = arr.length;

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

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

        System.out.println();

    }



    // Main method to test the insertion

    public static void main(String args[])

    {

        SelectionSort ob = new SelectionSort();

        int arr[] = {64,25,12,22,11};

        ob.sort(arr);

        System.out.println("Sorted array");

        ob.printArray(arr);

    }

}

/* This code is contributed by Onuoha David*/

Output:

Sorted array:
11 12 22 25 64

ANOTHER EXAMPLE OF INSERTION SORT

1. public class SelectionSortExample {  
2.     public static void selectionSort(int[] arr){  
3.         for (int i = 0; i < arr.length - 1; i++)  
4.         {  
5.             int index = i;  
6.             for (int j = i + 1; j < arr.length; j++){  
7.                 if (arr[j] < arr[index]){  
8.                     index = j;//searching for lowest index  
9.                 }  
10.             }  
11.             int smallerNumber = arr[index];   
12.             arr[index] = arr[i];  
13.             arr[i] = smallerNumber;  
14.         }  
15.     }  
16.        
17.     public static void main(String a[]){  
18.         int[] arr1 = {9,14,3,2,43,11,58,22};  
19.         System.out.println("Before Selection Sort");  
20.         for(int i:arr1){  
21.             System.out.print(i+" ");  
22.         }  
23.         System.out.println();  
24.           
25.         selectionSort(arr1);//sorting array using selection sort  
26.          
27.         System.out.println("After Selection Sort");  
28.         for(int i:arr1){  
29.             System.out.print(i+" ");  
30.         }  
31.     }  
32. }  

Output:

Before Selection Sort
9 14 3 2 43 11 58 22 
After Selection Sort
2 3 9 11 14 22 43 58 

public class MySelectionSort {



    public static int[] doSelectionSort(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 smallerNumber = arr[index];  

            arr[index] = arr[i];

            arr[i] = smallerNumber;

        }

        return arr;

    }

     

    public static void main(String a[]){

         

        int[] arr1 = {10,34,2,56,7,67,88,42};

        int[] arr2 = doSelectionSort(arr1);

        for(int i:arr2){

            System.out.print(i);

            System.out.print(", ");

        }

    }

}

Output:
Sorted array:
2, 7, 10, 34, 42, 56, 67, 88,

Time Complexity: O(n2) as there are two nested loops.

Auxiliary Space: O(1)
The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

While being an easy sort to program, the selection sort is one of the least efficient.  The algorithm offers no way to end the sort early, even if it begins with an already sorted list.  

// Selection Sort Method for Descending Orderpublic static void SelectionSort ( int [ ] num )
{
     int i, j, first, temp;
     for ( i = num.length - 1; i > 0; i - - )
     {
          first = 0;   //initialize to subscript of first element
          for(j = 1; j <= i; j ++)   //locate smallest element between positions 1 and i.
          {
               if( num[ j ] < num[ first ] )         
                 first = j;
          }
          temp = num[ first ];   //swap smallest found with element in position i.
          num[ first ] = num[ i ];
          num[ i ] = temp;
      }         
}