Читать онлайн «Методы сортировок и их реализации: Методические указания к выполнению лабораторных работ»

И. В. Беляева К. с. Беляев МЕТОДЫ СОРТИРОВОК И их РЕАЛИЗАЦИИ Ульяновск 2006  Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный техниический университет МЕТОДЫ СОРТИРОВОК И ИХ РЕАЛИЗАЦИИ методические указания к выполнению лабораторных работ по программированию для студентов направлений 23010062 «Информатика и вычислительная техника и специальности 230 1о 165«Вычислительные машины, комплексы, системы и сети» Составители: и. В. Беляева К. С. Беляев Ульяновск 2006 УДК 681. 3(076) ББК 32. 973я7 М54 Рецензент кандидат технических наук, профессор, декан ФИСТ В. В. Шишкин Одобрено секцией методических пособий научно-методического совета университета Методы сортировок и их реализации: методические указания к М54 выполнению лабораторных работ / сост. и. В. Беляева, К. с. Беляев. ­ Ульяновск: УлГТУ, 2006. - 48 с. Рассмотрены алгоритмы сортировок и их реализация на языке С++. В данном методическом указании освещены следующие методы сортировок: методом выбора, метода пузырька, методом вставок, методом слияния и быстрая сортировка. Подробно рассмотрены вопросы оценки эффективности алгоритмов с использованием нотации О ­ большое. В методическое указание включены задания для лабораторной работы «Методы сортировок» . Методические указания могут быть использованы студентами младших курсов, изучающими дисциплины «Информатика», «Программирование на языках высокого уровня» при изучении темы «Методы сортировок» и при выполнении практических и лабораторных работ по этой теме. Методические указания также могут использоваться учащимися школ при изучении соответствующих тем школьного курса «Информатика». Работа подготовлена на кафедре ВТ. УДК 681. 3(076) ББК 32. 973я7 © и. В. Беляева, К. с. Беляев, составление, 2006 © Оформление. УлГТУ, 2006 ОГЛАВЛЕНИЕ ВВЕдЕНИЕ 4 ИЗМЕРЕНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ 5 БЫСТРОДЕЙСТВИЕ АЛГОРИТМОВ 6 СТЕПЕНЬ РОСТА ВРЕМЕННЫХ зАТРАТ 7 ОЦЕНКА ПОРЯДКА ВЕЛИЧИНЫ И ОБОЗНАЧЕНИЕ О-БОЛьшОЕ 8 ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ ПОИСКА 14 АЛГОРИТМЫ СОРТИРОВКИ И ИХ ЭФФЕКТИВНОСТЬ 15 СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА 19 СОРТИРОВКА МЕТОДОМ ВСТАВОК 22 СОРТИРОВКА СЛИЯНИЕМ 24 БЫСТРАЯ СОР'ТИРОВКА 30 СРАВНЕНИЕ АЛГОРИТМОВ СОРТИРОВКИ 44 ЛАБОРАТОРНАЯ РАБОТА «МЕТОДЫ СОРТироВоК» 44 ЦЕЛЬ РАБОТы 44 ОБЩЕЕ ЗАДАНJ!IЕ 44 ВАРИАНТЫ 45 БИБЛИОГРАФИЧЕСКИЙ сПИСОК 48 3 Введение Развитие компьютерной техники, позволившее хранить и обрабатывать огромные объемы информации, вызвало необходимость в методах и средствах, обеспечивающих ее сортировку.