курсовая по основам проиграмирвоания 123. Напиши курсовую использую данный план
 Скачать 25.51 Kb.
|
|
напиши курсовую использую данный план: 1 Введение Обоснование выбора темы Цель и задачи работы Описание структуры курсовой II. Описание алгоритма сортировки посредством слияния списков Основные принципы работы алгоритма Алгоритм в псевдокоде Пример работы алгоритма на простом списке 3 Рекурсивная реализация алгоритма Нерекурсивная реализация алгоритма Примеры использования алгоритма для сортировки различных типов данных и объектов IV. Анализ алгоритма сортировки посредством слияния списков Сложность алгоритма Сравнение с другими алгоритмами сортировки Преимущества и недостатки алгоритма V. Заключение Результаты выполненной работы Выводы и рекомендации по применению алгоритма сортировки посредством слияния списков Перспективы дальнейших исследований в данной области VI. Список использованных источников Перечень литературы и интернет-ресурсов, использованных при написании курсовой. и примеры на языке С++ с количеством слов более 5 тысяч Сортировка является одной из наиболее важных задач в области информатики и алгоритмов. Существует множество алгоритмов сортировки, каждый из которых имеет свои особенности и применимость в различных ситуациях. Один из таких алгоритмов - сортировка посредством слияния списков - рассматривается в данной курсовой работе. Обоснование выбора темы Выбор данной темы обусловлен ее актуальностью и практической значимостью. Сортировка посредством слияния списков является одним из наиболее эффективных алгоритмов сортировки для больших объемов данных и широко применяется в различных областях, в том числе в базах данных, информационных системах и науке о данных. Цель и задачи работы Цель данной курсовой работы состоит в изучении алгоритма сортировки посредством слияния списков, его реализации на языке программирования Python и анализе его эффективности и применимости в различных ситуациях. Для достижения этой цели были поставлены следующие задачи: изучение основных принципов работы алгоритма сортировки посредством слияния списков; написание псевдокода алгоритма сортировки посредством слияния списков; реализация алгоритма сортировки посредством слияния списков на языке программирования Python; исследование эффективности алгоритма сортировки посредством слияния списков на различных типах данных и объектах; проведение анализа сложности алгоритма сортировки посредством слияния списков; сравнение алгоритма сортировки посредством слияния списков с другими алгоритмами сортировки; выявление преимуществ и недостатков алгоритма сортировки посредством слияния списков. Описание алгоритма сортировки посредством слияния списков Алгоритм сортировки слиянием (Merge sort) можно реализовать на языке C++ следующим образом: #include #include using namespace std; // Функция для слияния двух отсортированных массивов void merge(vector // Вычисляем размеры двух подмассивов int n1 = m - l + 1; int n2 = r - m; // Создаем временные векторы для хранения данных из левой и правой частей массива vector vector // Копируем данные во временные векторы for (int i = 0; i < n1; i++) { left[i] = arr[l + i]; } for (int j = 0; j < n2; j++) { right[j] = arr[m + 1 + j]; } // Слияние временных векторов в исходный массив int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (left[i] <= right[j]) { arr[k] = left[i]; i++; } else { arr[k] = right[j]; j++; } k++; } // Копируем оставшиеся элементы из левого и правого подмассивов в исходный массив while (i < n1) { arr[k] = left[i]; i++; k++; } while (j < n2) { arr[k] = right[j]; j++; k++; } } // Функция для сортировки массива методом слияния void mergeSort(vector if (l < r) { // Находим середину массива int m = l + (r - l) / 2; // Рекурсивно сортируем левую и правую части массива mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Слияние двух отсортированных массивов merge(arr, l, m, r); } } int main() { vector int n = arr.size(); cout << "Исходный массив: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } mergeSort(arr, 0, n - 1); cout << "\nОтсортированный массив: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } return 0; } Как видно из кода, функция merge используется для слияния двух отсортированных подмассивов в один отсортированный массив. Основные принципы работы алгоритма Основным принципом работы алгоритма сортировки посредством слияния списков является разделение списка на меньшие подсписки, сортировка каждого подсписка отдельно и последующее их слияние в один отсортированный список. Для реализации этого алгоритма используется рекурсивный подход. При рекурсивной сортировке списка с помощью слияния, сначала исходный список разбивается на две примерно равные половины, после чего каждая из них рекурсивно сортируется. Это происходит до тех пор, пока размер каждого подсписка не достигнет одного элемента, так как один элемент считается уже отсортированным. Затем происходит слияние двух отсортированных подсписков в один отсортированный список. Для этого используется два указателя, один указывает на первый элемент первого списка, второй указывает на первый элемент второго списка. Затем выбирается минимальный элемент из этих двух списков, и он добавляется в результирующий список. Выбранный элемент удаляется из исходного списка, и указатель перемещается на следующий элемент в соответствующем списке. Этот процесс продолжается до тех пор, пока все элементы из обоих списков не будут добавлены в результирующий список. Одним из главных преимуществ сортировки слиянием является ее стабильность, то есть порядок элементов с одинаковыми значениями сохраняется после сортировки. Также, благодаря своей эффективности, сортировка слиянием является одним из самых используемых алгоритмов сортировки в программировании. Псевдо код Код сортировки слиянием можно представить в виде псевдокода. Ниже приведен пример рекурсивной реализации алгоритма сортировки слиянием на языке псевдокода: function merge_sort(list) if length(list) ≤ 1 return list else mid = length(list) / 2 left_list = merge_sort(list[1:mid]) right_list = merge_sort(list[mid+1:end]) return merge(left_list, right_list) function merge(left_list, right_list) sorted_list = [] while length(left_list) ≠ 0 and length(right_list) ≠ 0 if left_list[0] ≤ right_list[0] sorted_list.append(left_list[0]) left_list = left_list[1:] else sorted_list.append(right_list[0]) right_list = right_list[1:] if length(left_list) ≠ 0 sorted_list.extend(left_list) if length(right_list) ≠ 0 sorted_list.extend(right_list) return sorted_list Функция merge_sort принимает список и возвращает отсортированный список. Сначала проверяется, что список имеет длину более одного элемента, иначе он считается уже отсортированным и возвращается. Затем список разбивается на две части и каждая часть рекурсивно сортируется с помощью merge_sort. Далее отсортированные списки объединяются с помощью функции merge, которая сравнивает первый элемент каждого списка и добавляет наименьший в новый список, продолжая этот процесс до тех пор, пока один из списков не станет пустым. Затем оставшийся список просто добавляется в новый список. Наконец, отсортированный список возвращается из функции merge_sort. Функция merge принимает два отсортированных списка и возвращает отсортированный список, который объединяет эти два списка. Она создает новый пустой список sorted_list и добавляет элементы из двух списков, пока они не будут пустыми. При каждой итерации она сравнивает первый элемент каждого списка и добавляет наименьший элемент в sorted_list. Затем она удаляет этот элемент из списка и продолжает сравнивать оставшиеся элементы. Когда один из списков становится пустым, она просто добавляет оставшийся список в sorted_list. Наконец, отсортированный список возвращается из функции merge. Пример работы алгоритма на простом списке Конкретная реализация алгоритма на языке C++ может выглядеть следующим образом: #include #include using namespace std; vector vector while (left.size() > 0 && right.size() > 0) { if (left[0] <= right[0]) { result.push_back(left[0]); left.erase(left.begin()); } else { result.push_back(right[0]); right.erase(right.begin()); } } while (left.size() > 0) { result.push_back(left[0]); left.erase(left.begin()); } while (right.size() > 0) { result.push_back(right[0]); right.erase(right.begin()); } return result; } vector if (arr.size() <= 1) { return arr; } int mid = arr.size() / 2; vector vector left = mergeSort(left); right = mergeSort(right); return merge(left, right); } int main() { vector arr = mergeSort(arr); for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } cout << endl; return 0; } В данном примере мы используем две функции: merge() и mergeSort(). Функция merge() сливает два отсортированных списка в один отсортированный список. Функция mergeSort() рекурсивно разбивает список на две части, сортирует их отдельно, а затем сливает их в один отсортированный список с помощью функции merge(). Для примера мы создали вектор arr с неотсортированными элементами и применили к нему функцию mergeSort(). Затем мы выводим отсортированные элементы в консоль. В результате выполнения данного кода мы получим следующий вывод: 1 2 3 4 5 6 7 8 Таким образом, данный пример иллюстрирует работу алгоритма сортировки слиянием на языке C++. Рекурсивыный код Код рекурсивной реализации алгоритма сортировки слиянием на языке C++ может выглядеть следующим образом: #include #include using namespace std; // Функция для слияния двух отсортированных подмассивов void merge(vector int n1 = mid - left + 1; // размер первого подмассива int n2 = right - mid; // размер второго подмассива // Создание временных массивов vector // Копирование данных во временные массивы for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } // Объединение временных массивов и сортировка элементов int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // Копирование оставшихся элементов первого подмассива (если они есть) while (i < n1) { arr[k] = L[i]; i++; k++; } // Копирование оставшихся элементов второго подмассива (если они есть) while (j < n2) { arr[k] = R[j]; j++; k++; } } // Рекурсивная функция сортировки слиянием void mergeSort(vector if (left < right) { // Находим середину массива int mid = left + (right - left) / 2; // Сортируем левую и правую части массива mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Слияние отсортированных частей merge(arr, left, mid, right); } } int main() { vector int n = arr.size(); cout << "Исходный массив: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; mergeSort(arr, 0, n - 1); cout << "Отсортированный массив: "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; return 0; } Этот код сначала объявляет функцию merge, которая выполняет слияние двух отсортированных подмассивов в один. Не рекурсивное Не рекурсивная реализация алгоритма сортировки слиянием также возможна. Для этого необходимо использовать стек для хранения диапазонов индексов массива, которые нужно отсортировать. На каждой итерации алгоритма извлекается пара диапазонов индексов из стека, которые нужно слить в отсортированный массив. Затем полученный отсортированный массив помещается обратно в исходный массив по соответствующим индексам. Вот пример нерекурсивной реализации алгоритма сортировки слиянием на языке C++: void mergeSortIterative(int arr[], int n) { int curr_size; // текущий размер подмассивов int left_start; // начало левого подмассива // Обрабатываем подмассивы различного размера for (curr_size = 1; curr_size <= n-1; curr_size = 2*curr_size) { // Обрабатываем подмассивы длины curr_size for (left_start = 0; left_start < n-1; left_start += 2*curr_size) { // Находим конец левого подмассива int mid = min(left_start + curr_size - 1, n-1); // Находим конец правого подмассива int right_end = min(left_start + 2*curr_size - 1, n-1); // Сливаем два подмассива в один merge(arr, left_start, mid, right_end); } } } Здесь используется два вложенных цикла: внешний цикл управляет текущим размером подмассивов, а внутренний цикл обрабатывает все пары подмассивов данного размера. На каждой итерации внутреннего цикла находится начало левого подмассива и вычисляются индексы его конца и конца правого подмассива. Затем два подмассива объединяются с помощью функции merge, определенной ранее. Примеры Алгоритм сортировки слиянием может быть использован для сортировки различных типов данных, таких как целые числа, числа с плавающей запятой, строки, структуры и т.д. Для сортировки целых чисел можно использовать следующий код на языке C++: #include #include using namespace std; void merge(vector int n1 = m - l + 1; int n2 = r - m; vector vector for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0; int j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(vector if (l >= r) { return; } int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } int main() { vector int n = arr.size(); mergeSort(arr, 0, n - 1); for (int i = 0; i < n; i++) cout << arr[i] << " "; return 0; } |