СРАВНЕНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ СОРТИРОВКИ

Министерство образования Российской Федерации Владивостокский государственный университет экономики и сервиса СРАВНЕНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ СОРТИРОВКИ курсовая работа по дисциплине Алгоритмизация и программирование Выполнил студент гр. ИТ-0401 Иванова Т.А. Проверил доцент. каф. ИСКТ к.т.н. Гриняк В.М. Владивосток 2006 ВВЕДЕНИЕ Целью курсовой работы является закрепление основ и углубление

знаний приемов программирования на алгоритмических языках высокого уровня, получение практических навыков в создании программного продукта, отработка при мов проведения вычислительных экспериментов на ЭВМ. Данная курсовая работа содержит в себе два программы, сортирующих массив со случайными числами. В первой программе описана сортировка методом вставок, во второй пузырьковая сортировка. Для того чтобы выяснить, какая сортировка эффективнее, производится подсчет среднего числа сравнений,

необходимого для сортировки n элементов тем и другим алгоритмом. ПОСТАНОВКА ЗАДАЧИ Сравнить эффективность алгоритмов сортировки пузырьковой и сортировки вставками. ОПИСАНИЕ РЕШЕНИЯ ЗАДАЧИ СОРТИРОВКА ВСТАВКАМИ Сортировка вставками элементов a1, a2, , an относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a0 а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется

в нужное место. При вставке элемент aj временно размещается в переменной w, и просматриваются элементы aj-1, aj-2, ,a1 уже к этому времени упорядоченные . Они сравниваются с w и сдвигаются, если обнаруживается, что они больше чем w. for j 2 j lt n 1 j w a j i j-1 while w lt a i a i 1 a i i i-1 a i 1 w Сложность алгоритма определяется числом проверок условия w lt a i в цикле. В худшем случае потребуется n n-1 2 таких сравнений, то есть сложность сортировки

вставками - квадратичная. ПУЗЫРЬКОВАЯ СОРТИРОВКА Метод пузырьковой сортировки последовательности a1, a2, , an представляет собой систематический обмен местами слева направо смежных элементов, не отвечающих выбранному порядку, до тех пор, пока они не оказываются на правильном месте. Большие элементы при этом как бы всплывают пузырьками вверх в конец списка. В привед нном ниже алгоритме используется переменная b, значение которой содержит число ещ не отсортированных

элементов b n while b! 0 t 0 for j 1 j lt b j if a j gt a j 1 w a j a j a j 1 a j 1 w t j b t Сложность данного алгоритма определяется числом проверок условия a j gt a j 1 в цикле и является квадратичной O n2 . Число реально проделанных сравнений существенно зависит от первоначального расположения элементов массива. Рассмотренный ниже другой алгоритм так называемой полной пузырьковой сортировки является наиболее популярным и легко программируемым е вариантом. for i 1 i lt n i for j 1 j lt n-i j if a j gt a j 1

w a j a j a j 1 a j 1 w Сложность привед нного алгоритма определяется числом сравнений a j gt a j 1 . Она оста тся постоянно равной n n-1 2 то есть квадратичной и не зависит от расположения исходных данных. ЗАКЛЮЧЕНИЕ Основываясь на результатах среднего числа сравнений можно сделать вывод, что сортировка вставками эффективнее пузырьковой сортировки. Это видно и из графика приведенного ниже СПИСОК ЛИТЕРАТУРЫ 1. Лекции по курсу Алгоритмизация и программирование.

Структуры и алгоритмы компьютерной обработки данных . 2. Б.Н. Иванов Дискретная математика. Алгоритмы и программы Учеб. пособие. Владивосток Изд-во ДВГТУ, 2000.