Selection sort

Selection sort is designed to make the fewest swaps possible. For a vector of n elements selection sort will make n swaps. Here鈥檚 how it works:

1. scan the unsorted portion of the vector and select the smallest element
2. swap that element with the leftmost unsorted element
3. repeat until there are no more unsorted elements

Selection sort has time complexity of \mathcal{O}(n^2) and space complexity of \mathcal{O}(1).

In this video, we implement selection sort in C++.

Additional resources:

• Selection Sort.pdf
• selectionSort.cpp

Comprehension check:

1. Writing to a memory location takes more time than _______________ from a memory location.
2. True or false? Selection sort is not stable.
3. Given a vector of n elements, selection sort will make _____________ swaps to completely sort the vector.
4. If we have a vector of 10 elements, and three elements are sorted, selection sort will perform _______ comparisons in order to sort the next element.
5. True or false? Given the vector 0, 3, 4, 7, 1, 2, after the first iteration, the vector will be [0, 1, 4, 7, 3, 2.]

[Answers: 菨n晒蕠 / 9 / u / 菨n晒蕠 / 苾u岽塸蓯菨晒]

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.