Selection Sort

Selection Sort

---

Given a array of integers, Sort it.
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. 

Java Program for Selection Sort

---

package javabypatel.sorting;

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

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. 

 

You may also like to see

---

Merge Sort

Heap Sort

Bubble Sort

Insertion Sort

Quick Sort

---

Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space. 

Count number of Bits to be flipped to convert A to B 

Count number of Set Bits in Integer. 

Check if number is Power of Two. 

Find all subsets of a set (Power Set).

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.