Selection Sort Algorithm:

In selection sort, the smallest value among the unsorted elements of the array is selected in every
pass and inserted to its appropriate position into the array. It is also the simplest algorithm. It is
an in-place comparison sorting algorithm. In this algorithm, the array is divided into two parts,
first is sorted part, and another one is the unsorted part. Initially, the sorted part of the array is
empty, and unsorted part is the given array. Sorted part is placed at the left, while the unsorted
part is placed at the right.

In selection sort, the first smallest element is selected from the unsorted array and placed at the
first position. After that second smallest element is selected and placed in the second position.
The process continues until the array is entirely sorted.

The average and worst-case complexity of selection sort is O(n2), where n is the number of
items. Due to this, it is not suitable for large data sets.

Selection sort is generally used when -

o A small array is to be sorted

o Swapping cost doesn't matter
o It is compulsory to check all elements

Working of Selection sort Algorithm

Now, let's see the working of the Selection sort Algorithm.

To understand the working of the Selection sort algorithm, let's take an unsorted array. It will be
easier to understand the Selection sort via an example.

Let the elements of array are -

We'll begin with the entire array. Next, we'll identify the smallest element in the unsorted part,
which is currently the entire array. In this case, the smallest element is 8.

We'll then swap the smallest element (8) with the first element (12). The array now looks like
this:
Now, let's look at the subarray starting from index 1 (since the first element is already sorted).
The smallest element in this subarray is 12. Swap this smallest element (12) with the second
element (29).

Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in the
sorted array. So, after two iterations, the two smallest values are placed at the beginning in a
sorted way.

Consider the sub array starting from index 2 (since the first two elements are already sorted).
Identify the smallest element in this sub array, which is 17. Swap this smallest element (17) with
the third element (25) . The sub array starting from index 3 is considered. The smallest element
in this sub array is found to be 25. This smallest element is swapped with the fourth element,
which is 29. Then, the sub array starting from index 4 is considered. The smallest element in this
sub array is found to be 29. This smallest element is swapped with the fifth element, which is 32.
Finally, the sub array starting from index 5 is considered. The smallest element in this sub array
is found to be 32. This smallest element is swapped with the sixth element, which is 40 (no
change ).

Now, the array is completely sorted.

 Selection sort complexity

Now, let's see the time complexity of selection sort in best case, average case, and in worst case.
We will also see the space complexity of the selection sort.

Case Time Complexity

Best Case O(n2)

Average Case O(n2)

Worst Case O(n2)

1. Time Complexity

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is
already sorted. The best-case time complexity of selection sort is O(n2).
o Average Case Complexity - It occurs when the array elements are in jumbled order that
is not properly ascending and not properly descending. The average case time complexity
of selection sort is O(n2).
o Worst Case Complexity - It occurs when the array elements are required to be sorted in
reverse order. That means suppose you have to sort the array elements in ascending order,
but its elements are in descending order. The worst-case time complexity of selection sort
is O(n2).

2. Space Complexity

Space Complexity O(1)

Stable YES

o The space complexity of selection sort is O(1). It is because, in selection sort, an extra
variable is required for swapping.
Algorithm
SELECTION SORT(arr, n)

Step 1: Repeat Steps 2 and 3 for i = 0 to n-1

Step 2: CALL SMALLEST(arr, i, n, pos)
Step 3: SWAP arr[i] with arr[pos]
[END OF LOOP]
Step 4: EXIT

SMALLEST (arr, i, n, pos)

Step 1: [INITIALIZE] SET SMALL = arr[i]
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
SET SMALL = arr[j]
SET pos = j
[END OF if]
[END OF LOOP]
Step 4: RETURN pos

Implementation of selection sort:

Program: Write a program to implement selection sort in C language.

#include <stdio.h>

void selection(int arr[], int n)

{
int i, j, small;

for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
small = i; //minimum element in unsorted array

for (j = i+1; j < n; j++)

if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */

{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
</stdio.h>

Output:

After the execution of above code, the output will be -