Selection Sort in Java

Selection Sort in Java

The selection sort is the improvement over bubble sort by making only one exchange for every pass through the list.

In this algorithm, find the smallest element from an unsorted list in each iteration and place that element at beginning of the list.

Or find the largest element from an unsorted list in each iteration and place that element at the end of the list.

How Selection Sort Works?

1.     Lets take and list as mentioned below and take the first element as minimum

20

12

10

15

2

2.     Compare first element with the second element is the second element is smaller than first then assign second element to minimum. Compare minimum with the third element and if the third element is smaller than minimum then assign thirst variable to minimum. The process goes on until the last element.

3.     After each iteration, minimum placed at the beginning of unsorted list by swapping.

4.     For each iteration, indexing start from the first unsorted element. Step 1 and 3 are repeated until all the elements are placed at their correct positions.

5.     And the selection is sort all the elements by using above steps in recursive method.

 // Selection sort in Java
import java.util.Scanner;
class SelectionSort {
  void selectionSort(int array[]) {
    int size = array.length;
    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;
      for (int i = step + 1; i < size; i++) {
        if (array[i] < array[min_idx]) {
          min_idx = i;
        }
      }
      int temp = array[step];
      array[step] = array[min_idx];
      array[min_idx] = temp;
    }
  }
  void printArray(int array[]) {
    int size = array.length;
    for (int i = 0; i < size; ++i)
      System.out.print(array[i] + " ");
    System.out.println();
  }
  public static void main(String args[]) {
    int[] data = { 20, 12, 10, 15, 2 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("Sorted Array in Ascending Order: ");
    ss.printArray(data);
  }
}

Complexity

Now lets talk about the complexity of selection sort.

Complexity = O(n2)

Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is O(n*n) = O(n²). So the complexity of this algorithm is O(n*n) = O(n2 ). This is the worst case complexity.

Where we can use bubble sort?

The selection sort is used when:

1.     small list is to be sorted

2.     cost of swapping does not matter

3.     checking of all the elements is compulsory

4.     cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)