Overview

Selection Sort is a sorting algorithm regarded for its simplicity. In general the performance of Selection Sort makes it inefficient for handling large lists, and generally performs slower, in practice, than the comparable Insertion Sort algorithm.

Concept

The basic concept of the Selection Sort algorithm is it sorts an array by repeatedly finding the minimum element in the unsorted portion of the array and places that element at the beginning of the array.

Algorithmic Complexity

Big-O

Algorithm	Data Structure	Time Complexity - Best	Time Complexity - Average	Time Complexity - Worst	Worst Case Auxiliary Space Complexity
Select Sort	Array	O(n^2)	O(n^2)	O(n^2)	O(1)

Implementation

Java Implementation

import java.util.Arrays;

/**
 * Selection Sort algorithm implementation
 * 
 * www.algorithmiccomplexity.com
 */
public class SelectionSort{
	
	public static int[] selectionSort(int[] unsortedArray)
	{
                int size = unsortedArray.length;

                for(int i = 0; i < size - 1; i++)
                {
                       // Find the minimum element in the unsorted array.
                       int minIndex = i;

                       for(int j = i + 1; j < n; j++)
                       {
                                        if(unsortedArray[j] < unsortedArray[minIndex])
                                        {
                                                  minIndex = j;
                                        }
                       }

                       // Swap the minimum element with the first element.
                       int temp = unsortedArray[minIndex];
                       unsortedArray[minIndex] = unsortedArray[i];
                       unsortedArray[i] = temp;
                }

		return unsortedArray;
	}
	
	/**
	 * Test driver for the selection sort algorithm.
	 * 
	 * @param args Command line arguments {@code null}.
	 */
	public static void main(String[] args)
	{
		int[] unsortedArray = new int[9];
		unsortedArray[0] = 10;
		unsortedArray[1] = 5;
		unsortedArray[2] = 3;
		unsortedArray[3] = 7;
		unsortedArray[4] = 1;
		unsortedArray[5] = 8;
		unsortedArray[6] = 8;
		unsortedArray[7] = 0;
		unsortedArray[8] = 6;
		
		System.out.println(Arrays.toString(unsortedArray));
		unsortedArray = SelectionSort.selectionSort(unsortedArray);
		System.out.println(Arrays.toString(unsortedArray));
	}
}

References

Wikipedia: Select sort

 

<- back