1. На какой идее основан метод пузырька? Метод выбора?
Метод пузырька основан на последовательном сравнении соседних элементов и их обмене, если они находятся в неправильном порядке. Метод выбора основан на нахождении минимального (или максимального) элемента в оставшейся неотсортированной части массива и его перемещении на нужную позицию.
2. Объясните, зачем нужен вложенный цикл в описанных методах сортировки.
Вложенный цикл необходим для последовательного сравнения элементов в массиве. В сортировке пузырьком внутренний цикл отвечает за продвижение наибольшего элемента в конец неотсортированной части, а во время сортировки выбором – за поиск минимального элемента.
3. Сравните метод пузырька и метод выбора. Какой из них требует меньше перестановок?
Метод выбора выполняет меньше перестановок, так как он делает их ровно столько, сколько элементов в массиве (в худшем случае). Пузырьковая сортировка может делать значительно больше перестановок, особенно если массив изначально неотсортирован.
4. Расскажите про основные идеи метода сортировки слиянием.
Сортировка слиянием основана на принципе «разделяй и властвуй». Массив рекурсивно делится на две части, сортируется, а затем объединяется в один отсортированный массив, сравнивая элементы из двух половин.
5. Как вы думаете, можно ли использовать метод «быстрой сортировки» для нечисловых данных, например для символьных строк?
Быстрая сортировка применима к символьным строкам, так как строки можно сравнивать лексикографически. Алгоритм будет работать так же, как и с числами, разделяя массив строк относительно опорного элемента.
6. От чего зависит скорость «быстрой сортировки»? Какой самый лучший и самый худший случай?
Скорость быстрой сортировки зависит от выбора опорного элемента. В среднем она выполняется за O(n log n), но в худшем случае (если опорные элементы выбираются неудачно) время может увеличиться до O(n²). Лучший случай – когда массив постоянно делится пополам.
7. Как вы думаете, может ли метод «быстрой сортировки» работать дольше, чем метод выбора (или другой «простой» метод)? Если да, то при каких условиях?
Да, быстрая сортировка может работать дольше метода выбора, если массив уже отсортирован, но алгоритм всегда выбирает крайний элемент в качестве опорного. В этом случае разделение массива будет неравномерным, что приведёт к худшей сложности O(n²).
8. Как нужно изменить приведённые в параграфе алгоритмы, чтобы элементы массива были отсортированы по убыванию?
def qSort(A, nStart, nEnd): if nStart >= nEnd: return L = nStart R = nEnd X = A[(L + R) // 2] # Опорный элемент while L <= R: while A[L] > X: # Ищем элемент, который меньше опорного L += 1 while A[R] < X: # Ищем элемент, который больше опорного R -= 1 if L <= R: A[L], A[R] = A[R], A[L] L += 1 R -= 1
qSort(A, nStart, R) qSort(A, L, nEnd)
9. Какие встроенные средства сортировки массивов в Python вы знаете?
В Python встроены средства сортировки, такие как функция sorted() и метод .sort() для списков. Они реализуют эффективные алгоритмы, такие как Timsort, который комбинирует сортировку вставками и сортировку слиянием.
10. Как задать нестандартный порядок сортировки для функции sorted?
Функция sorted() позволяет задать нестандартный порядок сортировки с помощью параметра key. Можно использовать лямбда-функции, например: sorted(arr, key=lambda x: -x) # сортировка по убыванию Или, если сортируется список строк, можно изменить регистр или учитывать длину строк.
11. Что такое лямбдафункции? Когда их удобно использовать?
Лямбда-функции — это анонимные функции, определяемые с помощью lambda, которые удобно использовать для коротких операций без явного объявления функции. Например, в сортировке или фильтрации данных: sorted(arr, key=lambda x: x[1]) # сортировка по второму элементу кортежа
12. Чем отличаются функция sorted и метод sort для списков?
Функция sorted() создаёт новый отсортированный список, а метод .sort() изменяет исходный список на месте, не создавая копию.
13. Используя информацию из дополнительных источников и модуль time, попробуйте построить зависимость времени выполнения сортировки от размера массива для разных методов. Какие зависимости у вас получились?
Для исследования зависимости времени выполнения сортировки от размера массива можно использовать модуль time: import time import random
sizes = [100, 1000, 5000, 10000] for size in sizes: arr = [random.randint(0, 10000) for _ in range(size)] start = time.time() sorted(arr) end = time.time() print(f"Размер: {size}, Время: {end - start:.6f} секунд") Зависимость времени от размера массива для встроенной сортировки обычно близка к O(nlogn), так как Timsort эффективен. Для простых алгоритмов, таких как пузырьковая сортировка, зависимость будет O(n2).