The average case time complexity of the selection sort is $O(N^2)$.

The worst-case time complexity of selection sort, as well as the best-case time complexity of selection sort, comes out to be the same as the average case time complexity of selection sort i.e. $O(N^2)$.

Before getting into the details of how the time complexity of selection sort is determined, let us first get a brief introduction about the time complexity.

In simple terms, we can define time complexity as the amount of time taken to execute the set of instructions of a particular algorithm. But it is not the amount of time taken as the time depends on various other factors like compiler used, type of machine used, the type of processor, the speed of the processor, etc rather than just the set of instructions.

The time complexity can be said to the number of times the instructions set of an algorithm executes. So, the time complexity is defined in the terms of N where N is the function of input size(N).

The time complexity is divided into three categories :

1. Best Case Time Complexity :
   The best case time complexity is defined for the input that is taking the minimum time for execution.
2. Average Case Time Complexity :
   As the name suggests the average case time complexity is defined for all possible inputs as we calculate computing time for all of the inputs and then divide the result by the total number of inputs.
3. Worst Case Time Complexity :
   The worst-case time complexity is defined as the input that is taking the maximum time for execution.

There is another complexity in algorithm analysis $i.e.$ space complexity.

The space complexity is the total amount of space in the memory required by the particular algorithm. In simple terms, we can say that space complexity is the extra space required by the program in execution.

Now let us learn more about the time complexity of selection sort. The selection sort sorts the array by repeatedly finding the minimum value in the array of elements and then assigning it to the beginning of the array. So, the algorithm virtually maintains two sub-arrays in which the first array stores the element in sorted order and the other array contains the rest of the unsorted array.

In each iteration of the selection sort algorithm, we find the minimum values element for the unsorted part of the array and then move it to the sorted part. So we perform the basic swap from a certain position to the other position inside the array itself. Hence, the selection sort is an in-place sorting algorithm.

Let us see the pseudo-code of the selection sort so that we can easily understand and derive the time complexity of the selection sort.

Pseudo-code :

Refer to the next section for better visualization for example.

The time complexity of the selection sort depends upon the iteration and then finding the minimum element in each iteration. In each iteration, we find the minimum element from the sub-array and bring it to the right position using swapping.

The time complexity of finding the minimum element in a sub-array takes $O(N)$ time where N is the number of elements in the unsorted sub-array. As we will need to traverse the entire unsorted sub-array of size N for finding the minimum element so the time complexity of searching comes out to be $O(N)$. Now, after the searching, we will be performing the swapping (if needed) but the swapping is a constant time operation i.e. it takes only $O(1)$ time hence it will not affect the overall time complexity of the selection sort.

Now, for each of the Niterations, we perform the searching and swapping so the time complexity of the selection sort becomes $N*N$ i.e. $O(N^2)$. Let us look at the best, average, and worst-case time complexity of selection sort.

The best case is when the array is already sorted. So even if the array is already sorted, we will traverse the entire array for checking, and in each iteration or traversal, we will perform the searching operation. Only the swapping will not be performed as the elements will be at the correct position. Since the swapping only takes a constant amount of time i.e. $O(1)$the best time complexity of selection sort comes out to be $O(N^2)$.

The worst case is when the array is completely unsorted or sorted in descending order. So, we will traverse the entire array for checking, and in each iteration, we will perform the searching operation. After searching, we will swap the element at its correct position. As we know that the swapping only takes a constant amount of time i.e. $O(1)$ so the worst time complexity of selection sort also comes out to be $O(N^2)$.

The average case is when some part of the array is sorted. So, as we have seen earlier in the best and worst cases, we will need to perform the searching, and swapping in each iteration. So, the average time complexity of the selection sort is $O(N^2)$ as well.

Example of Time Complexity of Selection Sort

Now, let us take an example to understand the working of the selection sort better.

Refer to the image above for a clear understanding. We have taken as array i.e. a = [ 7, 5, 4, 2 ].

For the example, we will start by taking the min variable pointing to the last element of the array as it is the minimum element of the array. So, min will point to the last element i.e. a[3]. We also need another variable (let's say i) that will keep track of the correct position of the current min element. So, in the first step, the current element is larger than the min element. So, we will swap the current element with the min element. After swapping we will increment the position of i by 1.

We can see that virtually the array is divided into two parts the first being the sorted part and the other having the unsorted elements.

Now, in the second step, we will again find the minimum element from the unsorted array and make it point by the min variable. After finding the minimum element, we will check if it is greater than the current element (i.e. a[i]) or not. If it is greater then we will perform swapping and increment the i variable by one position.

This process of searching, swapping, and incrementing the pointer will continue until all the elements of the array become sorted.

C++ Code :

Java Code :

Python Code :

Output :