Selection Sort Program in Java

In this post we’ll see how to write Selection sort program in Java. Selection sort is considered a step ahead of bubble sort as the number of swaps is lesser though the comparison are still proportional to N².

How selection sort works

In selection sort aim is to bring the lowest element to the 0th index in the first pass. In the next iteration the second lowest to the 1st index and so on.

You start with the element at the 0th index and consider it the lowest. Then compare it with the other elements, if any element is smaller than the first element then that element becomes the lowest for further comparisons in that pass. That way you have the lowest element at the end of the iteration it is then swapped with the element at the 0th index.

Same way in the next iteration you start with the element at the 1st index and consider it the second lowest element. Then compare it with all the elements on its right, in between if any element smaller than this element is found then further comparisons are done using the now smallest element.

For example if you have an array [5, 2, 6, 1] then in the first iteration-

Initially you will start with 5 (element at 0th index) and compare it with elements on its right. Since 2 is smaller than 5 so now 2 is considered the lowest.
Then 2 is compared with 6. Still 2 is the lowest.
Then 2 is compared with 1, since 1 is smaller so it is now the lowest element and the end of the array is also reached. Swap 1 with 5 so after the first iteration array is [1, 2, 6, 5].

In the next iteration you will start with 2 (element at the 1st index) and compare it with elements on its right using the same logic for sorting.

Selection Sort Java program

Logic for writing the selection sort Java program is as follows-

There are two for loops, the outer loop starts from the leftmost element and goes till the one less than the number of elements in the array.

The inner loop starts at the index one more than the current index of the outer loop and goes till the end of the array.

With in the inner loop elements are compared with the element currently pointed by the outer loop to get the lowest element with in that iteration. Once the element is found it is swapped with the element at the current index of the outer loop.

public class SelectionSort {
  public static void main(String[] args) {
    int[] numArray = {47, 85, 620, 3456, 7, 10, 4500, 106, 345, 1000};
    int[] sortedArray = selectionSort(numArray);
    System.out.println("Sorted array is- ");
    for(int num : sortedArray){
      System.out.print(num + " ");
    }
  }
  private static int[] selectionSort(int[] numArray){
    int lowest;
    for(int i = 0; i < numArray.length - 1; i++){
      lowest = i;
      for(int j = i+1; j < numArray.length; j++){
        //if smaller then this is considered the smallest
        if(numArray[j] < numArray[lowest]){
          lowest = j;
        }
      }
      swapElements(i, lowest, numArray);
    }
    return numArray;
  }
    
  private static void swapElements(int index, int lowest, int[] numArray){
    int temp = numArray[index];
    numArray[index] = numArray[lowest];
    numArray[lowest] = temp;
    // Uncomment it to see the element movement in each iteration    
    /*for(int num : numArray){
      System.out.print(num + " ");
    }
    System.out.println("");*/
  }
}

Output

Sorted array is- 
7 10 47 85 106 345 620 1000 3456 4500

Time and space complexity of Selection sort

For selection sort there are two loops that go through the elements that makes it a complexity of N*N i.e. time complexity of Selection sort is O(N²) where total number of comparisons are N*(N-1)/2.

In selection sort the number of swaps are less in comparison to the bubble sort making it faster than the bubble sort.

Selection sort is an in place sorting algorithm so apart from the initial array there is no auxiliary space requirement thus the space complexity of Selection sort is O(1), total space can be considered as O(N).

That's all for this topic Selection Sort Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Thursday, January 13, 2022