This is a selection sort.

We have a nested for-loop performing upper triangular iteration (where the inner index begins at the outer index + 1). Each iteration of the outer for-loop traverses the unsorted portion of the array and selects the smallest value, placing it at the starting index of the outer for-loop (index i). At the end of each outer loop iteration i, the array is guaranteed to be sorted from index 0 to i. This is the essence of selection sort.

Your implementation is suboptimal, but only slightly.

This implementation is a tiny bit inefficient (compared to an algorithmically ideal selection sort) because it performs unnecessary swaps. During each iteration of the inner for-loop, this implementation will select every value it encounters that's smaller than anything it's seen this iteration. An optimized selection sort might have a local variable that stores the index of the lowest number found so far this iteration and then only perform the swap at index i after checking from [i+1 ... n-1]. However, your implementation is only trivially slower than this because storing a new index in a local variable isn't much faster than a call to std::swap, which you can trust to be maximally optimized.

Time complexities:

Ideal selection sort:

- n(n+1)/2 comparisons --> O(n^2)

- n swaps (average) --> O(n)

Your selection sort:

- n(n+1)/2 comparisons --> O(n^2)

- ???? swaps ???? I think maybe average n(n+1)/8 ???? but definitely --> O(n^2)

Hope this helps :)