How to implement Selection Sort in java
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It is a combination of searching and sorting. During each pass, the unsorted smallest (or largest) value is moved to its proper position in the array. In the selection sort, the inner loop finds the next smallest (or largest) value and the outer loop places that value into its proper location. The total number of iterations are one less than total number of elements in the array.
Performance of Selection Sort
Worst case performance : О(n2)
Best case performance : O(n2)
Average case performance : О(n2)
Understand Selection Sort with an example.
Let us see how this can be implemented in Java.
|
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 |
package com.code2succeed.sorting; import java.util.Arrays; public class SelectionSortExample { public static void main(String[] args) { int [] a = {10, 5, 87, 32, 14, 22}; System.out.println("Array Before Sorting : "); print(a); selectionSort(a); System.out.println("Array After Sorting : "); print(a); } public static void selectionSort(int [] a){ int length = a.length; for (int i = 0; i < length - 1; i++) { int index = i; for (int j = i + 1; j < length; j++) if (a[j] < a[index]) index = j; int smallerNumber = a[index]; a[index] = a[i]; a[i] = smallerNumber; printArray(a, i); } } public static void print(int [] a) { System.out.println(Arrays.toString(a)); } public static void printArray(int [] a, int index) { int iterationCount = index+1; System.out.println("Array after iteration "+iterationCount); print(a); } } |
Output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Array Before Sorting : [10, 5, 87, 32, 14, 22] Array after iteration 1 [5, 10, 87, 32, 14, 22] Array after iteration 2 [5, 10, 87, 32, 14, 22] Array after iteration 3 [5, 10, 14, 32, 87, 22] Array after iteration 4 [5, 10, 14, 22, 87, 32] Array after iteration 5 [5, 10, 14, 22, 32, 87] Array After Sorting : [5, 10, 14, 22, 32, 87] |