Кормен "Алгоритмы": найти время работы алгоритма сортировки выборкой

Рейтинг: 1Ответов: 1Опубликовано: 02.12.2014

Тут есть такая задача - найти время работы алгоритма сортировки выборкой. И тут возникает вопрос, какие средства доступны юзеру при написании сего алгоритма, ведь если имеется возможность использовать списки, время будет O(n), ибо мы можем, не проводя нудную операцию сдвига всего массива на один элемент, вставить в начало, а если нет - O(n^2)?

алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Вы что-то путаете явно. Сортировка выбором не сдвигает элементы массива, она их меняет местами.

2 4 7 3 5 1 - исходный массив
1 4 7 3 5 2 - 1 минимальный, меняем 1 и 2
1 2 7 3 5 4 - 2 минимальный, меняем 2 и 4
1 2 3 7 5 4
1 2 3 4 7 5
1 2 3 4 5 7

Независимо от структуры данных операций сравнения будет O(n^2)