Time ComplexityLesson 46Free preview

Selection Sort

This lesson is part of DSA · All levels

Summary

Sort selection always searches for the full minimum element in each round, so the complexity of the O(n^2) in all cases includes the data that has already been sorted. The exchange rate is at most n-1 times, saving memory writing. Its space complexity is constant because it runs in-place.

Key points

Complexity at best, average, and worst
The maximum number of exchanges is n times
The number of constant comparisons is n(n-1)/2 regardless of the order of the data
Space complexity O(1)

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.