Selection Sort(Java Implementation)

Selection sort is a simple sorting algorithm. It sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

Initially, the sorted part is empty and the unsorted part is the entire list.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

How Selection Sort Works?

arr[] = 66 24 16 20 17

// Find the minimum element in arr[0...4]
// and place it at beginning
16 24 66 20 17

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
16 17 66 20 24

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
16 17 20 66 24

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
16 17 20 24 66

 

Algorithm

• Step 1 − Set SMALL to location 0
• Step 2 − Search the minimum element in the list
• Step 3 − Swap with value at location SMALL
• Step 4 − Increment SMALL to point to next element
• Step 5 − Repeat until list is sorted

Let’s take a look at the implementation.

public class Sort {

public static void selectionSort(int arr[],int small,int pos) {

int temp;

    for(int i=0;i<=arr.length-2;i++)
    //set current element as minimum or small
    {

       small = arr[i];

       pos = i;

       for(int j=i+1;j<=arr.length-1;j++)
       {
       //check the element to be small
          if(arr[j]<small){

          small = arr[j];

          pos = j;

          }

        }
      //swap the minimum element with the current element
       temp=arr[i];

       arr[i]=arr[pos];

       arr[pos]=temp;

    }

}

public static void main(String[] strr) {

int small, pos;

int arr[] = {3, 2, 10, 17, 13, 9, 330, 42, 21, 90, 100};

small = arr[0];

pos = 0;

System.out.println(" Before sorting");

for(int j=0;j<=arr.length-1;j++)

{

System.out.print(" "+arr[j]);

}

selectionSort(arr,small,pos);

System.out.println("\nAfter Sorting");

for(int j=0;j<=arr.length-1;j++)

{

System.out.print(" "+arr[j]);

}

}

}

output:

Before sorting 3 2 10 17 13 9 330 42 21 90 100

After Sorting 2 3 9 10 13 17 21 42 90 100 330

Time Complexity:

The time complexity of selection sort is O(n²) as there are two nested loops. One loop is for comparisons and another loop is for swapping  between the elements.