# Selection Sort in Java and Complexity Analysis

Selection sort is a sorting algorithm, precisely an in-place comparison sort. The selection sort improves over the bubble sort by reducing the number of swapping necessary from O(n2) to O(n). But the number of comparisons remains O(n2).

##### Selection Sort Java Example
```package com.sneppets.dsalgo;

public class SelectionSortExample {

public static int[] doSelectionSort(int[] inArray){

int i, j, nElements, min;

nElements = inArray.length;

for(i=0; i < nElements-1; i++)	//outer loop
{
min = i;		//minimum

for (j = i+1; j < nElements; j++) //inner loop
{
//if min is greater, we have a new min
if(inArray[j] < inArray[min]){
min = j;
}
}
//At the end of inner loop min points to the minimum value
//and the array elements pointed to by i and min are swapped.

//swap
swap(i, min, inArray);
}

return inArray;
}

private static void swap(int i, int min, int[] inArray) {

int temp = inArray[min];
inArray[min] = inArray[i];
inArray[i] = temp;
}

public static void main(String[] args){

int[] inArray = {24,10,2,30,15,6,20,8};

System.out.println("Array elements before selection sort");
printArrayElements(inArray);

System.out.println("Array elements after selection sort");
int[] outArray = doSelectionSort(inArray);
printArrayElements(outArray);
}

private static void printArrayElements(int[] inArray) {
for(int i=0; i<inArray.length; i++){
System.out.print(inArray[i] + ", ");
}
System.out.println("\n");
}

}
```
##### Output
```Array elements before selection sort
24, 10, 2, 30, 15, 6, 20, 8,

Array elements after selection sort
2, 6, 8, 10, 15, 20, 24, 30,```

Note: At each new position of j, the elements inArray[j] and inArray[min] are compared. At the end of the inner loop, min points to the minimum value and the array elements pointed to by j and min are swapped.

##### Time Complexity

The selection sort performs the same number of comparisons as the bubble sort, which is n*(n-1)/2. However the number of swaps required is fewer when compared to bubble sort. But for larger values of n, the comparison time will dominate compared to swap time, so we should say that selection sort runs in O(n2) time like bubble sort.

##### Space Complexity

The space for section sort is O(1), because the above algorithm requires only a single additional memory space for temp variable.

### References: 