Select Sort

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

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Select SortArray 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