Selection Sort In Java
June 22, 2017
Categorised in: Java Codes
- 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
*/
Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.