Selection Sorting


Selection sorting is considered to be the simplest sorting and also has a simple algorithm. The algorithm of selection sorting finds the smallest element in the array and places it at the first position of the array.

Then it finds the next smallest element in the array and places it at the second position of the array. This process is continued until the whole array is sorted. In short we can say that the main idea of selection sorting contains the following steps:

  1. Finding the smallest element of the array
  2. Putting the smallest element at first position of the array or at index 0
  3. Finding the next smallest element in the array
  4. Putting the next smallest element at second position of the array or at index 1
  5. So one, until the entire array is sorted


How selection sorting works:

Consider the following figures and you will able to comprehend the main idea of selection sorting algorithm:

19 5 7 12

The above array has four elements in it and we want to sort this array in ascending order, then selection sorting is applied. The smallest element in the array is 5 and it is at the index 1. This element is selected and is placed at index 0 that is the first location of the array. Consider the following figure:

5 19 7 12

Now the element 7 is selected and is placed at the second position of the array that is at index 1. Consider the following figure:

5 7 19 12

Then we select the last element of the array that is 12 and it is placed at index 2 or at position 3 of the array and automatically the element 9 is placed at the last position of the array that is at index 3. In this way we have a sorted array of elements. Consider the following figure:

5 7 12 19


Sorting using Selection Sort Algorithm:

The following is the algorithm of Selection sorting:

ALGORITHM:

void selectionsorting (int arr [], int len) {

int x, y, minimum, temp;

for (x = 0; x < len – 1; x ++)

{

minimum = x;

for (y = x + 1; y < len; y ++)

{

if (arr [y] < arr [minimum])

{

minimum = y;

}

}

temp = arr [x];

arr [x] = arr [minimum];

arr [minimum] = temp;

}

}

In the above algorithm, a method void selectionsorting () is defined in which we have passed the array to be sorted and its length that is the size of the array. Then we declared two counter variables x and y that will be used in the array. The first loop initializes x at 0 and is terminated when x becomes equal to (len – 1). In the loop we set the variable “minimum” to the counter variable x.

Then in the “if condition” we checked that if the element of the array at location y is less than the element at minimum position then it will set the variable minimum as the counter variable y. After the “if condition” swapping is done which exchanges the smallest elements to the elements at earlier positions of the array.


Complexity of Analysis of Selection Sorting:

The following are the cases for time complexity of selection sorting:

Worst case Time Complexity:

The worst case time complexity is o (n ^ 2)

Best case Time Complexity:

The best case time complexity is o (n ^ 2)

Average Time Complexity:

The average case time complexity is o (n ^ 2)

Space Complexity:

The space complexity is o (1)