Алгоритмы сортировки. 2

Федеральное агентство по образованию

ГОУ ВПО

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

Кафедра прикладной информатики

Факультет менеджмент и маркетинг

Специальность менеджмент организации

Контрольная работа

по информатике

на тему

«алгоритмы сортировки»

Студент: Коновалова Надежда Васильевна

Курс 2   № группы 202

Личное дело № 08ММБ00284

Преподаватель: Савин Дмитрий Александрович

Москва – 2010

ОГЛАВЛЕНИЕ:

ВВЕДЕНИЕ

Глава 1 АЛГОРИТМЫ СОРТИРОВКИ

1.1 ОБЩАЯ ХАРАКТЕРИСТИКА АЛГОРИТМОВ СОРТИРОВКИ

1.2 ОСНОВНЫЕ ВИДЫ СОРТИРОВОК

1.2.1 Сортировка пузырьком

1.2.2 Сортировка перемешиванием

1.2.3 Сортировка методом вставок

1.2.4 Сортировка подсчетом

1.2.5 Сортировка слиянием

1.2.6 Сортировка методом выбора

1.2.7 Сортировка методом Шелла

1.2.8 Метод Хoopа

1.2.9 Цифровая сортировка

1.2.10 Поразрядная сортировка

1.2.11 Быстрая сортировка

Глава 2 ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Общая характеристика задачи

2.2 Алгоритм решения задачи

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

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

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

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

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

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

Глава 1 АЛГОРИТМЫ СОРТИРОВКИ

1.1 ОБЩАЯ ХАРАКТЕРИСТИКА АЛГОРИТМОВ СОРТИРОВКИ

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

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

Практически каждый алгоритм сортировки можно разбить на три части:

1)                 сравнение, определяющее упорядоченность пары элементов;

2)                 перестановку, меняющую местами пару элементов;

3)                 собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

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

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

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

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

•              Естественность поведения — эффективность метода при обработке уже

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

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

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

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

1.2 ОСНОВНЫЕ ВИДЫ СОРТИРОВОК

1.2.1 Сортировка пузырьком

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся не отсортированных N-1 элементов (т.е. для тех, которые лежат "ниже" первого). Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.

1.2.2 Сортировка перемешиванием

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

1.2.3 Сортировка методом вставок

Простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

                 прост в реализации

                 эффективен на небольших наборах данных

                 эффективен на наборах данных, которые уже частично отсортированы

                 это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

                 может сортировать список по мере его получения

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

1.2.4 Сортировка подсчетом

Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

Описание алгоритма:

Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

1.2.5 Сортировка слиянием

Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй».

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

1.2.6 Сортировка методом выбора

На этот раз при просмотре мaccива мы будем искать наименьший элемент, сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.

1.2.7 Сортировка методом Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в устранении  массового беспорядка в массиве, сравнивая далеко стоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми). Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.

Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 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. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.

1.2.8 Метод Хoopа

Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

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

1.2.9 Цифровая сортировка

Цифровая сортировка обладает линейной вычислительной сложностью, что является лучшей возможной производительностью для алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве устойчивой).

Алгоритм цифровой сортировки действует следующим образом:

1.                       Создаём массив изначально пустых «ячеек», по одной для каждой величины из диапазона ключей.

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

3.                       Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.

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

1.2.10 Поразрядная сортировка

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

1.2.11 Быстрая сортировка

Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.

Алгоритм:

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1.                 Выбираем в массиве некоторый элемент, который будем называть опорным элементом.

2.                 Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.

3.                 Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

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

При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n log n).

Глава 2 ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Общая характеристика задачи

ВАРИАНТ 19

1.Произвести расчет платежа по кредиту клиента банка (рис. 2.1). Ежемесячное погашение кредита осуществляется равными (аннуитетными) платежами.

Погашение основного долга определяется как отношение суммы кредита к количеству месяцев, на которые выдан кредит. Результаты округлить до целого, используя функцию ОКРУГЛ().

Сумма процентов определяется как произведение суммы текущего остатка по кредиту на процентную ставку в месяц. Процентная ставка в месяц равна отношению процентной ставки кредита к количеству месяцев, на который выдан кредит.

Сумма текущего остатка по кредиту определяется как разница между суммой предыдущего остатка по кредиту и текущей суммы погашения основного долга.

Платеж по кредиту определяется как сумма текущей суммы процента по кредиту и текущей суммы погашения основного долга.

2.Результаты округлить до целого, используя функцию ОКРУГЛ(). Для того, чтобы итоговая сумма погашения основного долга равнялась сумме выданного кредита, использовать функцию ЕСЛИ() для отражения остатков по платежу в последнем платеже.  Сумма последнего платежа по погашению основного долга будет больше, чем платежи за предыдущие месяцы.

По данным таблицы (рис. 2.1) построить гистограмму с отражением платежей по кредиту по месяцам.

Рис. 2.1. Платежи по кредиту клиента банка «Акцепт»

2.2 Алгоритм решения задачи

1.      Запустить табличный процессор MS Excel.

2.      Создать книгу с именем «Кредит в Банке».

3.      Лист 1 переименовать в лист с названием «Платежи».

4.      На рабочем листе «Платежи» MS Excel создать таблицу с базовыми данными  о платежах по кредиту клиента банка «Акцепт» за 2006 г.

Заполнить таблицу  с базовыми данными  о платежах по кредиту клиента банка «Акцепт» за 2006 г. ( рис.1)

Рис.1 Таблицу  с базовыми данными  о платежах по кредиту клиента банка «Акцепт» за 2006 г.

5.      Рассчитать сумму погашения основного долга и процентную ставку за месяц по формуле:

Сумма погашения = Сумма кредита/Кол-во месяцев, на которые выдан кредит (B5=B3/B2)

Процентная ставка = Годовая ставка/ Кол-во месяцев, на которые выдан кредит (B4=B1/B2)

Рис.2 Результаты были округлены до целого

6.      На рабочем листе «Платежи» MS Excel в таблице «Платежи по кредиту клиента банка «Акцепт» за 2006 г.» заполняем таблицу по формулам и округляем результаты до целого числа (рис.4)

Таким образом, получаем (рис.3)

Рис. 3 Заполненная таблица

Рис. 4 Округленные результаты

7.      По данным таблицы построена гистограмма с отражением платежей по кредиту по месяцам (рис. 5)

Рис. 5 Гистограмма с отражением платежей по кредиту по месяцам

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

ЗАКЛЮЧЕНИЕ

Современную жизнь представить без современной техники просто невозможно.

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

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

- собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1.                  Информатика: Методические указания по выполнению курсовой работы для самостоятельной работы студентов II курса (первое высшее образование). – М.: Вузовский учебник, 2006.

2.                  Информатика в экономике: Учеб.пособие/Под ред. проф. Б.Е. Одинцова, проф. А.Н. Романова. – М.: Вузовский учебник, 2008.

3.                  Википедия — свободная энциклопедия – www.ru.wikipedia.org

4.                  Леонтьев В. П. Новейшая энциклопедия персонального компьютера 2005. – М.: ОЛМА-ПРЕСС Образование, 2005.

5.                  Михеева Е. В. Практикум по информационным технологиям в профессиональной деятельности: Учебное пособие, 2-е изд., стер. – М.: Издательский центр «Академия», 2006.

6.                  Акулов О.А., Медведев Н.В. Информатика: базовый курс. – М.: Омега-Л, 2008.

21