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

Оглавление

Введение……………………………………………………………………….3

• Теоретическая часть…………………………………………………………5
1. Понятие алгоритма……………………………………………………..5
2. Оценка алгоритма сортировки………………………………………...6
3. Сортировка пузырьком………………………………………………...8
4. Сортировка перемешиванием…………………………………………9
5. Сортировка методом вставок………………………………………...10
6. Блочная сортировка…………………………………………………..11
7. Сортировка подсчетом………………………………………………..13
8. Сортировка слиянием………………………………………………...13
9. Двоичное дерево……………………………………………………...14
10. Цифровая сортировка………………………………………………...15
11. Гномья сортировка……………………………………………………15
12. Сортировка методом выбора…………………………………………16
13. Сортировка методом Шелла…………………………………………16
14. Сортировка расчёской………………………………………………..16
15. Пирамидальная сортировка………………………………………….17
16. Быстрая сортировка…………………………………………………..18
17. Блинная сортировка…………………………………………………..19
• Практическая часть………………………………………………………...20

• Описание алгоритма решения задачи……………………………….22

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

 

 

 

 

 

 

 

 

Введение

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

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

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

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

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

Алгоритм  сортировки  выбором  более эффективная   сортировка   обменами   за критерием  М(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).

 

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

1.1 Понятие  алгоритма

 

Алгоритм – система  точно сформулированных правил, определяющих процесс преобразование доступных  исходных данных (входной информации) в желаемый результат (выходную информацию) за конечное число шагов [2, С 89].

Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает,  что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировка - это процесс упорядочения некоторого множества элементов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т.п.) в последовательности объектов необходимо для удобства работы с этим объектом [1, С 238 - 239]. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.

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

         1.2. Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются  по скорости выполнения и эффективности  использования памяти:

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

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

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

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

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

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

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

Алгоритмы сортировки данных

Список алгоритмов сортировки:

• Алгоритмы устойчивой сортировки:

• Сортировка пузырьком (Обменная сортировка)
• Сортировка перемешиванием (Сортировка коктейлем)
• Сортировка методом вставок
• Блочная сортировка (Корзинная сортировка)
• Сортировка подсчетом 
• Сортировка слиянием
• Двоичное древо 
• Цифровая сортировка (Сортировка по отделениям) 
• Поразрядная сортировка 
• Гномья сортировка

• Алгоритмы неустойчивой сортировки:

• Сортировка методом выбора 
• Сортировка методом Шелла 
• Сортировка расчёской
• Пирамидальная сортировка (Сортировка кучи) 
• Плавная сортировка
• Быстрая сортировка

• Непрактичные алгоритмы сортировки:

• Сортировка Акульшина
• Глупая сортировка
• Блинная сортировка

Существует множество  методов сортировки, каждый из которых  имеет свои достоинства и недостатки. Рассмотрим некоторые из них:

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

Является наиболее известным  методом сортировки. Алгоритм попарного сравнения элементов массива в литературе часто называют "методом пузырька", проводя аналогию с пузырьком, поднимающимся со дна бокала с газированной водой. По мере всплывания пузырек сталкивается с другими пузырьками и, сливаясь с ними, увеличивается в объеме. Чтобы аналогия стала очевидной, нужно считать, что элементы массива расположены вертикально друг над другом, и их нужно так упорядочить, чтобы они увеличивались сверху вниз.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.1. Демонстрация сортировки по неубыванию методом "пузырька".

 

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку  два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет 
сравнений, где n – количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n-1 раз, а внутренний выполняется в среднем n/2 раз [3, С 217].

Пузырьковая сортировка имеет такую особенность: неупорядоченные  элементы на "большом" конце массива  занимают правильные положения за один проход, но неупорядоченные элементы в начале массива поднимаются на свои места очень медленно. Поэтому, вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления. Таким образом, элементы, сильно удаленные от своих положений, быстро станут на свои места. Данная версия пузырьковой сортировки носит название шейкер-сортировки (shaker sort сортировка перемешиванием, сортировка взбалтыванием, сортировка встряхиванием), поскольку действия, производимые ею с массивом, напоминают взбалтывание или встряхивание.