Sorting

Selection sort

Pinterest LinkedIn Tumblr

Selection sort is sorting algorithm that divide into the sorted and unsorted part. It moves unsorted items to sorted array every step. It is an in-place comparison sort and faster than bubble sort. Write a program to implement selection sort.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class SelectionSort {
 
    public static void selection(int[] array) {
         int first;
          int tmp;
          for ( int i=array.length-1; i>0; i-- ) {
             first = 0;
             for(int j=1; j <= i; j++) {
                if( array[j] > array[first] ) 
                   first = j;
             }
             tmp = array[first];
             array[first] = array[i];
             array[i] = tmp;
          }
      
    }
    public static void main(String[] args) {
          int arr[] = {12, 11, 13, 5, 6, 7};
          System.out.println("unsorted array before sorting : " + Arrays.toString(arr));
          selection(arr);
          System.out.println("Sorted array After selection sorting : " + Arrays.toString(arr));
          }
}

Output

Unsorted array before sorting: [12, 11, 13, 5, 6, 7]
Sorted array after selection sorting: [5, 6, 7, 11, 12, 13]

Algorithm Explanation

Get a list of unsorted numbers
first find the smallest in the array and exchange it with the element in the first position
find the second smallest element and exchange it with the element in the second position
Continue in this way until the entire array is sorted.

Time Complexity

Best CaseAverage CaseWorst Case
O(n^2)O(n^2)O(n^2)

Reference

  1. http://www.sorting-algorithms.com/selection-sort
  2. https://en.wikipedia.org/?title=Selection_sort

Write A Comment