Selection Sort In Java
- 0,1,…, n-1 index numbers are exchanged with smallest number from index numbers: 1,2,…,n
- Best Case Time Complexity: O(n^2)
- Worst Case Time Complexity: O(n^2)
- Space Complexity: O(1)
- Stable
public class SelectionSortInJava { public static void SelectionSort(int[] arr){ for (int i = 0; i < arr.length - 1; i++) // excludes last element { int index = i; for (int j = i + 1; j < arr.length; j++){ // excludes first element if (arr[j] < arr[index]){ // find index of element smaller than key && smallest in the group of numbers to the right of key index = j; // searching for lowest index } } int smallNumber = arr[index]; // temporary variable to store smallest number arr[index] = arr[i]; // put key in place of smallest number arr[i] = smallNumber; // smallest number starts from index 0 which is why i = 0 in for loop } } public static void main(String[] args){ int[] arr = {2,13,2,1,42,10,57,21}; System.out.println("Unsorted:"); for(int i:arr){ System.out.print(i+" "); } System.out.println(); SelectionSort(arr); System.out.println("Sorted:"); for(int i:arr){ System.out.print(i+" "); } } } /* OUTPUT: Unsorted: 2 13 2 1 42 10 57 21 Sorted: 1 2 2 10 13 21 42 57 */ Selection Sort Analysis
public class SelectionSortAnalysis { public static void SelectionSort(int[] arr){ for (int i = 0; i < arr.length - 1; i++) // excludes last element { int index = i; System.out.println(); System.out.println("---{ " + arr[index] +" }---"); System.out.println(); for (int j = i + 1; j < arr.length; j++){ // excludes first element if (arr[j] < arr[index]){ // find index of element smaller than key && smallest in the group of numbers to the right of key System.out.println(arr[j] + " < " + arr[index] + " : YES"); index = j; // searching for lowest index } } int smallNumber = arr[index]; // temporary variable to store smallest number arr[index] = arr[i]; // put key in place of smallest number arr[i] = smallNumber; // smallest number starts from index 0 which is why i = 0 in for loop System.out.println("PASS "+ (i+1) + " : "); for(int x:arr){ System.out.print(x+" "); } } } public static void main(String[] args){ int[] arr = {2,13,2,1,42,10,57,21}; System.out.println("------------"); System.out.println("Unsorted:"); System.out.println("------------"); for(int i:arr){ System.out.print(i+" "); } System.out.println(); SelectionSort(arr); System.out.println(); System.out.println("------------"); System.out.println("Sorted:"); System.out.println("------------"); for(int i:arr){ System.out.print(i+" "); } } } /* ------------ Unsorted: ------------ 2 13 2 1 42 10 57 21 ---{ 2 }--- 1 < 2 : YES PASS 1 : 1 13 2 2 42 10 57 21 ---{ 13 }--- 2 < 13 : YES PASS 2 : 1 2 13 2 42 10 57 21 ---{ 13 }--- 2 < 13 : YES PASS 3 : 1 2 2 13 42 10 57 21 ---{ 13 }--- 10 < 13 : YES PASS 4 : 1 2 2 10 42 13 57 21 ---{ 42 }--- 13 < 42 : YES PASS 5 : 1 2 2 10 13 42 57 21 ---{ 42 }--- 21 < 42 : YES PASS 6 : 1 2 2 10 13 21 57 42 ---{ 57 }--- 42 < 57 : YES PASS 7 : 1 2 2 10 13 21 42 57 ------------ Sorted: ------------ 1 2 2 10 13 21 42 57 */