Selection Sort - Quiz

On each step the algorithm finds the minimum element in the unsorted part of the array and swaps it with the first element of that part. The process is then repeated for the remaining unsorted portion (excluding the already sorted elements). With each pass of the outer loop the boundary of the sorted part shifts one position to the right, and the smallest remaining values line up at the beginning of the array one after another. The algorithm works in place and needs no extra memory.

The time complexity is O(n²) in the best, average and worst cases. The outer loop runs n times and the inner loop runs on average n/2 times, and this number of comparisons does not depend on the input. Therefore even an already sorted array requires the complete set of comparisons — there is no early exit. Space complexity is O(1) because it sorts in place.

Selection sort performs the minimal number of swaps: at most n−1 exchanges over the whole run, that is O(n) swaps — one per pass of the outer loop. This pays off when a swap is expensive (for example, moving large objects), even though it still makes O(n²) comparisons. It also sorts in place and needs no extra memory.

In its basic array-based form, no — selection sort is not stable. Swapping the minimum element with the current one can change the relative order of equal values. If the order of equal elements matters, choose a stable algorithm such as insertion sort or merge sort.

Both are O(n²) and make the same number of comparisons, but they differ in the number of swaps. Bubble sort exchanges adjacent elements on every comparison, so it can perform up to O(n²) swaps. Selection sort finds the minimum in a single pass and does only one swap per pass — a total of O(n) exchanges, which is noticeably fewer.