Analysis of Selection Sort Time Complexity.

Analysis of Selection Sort Time Complexity. Selection sort worst case, best case and average case time complexity is O(n^2). Selection Sort Java Program.

Selection sort Time Complexity Analysis

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

Let's start with Selection sort Java program, How Selection sort works in java, Selection sort Algorithm in java.

Sort an array of integers using Selection sort in Java.
Lets understand what is the input and the expected output.

Overview

Selection Sort is very basic and easy sorting algorithm to understand and implement.

Selection sort works by,
1. Finding smallest element from the array and. 2. 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.

Selection Sort Java Program

package javabypatel;

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] + " ");
  }
 }
 
}

Why is Selection sort faster than Bubble sort?

When using Selecting sort it swaps elements "n" times in worst case, but Bubble sort swaps almost n*(n-1) times.

We all know, Reading time is less than writing time even in-memory.
(Compare and running time can be ignored)

If we have a system where write operations are extremely expensive and read operations are not, then Selection sort could be ideal.
Selection sort is good for sorting arrays of small size.

Selection sort is better than Bubble sort due to less swapping required.

Note:
In Bubble sort, we can identify whether list is sorted or not in 1st iteration but in Selection sort we can't able to identify that.
Compared to Selection sort, Bubble sort should be used when the given array is almost sorted.