Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
Аннотация к работе
Целью данной курсовой работы является изучения основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Например, для того, чтобы ввести понятие типа данных и предложить классификацию возможных типов, используются развитые механизмы абстрактной алгебры; при описании алгоритмов в обязательном порядке приводятся асимптотические оценки их сложности.В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Сортировка методом вставок (Insertion sort) - Сложность алгоритма: O(n2); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда Сортировка подсчетом (Counting sort) - Сложность алгоритма: O(n k); требуется O(n k) дополнительной памяти Сортировка слиянием (Merge sort) - Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем - сливаем отсортированные спискиАлгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своем месте, «всплывает» до нужной позиции как пузырек в воде, отсюда и название алгоритма.Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ: прост в реализации эффективен на небольших наборах данных эффективен на наборах данных, которые уже частично отсортированы это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы) может сортировать список по мере его получения На каждом шаге алгоритма, мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива - произволен, может использоваться практически любой алгоритм выбора.Сортировка методом выбора (англ. selection sort) - алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки.Шаги алгоритма: находим минимальное значение в текущем списке производим обмен этого значения со значением на первой позиции теперь сортируем хвост списка, исключив из рассмотрения уже отсортированный первый элемент Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных ключа для ускорения нахождения и удаления минимального элемента. Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на свое место и минимальное, и максимальное значения. {if (list[j] <list[min])Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов. Для примера возьмем файл из 16 элементов. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Следующий этап - 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Следующий этап - 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16.Быстрая сортировка (англ. quicksort) - широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром.Шаги алгоритма таковы: Выбираем в массиве некоторый элемент, который будем называть опорным элементом. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного - справа от него. Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место. сортировка данные алгоритм внутренний C#: int partition (int[] array, int start, intend)По результатам замеров производительности методов можно сделать следующие выводы: Наиболее универсальным методом, является метод быстрой сортировки («QUICKSORT»), он показывает стабильно высокие результаты на любых размерах массивов. Метод вставки эффективен, при условии большого времени выполнения операций перестановки, так как он является абсолютным лидером по количеству перестановок, проигрывая при этом по количеству сравнений.
План
Содержание
Введение
1. Алгоритмы сортировки
1.1 Сортировка пузырьком
1.2 Сортировка методом вставок
1.3 Сортировка методом выбора
1.4 Сортировка методом Шелла
1.5 Быстрая сортировка
2. Алгоритм
Заключение
Список литературы
Приложение
Введение
Целью данной курсовой работы является изучения основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Более подробно рассмотрен метод обменной сортировки.
Если обратиться к литературе, то можно обнаружить два крайних подхода к представлению материала. Некоторые авторы любят излагать материал на высоком теоретическом уровне. Например, для того, чтобы ввести понятие типа данных и предложить классификацию возможных типов, используются развитые механизмы абстрактной алгебры; при описании алгоритмов в обязательном порядке приводятся асимптотические оценки их сложности. Другой подход состоит в максимальном приближении к практике. Обычно выбирается некоторый конкретный язык программирования, и все описываемые структуры данных и алгоритмы представляются на этом языке.
Вывод
По результатам замеров производительности методов можно сделать следующие выводы: Наиболее универсальным методом, является метод быстрой сортировки («QUICKSORT»), он показывает стабильно высокие результаты на любых размерах массивов. На втором месте находится метод Шелла. Его использование может быть обосновано большее простым алгоритмом с точки зрения программиста.
Метод вставки эффективен, при условии большого времени выполнения операций перестановки, так как он является абсолютным лидером по количеству перестановок, проигрывая при этом по количеству сравнений.
При использовании небольших массивов данных нет большой разницы по скорости между методами сортировки, поэтому целесообразнее применять метод Пузырька или метод вставок.
Исследование проводилось на массивах с большой степенью неупорядоченности. Для массивов, которые уже являются почти отсортированными, наиболее применим метод сортировки вставками.
Список литературы
1. Вирт Н. Алгоритмы и структуры данных. M.: ДМК Пресс, 2010. - 411
2.C# для школьников: Учебное пособие / М. Дрейер. Перевод с англ. под ред. В. Биллига-М.: БИНОМ. Лаборатория знаний,2009. - 128
3. А.В. Левитин. Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ. - М.: «Вильямс», 2006. - С. 174-179.