How to implement Selection sort ?

Selection sort = searching + sorting

Total passes = n-1

During each pass :

Unsorted element with the smallest (or largest) value is moved to its proper position in the array

Algorithm divides array into 2 parts :

  Sublist 1. Sorted items, from left to right

  Sublist 2. Unsorted items - remaining to be sorted

STEPS 

Initially, sorted sublist is empty and the unsorted sublist is the entire input list.

1. Find the smallest / largest (depending on sorting order) element in the unsorted sublist.

2. Swapping it with the left-most unsorted element (putting it in sorted order).

3. Moving the sorted sublist boundaries one element to the right.

4. Repeat steps 3 and 4.

Example

Initially , sorted left sublist is empty and whole list is unsorted sublist.

65 38 22 25 14

14 65 38 22 25 // sorted sublist = {14}

14 22 65 38 25 // sorted sublist = {14, 22}

14 22 25 65 38 // sorted sublist = {14, 22, 25}

14 22 25 38 65 // sorted sublist = {14, 22, 25, 38}

14 22 25 38 65 // sorted sublist = {14, 22, 25, 38, 65}

Program

public class SelectionSort {

   public static void main(String[] args) {

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

      SelectionSort.sort(array);

      SelectionSort.printArr(array);

   }

   

   private static void sort(int array[]) {

      int n = array.length;

      int idx,idxSorted;

      // idxSorted: List sorted till this index

      int iMin; // Min element index.

      for (idxSorted = 0; idxSorted < n-1; idxSorted++) {

         /* find the min element in the unsorted array[j .. n-1] */

         /**Min index is the 1st element of unsorted list(default)*/

         iMin = idxSorted;

               

         for ( idx = idxSorted+1; idx < n; idx++) {

            /**

             * Find minimum element index in Unsorted List.

             * Update the Minimum element index.

             */

             if (array[idx] < array[iMin]) {

                 iMin = idx;

             }

         }

               

         if(iMin != idxSorted) {

             /** swap(array[j]<-->array[iMin]) */

             int temp = array[idxSorted];

             array[idxSorted] = array[iMin];

             array[iMin] = temp;

         }

      }

   }

     

   private static void printArr(int[] array) {

       StringBuffer sb = new StringBuffer();

       for (int i : array) {

            sb.append(i).append(" ");

       }

       System.out.println(sb.toString());

   }

}

Output

11 12 22 25 64