Summary

Selection Sort is an in-place comparison-based algorithm that divides the input list into two parts: a sorted sublist that is built up from left to right, and a sublist of the remaining unsorted items. The algorithm proceeds by finding the smallest element in the unsorted sublist, swapping it with the leftmost unsorted element, and moving the sublist boundary one element to the right.

How it Works

• Start with the first element (index i = 0). This marks the beginning of the unsorted portion.

• Assume the first element of the unsorted portion (arr[i]) is the minimum.

• Iterate through the rest of the unsorted portion (from i+1 to the end) to find the true minimum element.

• In each comparison, if a smaller element is found, update the index of the minimum.

• After scanning the entire unsorted portion, if the true minimum is not at index i, swap it with the element at arr[i].

• The element at index i is now sorted. Increment i to move the sorted sublist boundary to the right.

• Repeat this process until the entire array is sorted.