Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования(Понятие данных и массивов данных).pdf

ВВЕДЕНИЕ

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

Алгоритмы устойчивой сортировки; алгоритмы неустойчивой сортировки; непрактичные алгоритмы сортировки; алгоритмы, не основанные на сравнениях и алгоритмы топологической сортировки – это наиболее популярные алгоритмы, которые мы решили рассмотреть. Составляющие, с наличием комплекта нескольких равных данных, в отсортированном наборе сохраняются в том же порядке, как и в исходном наборе при помощи алгоритмов устойчивой (стабильной) сортировки. Таким образом, имея одинаковые ключи, сравнительный порядок сортируемых составляющих не меняется сравнительной сортировкой. К числу алгоритмов устойчивой сортировки относятся сортировка пузырьком, сортировка смешиванием (шейкерная, гномья сортировка, сортировка вставками, сортировка слиянием, сортировка с использованием двоичного дерева, метод сортировки Тима Петерса, сортировка подсчётом, блочная сортировка (корзинная сортировка) и ряд других. При сортировке по одному полю данных, которые состоят из нескольких полей, сохранение их взаимного месторасположения равных элементов принципиально – это одно из совокупных преимуществ алгоритмов устойчивой сортировки. [4]

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

Объект: возможности различных методов сортировки данных.

Предмет: программирование с использованием методов сортировки данных.

Цель курсовой работы – разработать программу, реализующую основные методы сортировки данных.

Для достижения указанной цели потребуется решить ряд задач:

1. Изучить данные, виды данных и методы их сортировки.
2. Рассмотреть возможности среды Lazarus для реализации программы сортировки.
3. Разработать программу, реализующую сортировку массивов при решении задач в среде разработки Lazarus.

---

Глава 1. Общая характеристика методов сортировки данных

1.1. Понятие данных и массивов данных

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

После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки.

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

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

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

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

---

Размерностью элементов массива является количество составляющих индексов.

Массивы называются двумерными, индекс которых равен двум. Где номер строки соответствует первому индексу, а номер ячейки в строке (номер столбца) - второму индексу, именно в виде такой таблицы оформляются двумерные массивы.

Одномерные массивы и двумерные массивы в программировании используются чаще всего.

Значения соответствующих элементов массива, которые будут храниться в выделенной нами памяти, а так же при помощи ключевого слова МАССИВ [20] указываем размерность и его имя – все это необходимо нам, чтобы объявить массив.

Пример 1:

массив В [20]

В данном примере будет объявлен одномерный массив В, состоящий из 20 соответствующих элементов.

Пример 2:

массив Р [8,6]

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

Ограничение на размер одномерного массива - 1000 элементов, для двумерных - 1000х1000. Чтобы время обработки не затягивалось, преследуя учебные цели, массивы более чем из 500 элементов лучше не применять. Все массивы в Game Logo имеют числовой тип (действительные числа).

Работа с массивами. После того, как мы объявили массив, каждый его элемент можно обработать, указав личный номер (имя) массива и индекс элемента в квадратных скобках. К примеру, запись Т [2] позволяет адресоваться ко второму элементу массива Т.

При работе с двумерным массивом указываются два индекса. К примеру, запись M [3,4] делает доступным для обработки значение элемента, оказавшегося в третьей строке четвертого столбца массива M.

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

Присваивание значений элементам массива.

А[5] = 13

Пятому элементу массива А будет присвоено значение 13.

М[2,4] = 25

Элементу массива М, находящемуся во второй строке четвертого столбца, будет присвоено значение 25.

При помощи команды СПРОСИ можно ввести в элемент массива.

спроси А[5]

Загрузка данных в массив. Команда ЗАГРУЗИ вводит данные в массив.

Примеры для одномерного массива А.

загрузи в A

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

---

конец загрузки

загрузи в A

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

конец загрузки

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

Пример для двумерного массива В.

загрузи в В

15	17	25	36	24	56	78	56	36	24
56	78	56	36	24	15	17	25	36	25
15	17	25	36	24	56	78	56	36	24
78	56	36	24	15	17	17	25	36	25
36	24	56	78	24	56	78	56	36	24
39	78	56	36	24	25	15	15	89	71
15	17	25	36	24	56	78	56	36	24
78	56	36	24	15	17	17	25	36	25
36	24	56	78	24	56	78	56	36	24
39	78	56	36	24	25	15	15	89	71

---

конец загрузки

Заполнение массива случайными числами. Используя цикл, можно заполнить массив случайными числами.

Пример заполнения элементов массива А псевдослучайными целыми числами в диапазоне от 10 до 99:

массив А[100]

переменная х

повторить для х = 1 до 100 {А[х] = Int(случайное * 89) + 10}

Вывод значений элементов массива

ПИШИ A[3]

Значение третьего элемента одномерного массива А будет выводиться на экран.

ПИШИ# A

Будут выведены значения всех элементов массива А.

Знак # в команде ПИШИ выводит массив полностью. Для одномерных массивов вывод осуществляется с переносом строк. Для двумерных - как есть в виде таблицы, вследствие этого вероятен выход за пределы поля.

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

ТОЧКА# <имя массива> [, <координата х>, <координата у>]

В скобки взяты необязательные параметры <координата х> и <координата у>. Они обеспечивают отступ от начала координат (верхнего левого угла).

Пример:

точка# M, 150, 50

Замена и копирование значений в массивах. Команда для замены во всем массиве одного значения на другое.

заменить в <имя массива> <число1> на <число2>

Команда для копирования всех значений одного массива в иной массив. Численность составляющих и размерность массивов должны совпадать.

копировать <имя массива> в <имя массива> [1]

Далее рассмотрим методы сортировки массивов.

Расположением элементов по возрастанию (или убыванию) называется сортировкой или же упорядочением массива. Говорят о неубывающем (или невозрастающем) порядке в том случае, если не все элементы различны.

1.2. Общая характеристика методов сортировки данных

Количество используемых индексов массива может быть различным: массивы с одним индексом называют одномерными, с двумя — двумерными, и т. д. Одномерный массив — нестрого соответствует вектору в математике; двумерный («строка», «столбец»)— матрице. Чаще всего применяются массивы с одним или двумя индексами; реже — с тремя; ещё большее количество индексов — встречается крайне редко.

---