Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки»




Скачать 288.54 Kb.
НазваниеКурсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки»
страница1/4
Дата публикации23.06.2013
Размер288.54 Kb.
ТипКурсовая
lit-yaz.ru > Информатика > Курсовая
  1   2   3   4


ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ

ИНСТИТУТ


КУРСОВАЯ РАБОТА

по дисциплине «Информатика»

на тему «Алгоритмы сортировки»

Исполнитель:

Руководитель:
Тула 2007г

Оглавление:
Введение…………………………………………………………………………..3

1.Теоретическая часть:

1.1 Алгоритмы сортировки:

1.1.1 Сортировка пузырьком…………………………………………………….10

1.1.2 Сортировка перемешиванием ……………………………………………....11

1.1.3 Сортировка методом вставок ……………………………………………...11

1.1.4Сортировка подсчётом.…………………………………………………......12

1.1.5Сортировка слиянием……………………………………………………....12

1.1.6Цифровая сортировка……………………………………………………....13

1.1.7Поразрядная сортировка ……………………………………………….......14

1.1.8Сортировка методом выбора ………………………………………….........15

1.1.9Сортировка методом Шелла …………………………………………...….15

1.1.10Пирамидальная сортировка………………………………………..……..17

1.1.11Быстрая сортировка……………………………………………………..18
2. Практическая часть:

2.1 Практическое задание №7...…………….….………………………………20

2.2Алгоритм выполнения практического задания………………………….…..21

Список использованной литературы…………………..………………..23

Приложения………………………………………………..……………....24


Введение
В наше время новые информационные технологии занимают очень важное место не только в специализированных, но и в повседневных сферах жизни. Компьютеры применяются в бизнесе, менеджменте, торговле, учебе и многих других сферах деятельности человека.

Компьютерные технологии очень удобны для выполнения разнообразных операций, но в разных сферах применения эти операции разные. Потому, каждая отдельная отрасль, которая использует специфические технические средства, нуждается в своих собственных программах, которые обеспечивают работу компьютеров.

Разработкой программного обеспечения занимается такая отрасль науки, как программирование. Она приобретает все большее и большее значение в последнее время, ведь с каждым днем компьютер становится все более необходимым, все более повседневным явлением нашей жизни. Ведь вычислительная техника прошлых лет уже почти полностью исчерпала себя и не удовлетворяет тем потребностям, которые появляются перед человечеством.

Таким образом, новые информационные технологии очень актуальны в наше время и нуждаются в большем внимании для последующей разработки и совершенствования. Рядом с этим, большое значение имеет также и программирование, которое является одним из фундаментальных разделов информатики и потому не может оставаться в стороне.

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

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

Задача сортировки в программировании не решена полностью. Ведь, хотя и существует большое количество алгоритмов сортировки, все же целью программирования является не только разработка алгоритмов сортировки элементов, но и разработка именно эффективных алгоритмов сортировки. Мы знаем, что одну и ту же задачу можно решить с помощью разных алгоритмов, и каждый раз изменение алгоритма приводит к новым, более или менее эффективным решениям задачи. Основными требованиями к эффективности алгоритмов сортировки является, прежде всего, эффективность по времени и экономное использование памяти. Согласно этим требованиям, простые алгоритмы сортировки (такие, как сортировка выбором и сортировки включением) не являются очень эффективными.

Алгоритм сортировки обменами, хотя и завершает свою работу (поскольку он использует лишь циклы с параметром и в теле циклов параметры принудительно не изменяются) и не использует вспомогательной памяти, но занимает много времени. Даже, если внутренний цикл не содержит ни одной перестановки, то действия будут повторяться до тех пор, пока не завершится внешний цикл.

Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.

Целью теоретической части курсовой работы является ознакомление с алгоритмами сортировки, попытка проанализировать их и осветить каждый из них.
Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления курсовой работы:

  • Процессор: INTEL PENTIUM 4 1.7 GHz;

  • Оперативная память: SD RAM 256mb;

  • Жесткий диск: HDD 40Gb;

  • Видеокарта: ATI RADEON 9600pro;

  • Клавиатура: Logitech G15;

  • Мышь: Logitech G9.


Программные средства: операционная система Windows ХР Professional sp2, пакет прикладных программ – MS Office 2003(из него использованы для выполнения курсовой работы: текстовый процессор MS Word 2003 табличный процессор MS Excel2003).

^ Алгоритмы сортировки
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.
^ Оценка алгоритма сортировки

Для того, чтобы обоснованно сделать такой выбор, рассмотрим параметры, по которым будет производиться оценка алгоритмов.

  • ^ Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это Ω(n²). Идеальное поведение для сортировки — O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в Ω(n log n) сравнениях в среднем;

  • Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

  • Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.

  • ^ Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

  • ^ Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.

  • ^ Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

    • доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим

    • объём данных не позволяет им разместиться в ОЗУ
  1   2   3   4

Добавить документ в свой блог или на сайт

Похожие:

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине «Информатика» на тему «Обмен данными в ms office»
Курсовая работа «Обмен данными в ms office» содержит 27 страниц печатного текста, 4 рисунка, 5 таблиц, использовано 5 источников

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине: «Информатика» на тему «Сетевые возможности ос ms windows»
Результаты выполнения контрольного примера в расчётном и формульном виде

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине «Информатика» на тему «Принципы, технологии, протоколы Интернет»
Проектирование форм выходных документов и графическое предоставление данных

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине: «Информатика» на тему «Архитектура современного пк»
Всероссийский заочный финансово-экономический институт Кафедра автоматизированной обработки экономической информации

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине «Информатика» на тему «Тенденции развития Интернет»
Основные черты Интернет-права как регулятора новых общественных отношений

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине «Информатика» На тему: «Использование...
«Информатика» На тему: «Использование пакетов прикладных программ в экономической деятельности»

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая Работа по дисциплине «Информатика» на тему «История развития криптографии»
Криптография тайнопись, специальная система изменения обычного письма, используемая с целью сделать текст понятным лишь для ограниченного...

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине «Математическая Логика» на тему: «Алгоритмы и автоматы»
Некоторые из таких, казалось бы, абсолютно бесполезных конструкций, изученных в прошлом, пришлись весьма кстати сейчас; другие все...

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине: «Информатика» на тему: «Настольные субд»
Наиболее популярной формой представления данных в компьютере является база данных – множество взаимосвязанных данных, структурированных...

Курсовая работа по дисциплине «Информатика» на тему «Алгоритмы сортировки» iconКурсовая работа по дисциплине “Информатика” на тему: «Этапы электронного...
Конечно, люди имеют неоспоримые интеллектуальные преимущества перед компьютером, но ведь компьютеры – это порождение высокоразвитого...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница