Способы сортировки в массивах данных

Линейный поиск в массивах данных

Массив как статическая структура данных

Статические структуры данных.

Фундаментальная (статическая) структура данных – это набор элементов базового представления данных, из которых строятся более сложные структуры; является совокупностью фиксированного количества данных постоянной размерности с неизменным характером связей между ними.

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

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

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

Массив как статическая структура обладает следующими свойствами:

· имеет описание, и обращение осуществляется по имени;

· память выделяется на этапе компиляции;

· объем памяти фиксирован и не меняется в процессе выполнения программы.

Массивы могут быть одномерными и многомерными.

Одномерный массив – это массив, для получения доступа к элементам которого достаточно одной индексной переменной; математическим представлением является вектор.

Многомерный массив – это массив, для получения доступа к элементам которого требуется более одной индексной переменной; математическим представлением является матрица.

Частный случай многомерного массива – двумерный массив, математическое представление которого – это двумерная матрица.

В задачах на линейный поиск требуется найти в массиве данных элемент, группу элементов (или фрагмент массива), которая отвечает заданным требованиям; как правило, нет необходимости сортировать массив или выделять дополнительные рабочие массивы того же порядка, что и заданный.

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

Признаки порядка для упорядочения массива А(n):

по возрастанию, если для любого i = 2, 3, …, n a_i > a_i-1

по неубыванию, если для любого i = 2, 3, …, n a_i ≥ a_i-1

по убыванию, если для любого i = 2, 3, …, n a_i < a_i-1

по невозрастанию, если для любого i = 2, 3, …, n a_i ≤ a_i-1