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

1.

Анализ алгоритмов
сортировки данных
Выполнил: Шебалов Е.А

2.

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

3.

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

4.

Сортировка и её виды
Алгоритм сортировки — это алгоритм для упорядочивания элементов
в массиве.
Два основных типа упорядочения:
Внутренняя сортировка (англ. internal sort) — оперирует массивами,
целиком помещающимися в оперативной памяти с произвольным
доступом к любой ячейке. Данные обычно упорядочиваются на том же
месте без дополнительных затрат. В современных архитектурах
персональных компьютеров широко применяется подкачка и
кэширование памяти.
Внешняя сортировка – сортировка данных, расположенных на
периферийных устройствах (магнитные диски, ленты и т.п) и не
вмещающихся в оперативную память, то есть, когда применить одну из
внутренних сортировок невозможно.

5.

Методы сортировок
Сортировка пузырьком (англ. bubble sort) – это простейший и один из
самых известных алгоритмов сортировки. Идея заключается в
последовательном сравнении значений соседних элементов. Если
текущий элемент больше следующего, меняя их местами. Алгоритм
необходимо повторять до тех пор, пока массив не будет отсортирован.
Пример работы алгоритма представлен на рисунке 1.
Рисунок 1. Сортировка пузырьком

6.

Методы сортировок
Сортировка выбором – идея метода состоит в том, чтобы создавать
отсортированную последовательность путем присоединения к ней
одного элемента за другим в правильном порядке. Будем строить
готовую последовательность, начиная с левого конца массива.
Алгоритм состоит из n последовательных шагов, начиная от нулевого и
заканчивая (n-1)-ым. На i-м шаге выбираем наименьший из элементов
a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при
n=6 изображена на рисунке ниже представлен на рисунке 2.
Рисунок 2. Сортировка выбором

7.

Методы сортировок
Вне зависимости от номера текущего шага i, последовательность
a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом,
на (n-2)-ом шаге вся последовательность, кроме a[n-1] оказывается
отсортированной, а a[n-1] стоит на последнем месте по праву: все
меньшие элементы уже ушли влево.

8.

Методы сортировок
Сортировка простыми вставками чем-то похожа на вышеизложенные
методы. Аналогичным образом делаются проходы по части массива, и
аналогичным же образом в его начале "вырастает" отсортированная
последовательность. Однако в сортировке пузырьком или выбором
можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на
правильных местах и никуда более не переместятся. Здесь же
подобное утверждение будет более слабым: последовательность
a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее могут
вставляться все новые элементы. Будем разбирать алгоритм,
рассматривая его действия на i-м шаге. Последовательность к этому
моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную
a[i+1]...a[n]. На следующем, (i+1)-ом каждом шаге алгоритма берем a[i+1] и
вставляем на нужное место в готовую часть массива.

9.

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

10.

Методы сортировок
Сортировка слиянием – алгоритм сортировки, который упорядочивает
списки (или другие структуры данных, доступ к элементам которых
можно получать только последовательно, например — потоки) в
определённом порядке. Эта сортировка — хороший пример
использования принципа «разделяй и властвуй». Сначала задача
разбивается на несколько подзадач меньшего размера. Затем эти
задачи
решаются
с
помощью
рекурсивного
вызова
или
непосредственно, если их размер достаточно мал. Наконец, их решения
комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки есть три этапа:
1.Сортируемый массив разбивается на две части примерно
одинакового размера;

11.

Методы сортировок
2. Каждая из получившихся частей сортируется отдельно, например —
тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в
один.
Пример работы алгоритма представлен на рисунке 4.
1
2
3
4
5
6
7
Рисунок 4. Сортировка слиянием