Time and Space Complexity

Временная сложность:

• Лучший, средний и худший случаи: O(n²)
  • Selection Sort всегда сканирует всю неотсортированную часть, чтобы найти минимум, даже если массив уже отсортирован. Количество сравнений не зависит от порядка входных данных.

Пространственная сложность:

• O(1)
  • Selection Sort является алгоритмом «на месте» (in-place). Он переставляет элементы, используя только константный объем дополнительной памяти, независимо от размера входных данных.

Итог:

• Selection Sort прост и эффективен с точки зрения использования памяти.
• Он выполняет мало перестановок (не более n-1), что полезно, когда операции записи стоят дорого.
• Его квадратичное время делает его плохим выбором для больших наборов данных, где предпочтительнее такие алгоритмы, как Merge Sort или Quick Sort.