Некоторые рекомендации при работе со статическим массивом

Признаки порядка

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

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

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

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

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

Для реализации алгоритма любого способа сортировки требуется прохождение не менее двух вложенных циклов.

Одномерный массив А(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

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

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

a_i^’ = min(max){a_j , j=i, i+1, …, n}, i=1, …, n-1

где n – размерность массива

3. Сортировка простыми вставками заключаетсяв том, что для i = 2, 3, …, n каждый элемент a_i переставляется в нужное место среди упорядоченных ранее элементов a₁, a₂, …, a_i-1, раздвигая их за счет удаления a_i.

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

· При обработке массивов рекомендуется использовать вывод на экран всего введенного массива в наглядной форме для визуального контроля правильности ввода и демонстрации соответствия результатов введенным данным.

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

· В задачах на анализ или поиск в заданном массиве не следует искажать массив в своих целях.

· Если требуется найти фрагмент массива (цепочку элементов), обладающий каким-либо свойством, то следует в качестве результата показать не только сам фрагмент, но и его местоположение (индексы первого и последнего элементов фрагмента) в массиве.

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

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