# 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(n ^{2})** to

**O(n)**. But the number of comparisons remains

**O(n**.

^{2})##### Selection Sort Java Example

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
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

1 2 3 4 5 |
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(n ^{2})** 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.

##### Recommended Posts

- Bubble Sort and Complexity Analysis
- Running time in Big O notation for Arrays Algorithms
- How to calculate binary Search time and space complexity

## Leave a Reply