# [Sorting] Selection Sort Program and Complexity (Big-O)

Selection sort is a simple sorting algorithm, it’s also known as in-place comparison sort. In selection sort algorithm, sorts an array of items by repeatedly finding the minimum item from unsorted part of array and move it at the beginning. This algorithm considers two sub arrays in a given array.

1. The sub array of already sorted items.
2. Remaining sub array unsorted items.

## Points to remember

• Data structure: Array
• Worst-case performance : О(n2) comparisons and O(n)swaps
• Best-case performance : O(n2) comparisons and O(n) Swaps
• Average performance: О(n2) comparisons and O(n) Swaps
• Worst-case space complexity :О(n) total, O(1) auxiliary

• Simple Implementation and efficient for small data set.
• Efficient in  comparison to other Quadratic Sort (i.e O(n2)) like Bubble Sort or  Insertion Sort.
• Efficient for data set that are already sorted. Time Complexity ( i.e O(n))
• Not change relative order of elements which are already sorted. Space Complexity (i.e O(1))

• Selection sort is much less efficient on large lists in compare to algorithms such as quicksort, heapsort, or merge sort.

## Selection Sort Steps

Here * marks the value set on particular iteration.

 2 6 3 8 4 1 5 0 0* 6 3 8 4 1 5 2 0 1* 3 8 4 6 5 2 0 1 2* 8 4 6 5 3 0 1 2 3* 4 6 5 8 0 1 2 3 4* 6 5 8 0 1 2 3 4 5* 6 8 0 1 2 3 4 5 6* 8

## Selection Sort with Loop

```public class SelectionSort {
public static void main(String[] args) {
int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
System.out.println("Before Selection Sorting :");
printArray(items);

// Perform selection sort
selectionSort(items);

System.out.println("After Selection Sorting :");
printArray(items);
}

static void selectionSort(int items[]) {

// select item one by one based on index
for (int i = 0; i < items.length - 1; i++) {
// Find the minimum item in unsorted array
int min_idx = i;
for (int j = i + 1; j < items.length; j++)
if (items[j] < items[min_idx])
min_idx = j;

// Swap the found minimum selected item with
// the first selected item
int temp = items[min_idx];
items[min_idx] = items[i];
items[i] = temp;
}
}

static void printArray(int items[]) {
for (int item : items) {
System.out.print(item + " ");
}
System.out.println();
}
}
```

## Output

``````
Before Insertion Sorting :
2 6 3 8 4 1 5 0
After Insertion Sorting :
0 1 2 3 4 5 6 8
``````