Selection Sort: Check & Understand Details With Java Examples

Suppose you are a company owner and want to give your employees a bonus on the new year. Here, you have already sorted data of the employee’s salary; then you can use it and add the increment value as per the positions of the employees. How is the selection sort algorithm used here?

Well, the employee’s salary data is already sorted (salaries divided as per the position). That is why they just have to compare the salary, find out the smallest value, place it at suitable positions, and add the incremental amount. 

Find it confusing?

Let’s understand more details about the selection sort in the upcoming paragraphs. But before that, let’s know what the selection sorting algorithm is.

What is the selection sort algorithm?

This is one of the sorting algorithms in which the smallest element of an unsorted array gets selected and lists it in a single iteration. And then place it at the starting of the unsorted list. This process continues until the array or list does not get sorted.

The selection sort algorithm has two subarrays within the particular array.

• The already subarray.
• The remaining and unsorted subarray.

Finally, the minimum or the smaller element from the unsorted subarray will be selected and moved forward to the sorted subarrays in each selection sort iteration.

How does selection sort work?

Here, I will define the process of how the selection sort works.

1. Set the first element of the list or array as the minimum.

2. Compare the minimum number with the adjacent or second element. If the number is found smaller than the selected smaller number, then assign the element set to minimum.

Compare the minimum element with the next (that is, third) element. If it is smaller, then assign the third to the smallest number; otherwise, do nothing. This process will continue till the last element of the array.

3. Once the iteration is completed, the minimum places in the unsorted list’s front.

4. Here, you need to keep in mind that the indexing of the unsorted element will start from the beginning. And step 1 to 3 will repeat till the elements place at the correct position.

Selection sort algorithm with flow chart

selectionSort(arr, size)

  repeat (size – 1) times

  setting the first unsorted item or element as minimum

  for every unsorted element

    if element < currentMinimum

      set it (element) as new minimum

  swap minimum element with first unsorted index position

end selectionSort

Let’s take an example of selection sort in Java

For your convenience, we have explained select sort with the help of Java programming

// Selection sort in Java

import java.util.Arrays;

class SelectionSort {
  void selectionSort(int arr[]) {
    int size = arr.length;

    for (int step = 0; step < size - 1; step++) {
      int min_idx = step;

      for (int i = step + 1; i < size; i++) {

        // For sorting the elements in descending order, 
       // modify > to <.
        // Choose the minimum element from 
       // the array in each loop.
        if (arr[i] < arr[min_idx]) {
          min_idx = i;
        }
      }

      // putting minimum at the correct position
      int temp = arr[step];
      arr[step] = arr[min_idx];
      arr[min_idx] = temp;
    }
  }

  // driver code
  public static void main(String args[]) {
    int[] data = { 30, 22, 20, 25, 12 };
    SelectionSort ss = new SelectionSort();
    ss.selectionSort(data);
    System.out.println("The Sorted Array: ");
    System.out.println(Arrays.toString(data));
  }
}

Output:

The Sorted Array: [12, 20, 22, 25, 30]

What about the complexity of the selection sort algorithm?

Below, we have mentioned the table that defines the different complexity factors, such as the time complexity of selection sort.

Time complexity:

Stability:

No

Space Complexity

O(1)

What are the applications of selection sort?

The selection sort is useful in the cases:

• when the swapping cost does not matter
• writing cost to the memory matters such as flash memory (number of swaps/writes O(n) in comparison to O (n^2) of the bubble sort)
• the smaller list need to be sort
• checking the elements of a list or array is compulsory

Conclusion

Selection Sort is a too easy algorithm to appear in your next coding interview with Microsoft or Google. You just need to know some of the key points about selection sort.

These are as follows:

• Starting with the first element, choose one element from the array.
• Sequentially compare it to all other entries in the array.
• Swap their locations if an element discovers to be smaller than the presently chosen element.

Before going on to the next member in the array, make sure you find the right place for the selected element. 

Apart from this, I want to recommend you to please solve each sorting iteration on paper if you truly want to learn sorting algorithms. Only attempt to code it and validate each stage of your paper answer once you have solved it successfully on paper.

Frequently Asked Questions