Selection Sort Java Program

This post shows how to write Selection sort program in Java.

Selection sort is also an in place sorting algorithm like Bubble sort that works by comparing and swapping elements in each pass.

Selection sort algorithm

Selection sort works as follows-

  1. Start with the left most element (index 0) and compare it with the elements on the right side to see if there is any element smaller than that element. If yes then this new element becomes the lowest element for further comparisons in that iteration.
  2. By the end of the iteration you get the index of the lowest element.
  3. Swap the lowest element with the leftmost element. So, by the end of the first pass you have the lowest element at its proper place.
  4. In the next pass start with index 1 and again follow the same process.

For example if array is {5, 4, 7, 1, 8} then start with element at index 0 and compare it with adjacent element.

Selection sort Java

 

After first pass you have the index of the lowest element which is then swapped with the element at index 0. That ends the first pass.

In the second pass start with the 4 (element at index 1) and again compare the elements.

Selection sort Java Program

public class SelectionSort {
  public static void main(String[] args) {
    int[] arr = {25, 34, 10, 7, 15, 92, 53, 72, 39, 45};
    System.out.println("Original array- " + Arrays.toString(arr));
    int[] sortedArray = selectionSort(arr);
    System.out.println("Sorted array- " + Arrays.toString(sortedArray));
  }
	
  private static int[] selectionSort(int[] arr){
    int index;
    for(int i = 0; i < arr.length - 1; i++){
      index = i;
      for(int j = i+1; j < arr.length; j++){
        //if lower than the current lowest assign this index
        if(arr[j] < arr[index]){
          index = j;
        }
      }
      // swap so that smallest element in this pass
      // is at its proper place
      swapElements(i, index, arr);
    }
    return arr;
  }
    
  private static void swapElements(int index, int lowest, int[] arr){
    int temp = arr[index];
    arr[index] = arr[lowest];
    arr[lowest] = temp;
  }
}

Output

Original array- [25, 34, 10, 7, 15, 92, 53, 72, 39, 45]
Sorted array- [7, 10, 15, 25, 34, 39, 45, 53, 72, 92]

Selection sort space and time complexity

Time complexity of selection sort is O(N2) which is same as the time complexity of bubble sort but the number of swaps required are comparatively lesser in Selection sort than Bubble sort.

No extra space is required so the space complexity of Selection sort is O(1).

Related Posts

That’s all for the topic Selection Sort Java Program. If something is missing or you have something to share about the topic please write a comment.


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.