Question

Ответьте пожалуйста на вопрос Сколько проходов с перестановками элементов потребуется для сортировки массива из 100 чисел отдам 10 баллов.........................................

Answer 1

Зависит от алгоритма сортировки.

Если брать популярную в школьной программе "пузырьковую" сортировку, то для сортировки n элементов в худшем случае потребуется пробежаться по массиву n^2 раз. То есть для 100 элементов потребуется 10000 раз пробежаться по массиву. Это называется временной сложностью алгоритма. Для "пузырьковой сортировки она O(n^2)

Надо сказать, что это один из самых медленных алгоритмов сортировки. Хуже только "глупая сортировка". А есть, например, алгоритм "быстрой сортировки". Его временная сложность O(2*n), что гораздо быстрее "пузырьковой".

Суть её заключается в том, что мы выбираем какой-то элемент и пересортировываем элементы так, что перед выбранным элементом все элементы меньше выбранного, а после – большие или равные. Тем самым мы ставим этот элемент на "своё место". Две оставшиеся части сортируем тем же способом по-отдельности.

Ответ: 10000 раз.

Answer 2

Для сортировки массива из 100 чисел существует различные методы сортировки, каждый из которых имеет свою сложность. Если вы имеете в виду метод сортировки перестановками (также известный как метод "пузырька"), то я могу пояснить, что в худшем случае этот метод потребует $n \times (n-1) / 2$ перестановок, где $n$ - количество элементов в массиве.

Для массива из 100 чисел это будет:

$100 \times (100 - 1) / 2 = 4950$

Таким образом, для сортировки массива из 100 чисел методом перестановок потребуется 4950 перестановок.