**Selection sort** is an in-place sorting algorithm that works on the notion of finding the minimum element(if sorting in ascending order) or maximum element(if sorting in descending order) in the unsorted array and placing it in its correct position.

It divides the entire unsorted array into two subarrays: sorted and unsorted. In every iteration, it picks the minimum/maximum element from the unsorted subarray and places it in the sorted subarray. Hence it runs n times.

##### Let’s understand how selection sort works

- Start from the first element and search for the smallest element in the entire array.
- Replace the minimum element with the first element of the array.
- Repeat steps 1 and 2 for each element until the entire array is no sorted.

### Algorithm

Following is the algorithm for selection sort.

```
selection_sort( arr ){
for i in range 0 to (n-1){
min = i;
for j in range (i+1) to (n-1){
if(arr[j] < arr[min])
min = j;
}
swap(arr[i],arr[j]);
}
return arr;
}
```

### Implementation in CPP

### Time Complexity

The time complexity of the above algorithm in the worst case is **O(N²)**, and **O(N)** in the best case i.e, when the entire array will be sorted.

**Remember:**

1. Best case time complexity = **O(N)**

2. Worst-case time complexity = **O(N²)**

3. Auxiliary space requirement =** O(1)**

4. The total number of swaps done = **O(N)**.

Did, we miss something, or do you want to add some other key points?

Please comment.