10 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 64 Сортировка
Стр.232-233.
1. Метод пузырька основан на последовательном сравнении и обмене соседних элементов массива, пока массив не будет отсортирован. Метод выбора заключается в поиске минимального элемента в неотсортированной части массива и его перемещении в начало этой части.
2. Вложенный цикл необходим для того, чтобы каждый элемент массива можно было сравнить с каждым другим элементом, либо для того, чтобы провести последовательные обмены или перемещения элементов, обеспечивая правильное упорядочивание массива.
3. Метод пузырька требует больше перестановок, так как каждый элемент может перемещаться несколько раз за одну итерацию. Метод выбора требует меньше перестановок, так как каждый элемент перемещается на своё место только один раз за итерацию.
4. Метод сортировки слиянием основан на принципе «разделяй и властвуй». Массив делится на две части, каждая из которых сортируется рекурсивно, а затем отсортированные части сливаются в один массив. Это позволяет эффективно обрабатывать большие массивы.
5. Да, метод «быстрой сортировки» можно использовать для символьных строк. Вместо чисел элементы массива будут сравниваться по алфавитному порядку или другому критерию, применимому к строкам.
6. Скорость «быстрой сортировки» зависит от выбора опорного элемента. Лучший случай — когда опорный элемент делит массив на две равные части, худший случай — когда массив делится крайне неравномерно, что может привести к линейному времени выполнения.
7. Да, «быстрая сортировка» может работать дольше, чем метод выбора, если выбор опорного элемента постоянно приводит к крайне неравномерному разбиению массива, что создаёт условия для худшего случая.
8. Чтобы отсортировать элементы массива по убыванию, нужно изменить условие сравнения в алгоритмах сортировки, заменив «меньше» на «больше» и наоборот.
9. В Python есть встроенные функции sorted() и метод .sort() для списков. Эти функции позволяют сортировать массивы различными способами.
10. Для задания нестандартного порядка сортировки используется именованный параметр key, которому присваивается функция, возвращающая значение, по которому будет происходить сравнение элементов.
11. Лямбда-функции — это анонимные функции, определяемые с помощью ключевого слова lambda. Они удобны, когда нужно создать простую функцию на месте, без необходимости её явного определения.
12. Функция sorted() возвращает новый отсортированный список, не изменяя исходный, тогда как метод .sort() сортирует сам список на месте, не создавая нового списка.
13. Результаты могут показать, что простые методы сортировки, такие как пузырёк и выбор, работают медленно на больших массивах, в то время как сложные методы, такие как сортировка слиянием и быстрая сортировка, демонстрируют значительно лучшую производительность.
Проекты
а) Сравнение скорости работы алгоритмов сортировки
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import time import random def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 def quick_sort(arr): if len(arr) <= 1: return arr else: pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) size = [1000, 5000, 15000] methods = [bubble_sort, selection_sort, merge_sort, quick_sort] names = ["Bubble Sort", "Selection Sort", "Merge Sort", "Quick Sort"] for s in size: arr = [random.randint(0, s) for _ in range(s)] print(f"Array size: {s}") for i, method in enumerate(methods): start_time = time.time() if method == quick_sort: method(arr.copy()) else: method(arr.copy()) end_time = time.time() print(f"{names[i]} took {end_time - start_time:.5f} seconds") |
б) Сортировка слиянием для данных в файле
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 with open('data.txt', 'r') as file: data = list(map(int, file.readlines())) merge_sort(data) with open('sorted_data.txt', 'w') as file: for item in data: file.write(f"{item}\n") |
в) Экспериментальное определение скорости работы алгоритмов сортировки
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
import random import time # Функция для генерации списка случайных чисел заданного размера def generate_random_list(size): return [random.randint(1, 10000) for _ in range(size)] # Сортировка пузырьком def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Сортировка выбором def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] # Сортировка слиянием def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 # Быстрая сортировка def quick_sort(arr): if len(arr) <= 1: return arr else: pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) # Измерение времени выполнения алгоритмов сортировки def measure_time(sort_function, arr): start_time = time.time() sort_function(arr) end_time = time.time() return end_time - start_time # Основная функция для выполнения эксперимента def main(): sizes = [1000, 5000, 10000] algorithms = { "Сортировка пузырьком": bubble_sort, "Сортировка выбором": selection_sort, "Сортировка слиянием": merge_sort, "Быстрая сортировка": quick_sort } for size in sizes: print(f"\nРазмер массива: {size}") arr = generate_random_list(size) for name, func in algorithms.items(): arr_copy = arr.copy() time_taken = measure_time(func, arr_copy) print(f"{name}: {time_taken:.6f} секунд") if __name__ == "__main__": main() |
| 62 | 63 | 64 | 65 | 66 |