Greedy

Selection sort algorithm

Pinterest LinkedIn Tumblr

Selection sort is a sorting algorithm that divide into the sorted and unsorted part. It moves unsorted items to sorted array every step. Selection sort 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 the list of unsorted numbers.
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
(n^2)(n^2)(n^2)

Reference

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

Write A Comment