- Finding smallest element from the array and.
- Replace the smallest element found to first position in array.
- Once the smallest element is found and placed at first position,
- Now task is to place 2nd smallest element in the second position.
- For finding the 2nd smallest element,
- We will repeat the same process and find smallest element but this time we will not include FIRST position in searching smallest number.
- Repeat the process until all elements are sorted.
public class SelectionSort {
public static void main(String[] args) {
new SelectionSort();
}
public SelectionSort() {
int[] arr = new int[] { 64, 2, 1, 22, 11 };
System.out.println("Before Sorting...");
printArray(arr);
selectionSort(arr);
System.out.println("\nAfter Sorting...");
printArray(arr);
}
// Iterate from 0 to n.
// While working for position 0, Search smallest element in array[0 to n]
// and put it at position 0.
// While working for position 1, Search smallest element in array[1 to n]
// and put it at position 1.
// While working for position 2, Search smallest element in array[2 to n]
// and put it at position 2.
// and so on.
private void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// variable to store index of smallest element and initially let
// smallest element be i.
int minimumTillNow = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minimumTillNow] > arr[j]) {
minimumTillNow = j;
}
}
// Checking if smallest initialized and found is same. if yes then
// there is no swapping done.
// So in that case no need to swap
if (minimumTillNow != i) { //
int temp = arr[minimumTillNow];
arr[minimumTillNow] = arr[i];
arr[i] = temp;
}
}
}
private void printArray(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
Complexity
- Selecting the lowest element requires scanning all n elements (this takes n – 1 comparisons) and then swapping it into the first position.
- Finding the next lowest element requires scanning the remaining n – 1 elements and so on,
- = (n – 1) + (n – 2) + … + 2 + 1 = n(n – 1) / 2
- = O(n^2) comparisons.
- Best Case : O(n)^2
- Worst Case : O(n)^2
- Average Case : O(n)^2
- Worst Case Space Complexity : O(1)
- Stable : No
Harshit Jain 