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