Лабораторная работа асд. Лабораторные работы_по_АСД. Дисциплина Алгоритмы и структуры данных Отчёт по лабораторной работе
 Скачать 3.09 Mb.
|
Лабораторная работа №6. Алгоритмы сортировкиЗадание Составить блок-схемы алгоритмов решения задач, выполнить их реализацию в виде программы на языке программирования и представить скрин экрана с результатом работы программы. Выполнить анализ работы алгоритмов при задании различных вариантов исходных данных и описать возможные ограничения по входным данным. Составить отчёт по выполненной лабораторной работе. Решение Задача 1. Задать массив из 8-12 элементов. Разобрать на примере этого массива и подробно описать сортировку методом выбора; методом обмена (пузырька); методом вставки. Подсчитать сложность каждого метода для вашего конкретного примера, то есть подсчитать количество операций сравнения и записи(присвоения). Вывести на экран. Все используемые идентификаторы представлены в таблице 22 Таблица 22 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 43:  Рисунок 42- Блок схема алгоритма решения задачи 1 Программа на C#: using System; namespace lr6_z1 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); Console.WriteLine("1) Сортировка методом выбора"); int comparison = 0, recording = 0; int[] mas1 = new int[N]; mas.CopyTo(mas1, 0); for (int i = 0; i < N - 1; i++) { int min = i; for (int j = i + 1; j < N; j++) { comparison++; if (mas1[j] < mas1[min]) min = j; } comparison++; if (min != i) { int temp = mas1[i]; mas1[i] = mas1[min]; mas1[min] = temp; recording++; } } Console.Write("Отсортированный массив: "); for (int i = 0; i < N; i++) Console.Write(mas1[i] + " "); Console.WriteLine(); Console.WriteLine("Количество операций сравнения: " + comparison); Console.WriteLine("Количество операций записи: " + recording); Console.WriteLine(); Console.WriteLine("2) Сортировка методом обмена (пузырька)"); comparison = 0; recording = 0; int[] mas2 = new int[N]; mas.CopyTo(mas2, 0); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { comparison++; if (mas2[i] > mas2[j]) { int temp = mas2[i]; mas2[i] = mas2[j]; mas2[j] = temp; recording++; } } } Console.Write("Отсортированный массив: "); for (int i = 0; i < N; i++) Console.Write(mas2[i] + " "); Console.WriteLine(); Console.WriteLine("Количество операций сравнения: " + comparison); Console.WriteLine("Количество операций записи: " + recording); Console.WriteLine(); Console.WriteLine("3) Сортировка методом вставки"); comparison = 0; recording = 0; int[] mas3 = new int[N]; mas.CopyTo(mas3, 0); for (int i = 1; i < N; i++) { int cur = mas3[i]; int j = i; while (j > 0 && cur < mas3[j - 1]) { comparison++; recording++; mas3[j] = mas3[j - 1]; j--; } mas3[j] = cur; } Console.Write("Отсортированный массив: "); for (int i = 0; i < N; i++) Console.Write(mas3[i] + " "); Console.WriteLine(); Console.WriteLine("Количество операций сравнения: " + comparison); Console.WriteLine("Количество операций записи: " + recording); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 44.  Рисунок 43 - Скриншот результата работы программы задачи 1. Задача 2. Придумать свой алгоритм сортировки, если получится, если нет, то найти и разобрать, указав автора и ссылку. Алгоритм сортировки подсчетом. https://ru.wikipedia.org/wiki/Сортировка_подсчётом Сортировка подсчётом - это алгоритм, основанный на подсчёте повторяющихся элементов в массиве. Есть массив A длиной n элементов, который нужно отсортировать. Создаётся вспомогательный массив C с индексами от 0 до k (максимальное значение в массиве A) и заполняется нулями. Последовательно проходим по массиву A и записываем в C[i] количество чисел, равных i. Таким образом индексы в массиве C - это значения массива A, а значение в массиве C - это то, сколько раз это число повторяется в массиве A. Проходим по массиву C и переносим значения в массив A. Все используемые идентификаторы представлены в таблице 23 Таблица 23 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 45:  Рисунок 44 - Блок схема алгоритма решения задачи 2 Программа на C#: using System; namespace lr6_z2 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); int max = mas[0]; for (int i = 0; i < N; i++) // находим максмальный элемент массива { if (max < mas[i]) max = mas[i]; } int[] C = new int[max + 1]; for (int i = 0; i < max + 1; i++) // заполняем массив С нулями C[i] = 0; for (int i = 0; i < N; i++) // заполняем массив С C[mas[i]] = C[mas[i]] + 1; int k = 0; for (int i = 0; i < max + 1; i++) for (int j = 0; j < C[i]; j++) { mas[k] = i; k++; } Console.WriteLine("Отсортированный массив:"); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 46.  Рисунок 45 - Скриншот результата работы программы задачи 2. Задача 3. Изменить решения в трех рассмотренных методах сортировки так, что бы осуществлялась сортировка: 3.5. однозначных элементов массива. Задачу 3 делаем по вариантам с разбором на пошаговом примере (вариант как в ЛР2). Варианты для задачи 3:
Все используемые идентификаторы представлены в таблице 24 Таблица 24 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 47:  Рисунок 46 - Блок схема алгоритма решения задачи 3 Программа на C#: using System; namespace lr5_var15_z3 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); for (int i = 1; i < N; i++) { if (Math.Abs(mas[i]) < 10) { int cur = mas[i]; int j = i - 1; int k = i; while (j >= 0) { if (Math.Abs(mas[j]) < 10 && cur < mas[j]) { mas[k] = mas[j]; mas[j] = cur; k = j; } j--; } } } Console.Write("Массив после сортировки: "); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 48.  Рисунок 47 - Скриншот результата работы программы задачи 3. Задача 4. Дан, например, массив 1 2 3 5 7 9 10. За один просмотр методом «пузырька» он становится отсортированным, остальные просмотры ничего не дают. Исключить лишние просмотры. Все используемые идентификаторы представлены в таблице 25 Таблица 25 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 49:  Рисунок 48 - Блок схема алгоритма решения задачи 4 Программа на C#: using System; namespace lr6_z4 { class Program { static void Main(string[] args) { int i; Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); i = 0; bool sorted = false; while (i < N && !sorted) { sorted = true; for (int j = 0; j < N - i - 1; j++) { if (mas[j] > mas[j + 1]) { sorted = false; int temp = mas[j]; mas[j] = mas[j + 1]; mas[j + 1] = temp; } } i++; } Console.WriteLine("Массив после сортировки: "); for (i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 50.  Рисунок 49 - Скриншот результата работы программы задачи 4. Задача 5. Массив 1 2 3 5 7 9 10 сортируется методом «пузырька» за один просмотр, а массив 5 7 9 10 12 3 – за пять (N-1). Явное неравноправие. Устранить его можно путем смены направлений просмотров, т. е. первоначально в направлении → получаем 5 7 9 10 3 12, а затем в направлении результат – 3 5 7 9 10 12. Итак, чередуем направления, пока массив не будет отсортирован. Все используемые идентификаторы представлены в таблице 26 Таблица 26 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 51:  Рисунок 50 - Блок схема алгоритма решения задачи 4 Программа на C#: using System; namespace lr6_z5 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); int left = 0, right = N - 1; while (left <= right) { for (int i = left; i < right; i++) { if (mas[i] > mas[i + 1]) { int temp = mas[i]; mas[i] = mas[i + 1]; mas[i + 1] = temp; } } right--; for (int i = right; i > left; i--) { if (mas[i - 1] > mas[i]) { int temp = mas[i - 1]; mas[i - 1] = mas[i]; mas[i] = temp; } } left++; } Console.WriteLine("Массив после сортировки: "); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 52.  Рисунок 51 - Скриншот результата работы программы задачи 5. Задача 6. Объединить требования заданий 4 и 5 в единое целое. Этот метод называется «шейкер-сортировкой» (пузырьковая без лишних просмотров). Реализовать его. Все используемые идентификаторы представлены в таблице 27 Таблица 27 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 53:  Рисунок 52- Блок схема алгоритма решения задачи 5 Программа на C#: using System; namespace lr6_z6 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); int left = 0, right = N - 1; bool sorted = false; while (left <= right && !sorted) { sorted = true; for (int i = left; i < right; i++) { if (mas[i] > mas[i + 1]) { sorted = false; int temp = mas[i]; mas[i] = mas[i + 1]; mas[i + 1] = temp; } } right--; for (int i = right; i > left; i--) { if (mas[i - 1] > mas[i]) { sorted = false; int temp = mas[i - 1]; mas[i - 1] = mas[i]; mas[i] = temp; } } left++; // увеличиваем левую границу } Console.WriteLine("Массив после сортировки: "); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 54.  Рисунок 53 - Скриншот результата работы программы задачи 6. Задача 7. В сортировке простыми вставками убрать переменную w, т. е. внутренний цикл записать в виде: While A[0]< A[j] Do. Подсказка. Массив А необходимо сделать типа Array[0..Nmax] Of Integerи i-й элемент записывать на 0 место, так называемый прием «барьерного элемента». Все используемые идентификаторы представлены в таблице 28 Таблица 28 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 55:  Рисунок 54 - Блок схема алгоритма решения задачи 7 Программа на C#: using System; namespace lr6_z7 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N + 1]; for (int i = 1; i < N + 1; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); for (int i = 2; i < N + 1; i++) { mas[0] = mas[i]; int j = i; while (j > 0 && mas[0] < mas[j - 1]) { mas[j] = mas[j - 1]; j--; } mas[j] = mas[0]; } Console.WriteLine("Массив после сортировки:"); for (int i = 1; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 56.  Рисунок 55 - Скриншот результата работы программы задачи 7. Задача 8. Метод вставок. На момент вставки элемента с номером i элементы массива с номерами от 1 до i-1отсортированы. Выберем из них средний элемент (или один из двух средних) и сравним его с элементом А[i]. Если A[i]меньше этого элемента, то поиск места вставки следует продолжать в левой половине, иначе – в правой половине отсортированного массива. Эта схема получила название сортировки бинарными вставками. Она предложена Дж. Мочли в 1946 году и была одной из первых публикаций по методам компьютерной сортировки. Реализовать данную схему. Все используемые идентификаторы представлены в таблице 29 Таблица 29 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 57:  Рисунок 56- Блок схема алгоритма решения задачи 8 Программа на C#: using System; namespace lr6_z8 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив:"); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); for (int i = 1; i < N; i++) { int current = mas[i]; int j = i; int local = binarySearch(mas, current, 0, j); while (j > local) { mas[j] = mas[j - 1]; j--; } mas[j] = current; } Console.WriteLine("Массив после сортировки:"); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); int binarySearch(int[] a, int current, int l, int r) { if (r <= l) return (current > a[l]) ? (l + 1) : l; int middle = (l + r) / 2; if (current == a[middle]) return middle + 1; if (current > a[middle]) return binarySearch(a, current, middle + 1, r); return binarySearch(a, current, l, middle - 1); } } } } Скриншот результата работы программы представлен на рисунке 58. Рисунок 57 - Скриншот результата работы программы задачи 8. Задача 9. Д. Л. Шелл в 1959 году предложил следующую модификацию метода – «сортировку с убывающим шагом». Ее суть покажем на примере. Массив из 8 элементов. Делим его на 4 группы по 2 элемента, сортируем элементы в каждой группе. Затем – на 2 группы по 4 элемента, выполняем для них сортировку и, наконец, сортируем одну группу из 8 элементов. При простых вставках мы перемещали элемент только в соседнюю позицию, а в этом методе перемещаем на большие расстояния, что приводит к получению более отсортированного массива и, в конечном итоге, к повышению эффективности метода. Значения 4, 2, 1 (приращения) не являются догмой. Можно выполнить сортировку при 5, 3, 1. Последний элемент должен быть равен 1. Д. Кнут дает оценку метода при грамотном выборе приращений – O(N1.2). Лучшим считается выбор в качестве значений приращений взаимно простых чисел. Реализовать «сортировку с убывающим шагом» для заданных значений приращений. Все используемые идентификаторы представлены в таблице 30 Таблица 30 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 59:  Рисунок 58- Блок схема алгоритма решения задачи 9 Программа на C#: using System; namespace lr6_z9 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив: "); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); int d = N / 2; while (d >= 1) { for (int i = 0; i < (N - d); i++) { int j = i; while ((j >= 0) && (mas[j] > mas[j + d])) { int temp = mas[j]; mas[j] = mas[j + d]; mas[j + d] = temp; j = j - d; } } d = d / 2; } Console.WriteLine("Массив после сортировки:"); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); } } } Скриншот результата работы программы представлен на рисунке 60.  Рисунок 59 - Скриншот результата работы программы задачи 9. Задача 10. Пусть N является точным квадратом натурального числа, например 3. Разделим массив на Sqrt(N)групп по Sqrt(N)элементов в каждой. Выберем максимальный элемент в каждой группе... Проще рассмотреть пример. Дан массив 7 10 3 5 15 9 6 12 8. При разбивке на группы – (7 10 3) (5 15 9) (6 12 8). Максимальные элементы 10 15 12. Максимальный из них 15, он во второй группе. Если оставшиеся элементы из второй группы, а это 5 и 9, меньше 10 и 12, то мы нашли сразу три элемента, записываемые на свои места. Если нет, то заменяем максимальные элементы элементами из группы. Этот метод предложен Э. Х. Фрэндом в 1956 году и получил название метода квадратичного выбора. Количество сравнений имеет порядок 0(N*Sqrt(N)).Реализовать метод. Все используемые идентификаторы представлены в таблице 31 Таблица 31 – Идентификаторы
Блок схема алгоритма решения задачи представлена на рисунке 61:  Рисунок 60 - Блок схема алгоритма решения задачи 10 Программа на C#: using System; namespace lr6_z10 { class Program { static void Main(string[] args) { Console.Write("Введите n: "); int N = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("Введите массив: "); int[] mas = new int[N]; for (int i = 0; i < N; i++) mas[i] = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(); int groupsCount = (int)Math.Round(Math.Sqrt(N)); int[][] W = new int[groupsCount][]; int count = 0; for (int i = 0; i < groupsCount; i++) { int n = N / groupsCount; if (i < N % groupsCount) n++; W[i] = new int[n]; for (int j = 0; j < n; j++) W[i][j] = mas[j + count]; count += n; } int[] B = new int[groupsCount]; for (int i = 0; i < groupsCount; i++) B[i] = Min(W[i]); for (int i = 0; i < N; i++) { int index = MinIndex(B); mas[i] = B[index]; B[index] = Min(W[index]); } Console.WriteLine("Массив после сортировки: "); for (int i = 0; i < N; i++) Console.Write(mas[i] + " "); Console.ReadKey(); int Min(int[] array) { int index = MinIndex(array); int min = array[index]; array[index] = int.MaxValue; return min; } int MinIndex(int[] array) { int min = array[0]; int index = 0; for (int i = 1; i < array.Length; i++) { if (min > array[i]) { min = array[i]; index = i; } } return index; } } } } Скриншот результата работы программы представлен на рисунке 62.  Рисунок 61 - Скриншот результата работы программы задачи 10. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||