Sorting 101: Selection Sort

Inplace Algorithm: Algorithm which does not need extra space.

Stable Algorithm: preserves the order of records for equal value records.

Selection Sort:

The idea is to loop through the array and swap each index with the minimum of the rest of the array.

For eg: for array

int arr[] = new int[]{5,4,3,2,1};

 

for(int i = 0; i<arr.length; i++){//Loop 1

 int startIndex = i+1;

 int minIndex = findMin(startIndex, arr);

 swap(i, minIndex, arr);

}

 

private int findMin(int startIndex, arr){

 int min = arr[startIndex];

 int minIndex = startIndex'

 for(int j = startIndex, j<arr.length; j++){//Loop 2

  if(arr[j]<min){

  min = arr[j];

  minIndex = j;

  }

 } return minIndex;

}

In the above code, let’s check the value of arr after every iteration in loop 1

Example 1:

arr = 5,4,3,2,1

i = 0, arr = 1,4,3,2,5

i = 1, arr = 1,2,3,4,5

i = 2, arr = 1,2,3,4,5

i = 3, arr = 1,2,3,4,5

i = 4, arr = 1,2,3,4,5

i = 5

Example 2:

arr = 4, 5, 5, 2, 3

i = 0, arr = 2, 5, 5, 4, 3

i = 1, arr = 2, 3, 5, 4, 5

i = 2, arr = 2, 3, 4, 5, 5

i = 3, arr = 2, 3, 4, 5, 5

i = 4, arr = 2, 3, 4, 5, 5

Example 3:

eg: 3

for arr = 1, 1, 2, 3, 4

i = 0, arr = 1, 1, 2, 3, 4

i = 1, arr = 1, 1, 2, 3, 4

i = 2, arr = 1, 1, 2, 3, 4

i = 3, arr = 1, 1, 2, 3, 4

i = 4, arr = 1, 1, 2, 3, 4

In example 3, even though the input was 1, 1, 2, 3, 4, the output came out to be 1, 1, 2, 3, 4

Here the red 1 got replaced by green 1 which means the input is not being returned as is, hence this is unstable algorithm.

Also, since no extra space is being used so it is inplace algorithm