Selection sort repeatedly finds the minimum element from unsorted part and puts it at the beginning. O(n 2) average and worst. The selection sort minimizes the number of swaps, but the number of comparison is still high. For data that is already sorted or almost sorted, the insertion sort does better.
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 39 40 41 42 43 44 45 46 47 48 49 |
import java.util.Arrays; public class SelectionSort { //Solution1: iterative, Time O(n^2), Space O(1), n is array length public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n-1; i++) { int min = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[min]) min = j; } swap(arr, i, min); } } //Swap two elements by index, Time O(1), Space O(1) private static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } //Solution 2: Recursive, Time O(n^2), Space O(n) public static void selectionSortRec(int[] a, int i, int n){ int min = i; for (int j = i + 1; j < n; j++){ if (a[j] < a[min]) { min = j; } } swap(a, i, min); if (i + 1 < n) { selectionSortRec(a, i+1, n); } } public static void main(String[] args) { int[] a = {19, 33, 4 , 61, 5, 38, -36, 21, 0}; selectionSort(a); System.out.println("Selection sort(iteration): " + Arrays.toString(a)); //recursive int[] b = {19, 33, 4 , 61, 5, 38, -36, 21, 0}; selectionSortRec(b, 0, b.length); System.out.println("Selection sort(recursion):"+ Arrays.toString(b)); } } |
Javascript
|
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 |
//Solutions 1: Iterative, Time O(n^2), Space O(1), n is array length function selectionSort(arr) { var n = arr.length; for (let i = 0; i < n-1; i++) { let min = i; for (let j = i+1; j < n; j++) { if (arr[j] < arr[min]) min = j; } swap(arr, i, min); } } //Swap two elements by index, Time O(1), Space O(1) function swap(arr, i, j) { var tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } //Solution 2: Recursive, Time O(n^2), Space O(n) function selectionSortRec(a, i, n){ var min = i; for (let j = i + 1; j < n; j++){ if (a[j] < a[min]) { min = j; } } swap(a, i, min); if (i + 1 < n) { selectionSortRec(a, i+1, n); } } let a = [19, 33, 4 , 61, 5, 38, -36, 21, 0]; selectionSort(a); console.log("Selection sort(iteration): " + a); let b = [19, 33, 4 , 61, 5, 38, -36, 21, 0]; selectionSortRec(b, 0, b.length); console.log("Selection sort(recursion): " + b); |
Python
|
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 |
#Solution 1: Iterative, Time O(n^2), Space O(1), n is array length def selectionSort(arr) : n = len(arr) for i in range(0, n-1) : min = i for j in range (i+1, n): if arr[j] < arr[min]: min = j swap(arr, i, min) #Swap two elements by index, Time O(1), Space O(1) def swap(arr, i, j) : tmp = arr[i] arr[i] = arr[j] arr[j] = tmp # Solution 2: Recursive, Time O(n^2), Space O(n) def selectionSortRec(a, i, n): min = i for j in range(i + 1, n): if a[j] < a[min]: min = j; swap(a, i, min) if i + 1 < n: selectionSortRec(a, i+1, n) array = [19, 33, 4 , 61, 5, 38, -36, 21, 0] selectionSort(array) print("Selection sort (iteration): ") print(array) b = [19, 33, 4 , 61, 5, 38, -36, 21, 0] selectionSortRec(b, 0 , len(b)) print("Selection sort (recursion): ") print(b) |
Doodle
Download Java, JavaScript and Python code
Selection sort doodle