Differences

This shows you the differences between two versions of the page.

--- g3l:lab3_var3 [2026/02/25 09:54] – created - external edit 127.0.0.1
+++ g3l:lab3_var3 [2026/02/25 10:06] (current) – eugeneai
@@ Line 1: / Line 1: @@
 ====== Сортировка слиянием для больших массивов ======
-**Задание:** Реализовать сортировку слиянием для работы с большими массивами данных
+**Задание:** Реализовать сортировку слиянием для работы с большими массивами данных. Продемонстрировать рекурсивное разделение массива и последующее слияние отсортированных подмассивов. Оценить использование дополнительной памяти.
 **Пример входных данных:**
 <code>
-f(x) = e^x - 3x = 0
+Массив: [38, 27, 43, 3, 9, 82, 10]
-Начальное приближение: x0 = 1.0
+Порог переключения на сортировку вставками: 3 (для оптимизации)
-Точность: 0.0001
 </code>
@@ Line 15: / Line 15: @@
 <code>
-Корень уравнения: x = 1.5121
+Исходный массив: [38, 27, 43, 3, 9, 82, 10]
-Количество итераций: 5
-f(1.5121) = 0.00008
+Процесс разделения:
+  Делим [38, 27, 43, 3, 9, 82, 10]
+    Левая часть: [38, 27, 43, 3]
+      Делим [38, 27, 43, 3]
+        Левая часть: [38, 27]
+          Делим [38, 27]
+            Левая часть: [38] (базовый случай)
+            Правая часть: [27] (базовый случай)
+          Сливаем [38] и [27] → [27, 38]
+        Правая часть: [43, 3]
+          Делим [43, 3]
+            Левая часть: [43] (базовый случай)
+            Правая часть: [3] (базовый случай)
+          Сливаем [43] и [3] → [3, 43]
+      Сливаем [27, 38] и [3, 43] → [3, 27, 38, 43]
+    Правая часть: [9, 82, 10]
+      Делим [9, 82, 10] (размер 3 ≤ порога, используем сортировку вставками)
+      Сортировка вставками: [9, 82, 10] → [9, 10, 82]
+  Сливаем [3, 27, 38, 43] и [9, 10, 82]
+Процесс слияния (финальный шаг):
+  Сравниваем 3 и 9 → берем 3
+  Сравниваем 27 и 9 → берем 9
+  Сравниваем 27 и 10 → берем 10
+  Сравниваем 27 и 82 → берем 27
+  Сравниваем 38 и 82 → берем 38
+  Сравниваем 43 и 82 → берем 43
+  Остаток правой части: [82]
+  Результат: [3, 9, 10, 27, 38, 43, 82]
+Отсортированный массив: [3, 9, 10, 27, 38, 43, 82]
+Количество уровней рекурсии: 3
+Использовано дополнительной памяти: 7 элементов (временный массив)
 </code>
@@ Line 62: / Line 94: @@
 **Вариант 20:** Массив: [14, 27, 39, 52, 65, 78, 81, 93]
-**Вариант 2:** Вариант задачи 2 для лабораторной 3.3
+**Дополнительные параметры (выбрать в соответствии с вариантом):**
+  * Варианты 1-4: Без оптимизации (чистое рекурсивное слияние)
-**Вариант 3:** Вариант задачи 3 для лабораторной 3.3
+  * Варианты 5-8: С оптимизацией (использовать сортировку вставками для подмассивов размером ≤ 4)
+  * Варианты 9-12: С визуализацией использования памяти (показывать выделение временных массивов)
-**Вариант 4:** Вариант задачи 4 для лабораторной 3.3
+  * Варианты 13-16: Итеративная реализация (снизу-вверх) без рекурсии
+  * Варианты 17-20: Внешняя сортировка (работа с файлами, имитация больших данных)
-**Вариант 5:** Вариант задачи 5 для лабораторной 3.3
-**Вариант 6:** Вариант задачи 6 для лабораторной 3.3
-**Вариант 7:** Вариант задачи 7 для лабораторной 3.3
-**Вариант 8:** Вариант задачи 8 для лабораторной 3.3
-**Вариант 9:** Вариант задачи 9 для лабораторной 3.3
-**Вариант 10:** Вариант задачи 10 для лабораторной 3.3
-**Вариант 11:** Вариант задачи 11 для лабораторной 3.3
-**Вариант 12:** Вариант задачи 12 для лабораторной 3.3
-**Вариант 13:** Вариант задачи 13 для лабораторной 3.3
-**Вариант 14:** Вариант задачи 14 для лабораторной 3.3
-**Вариант 15:** Вариант задачи 15 для лабораторной 3.3
-**Вариант 16:** Вариант задачи 16 для лабораторной 3.3
-**Вариант 17:** Вариант задачи 17 для лабораторной 3.3
-**Вариант 18:** Вариант задачи 18 для лабораторной 3.3
-**Вариант 19:** Вариант задачи 19 для лабораторной 3.3
-**Вариант 20:** Вариант задачи 20 для лабораторной 3.3
+**Примечание:** Для вариантов 17-20 считать, что массив не помещается в оперативную память, и реализовать слияние временных файлов на диске.