Selection sort gif uses animations to explain selection sort, which repeatedly finds the minimum element from the unsorted part and puts it at the beginning.
Table of Content
What is selection sort?
Selection sort repeatedly finds the minimum element from the unsorted part and puts it at the beginning. The time complexity is O(n 2) time.
Selection sort gif
Selection sort code
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
Free download
Download Java, JavaScript and Python code
Algorithm types and algorithm examples