Второй класс задач.
Примерами подобной обработки служат: замена значений некоторых элементов на другие в соответствии с определенными условиями, сортировка массивов по убыванию, возрастанию, и по любому другому признаку, перестановки и сдвиги различного характера и др. Особенностью этого класса задач является то, что несмотря на постоянство количества элементов массива, для перестановки или замены элемента сначала его необходимо найти. Таким образом, чтобы преобразовать массив, требуется несколько раз его просмотреть. Поэтому даже для одномерного массива требуется применение нескольких вложенных циклов. Рассмотрим несколько типовых приемов.
Пример1. Пусть необходимо заменить все отрицательные элементы массива на нулевые
Пример 2. Переформировать массив таким образом, чтобы сначала шли все положительные элементы, затем отрицательные и в конце - нулевые.
Однако, наиболее распространенными задачами второго класса являются сортировки массивов. В силу важности, рассмотрим их отдельно.
Сортировка массивов
Сортировка – это изменение положения элементов в массиве таким образом, что элементы становятся упорядоченными по некоторому закону. Для любого алгоритма оценивается вычислительная сложность, которая определяется зависимостью времени сортировки от количества сортируемых элементов. Чем меньше это время, тем более эффективен алгоритм. Кроме того, на практике интересны такие методы сортировки, которые позволяют экономно использовать оперативную память. Поэтому рассмотрим только такие алгоритмы, в которых не предполагается использование дополнительных массивов.
Сортировка с помощью выбора
Сортировка с помощью выбора представляет собой один из самых простых методов сортировки. Он основан на следующих принципах:
Выбирается наименьший элемент из всего массива.
Найденный наименьший элемент меняется местами с первым элементом.
Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент массива.
Пример алгоритма с помощью выбора приведен на рисунке 5.1
Рис. 5.1
Сортировка с помощью обмена
Алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов. Сравнения продолжают до тех пор, пока не будут упорядочены все элементы. Такой метод широко известен под именем «пузырьковая сортировка», т.к.элементы массиваможно рассматривать как пузырьки, которые поднимаются к началу массива.
Пусть, например, массив состоит из элементов (2, 5, 12, 1, 8, 4). Если сортировать массив по возрастанию, то после первого «прохода» по массиву мы получим следующий массив (2, 5, 1, 8, 4, 12). После второго «прохода» - (2, 1, 5, 4, 8, 12), после третьего – (1, 2, 4, 5, 8,12).
В своем простейшем виде алгоритм сортировки с помощью обмена представлен на рисунке 5.2.
Для улучшения алгоритма можно не только запоминать были ли перестановки в процессе некоторого прохода, но и место последнего обмена. Ясно, что все пары соседних элементов больше этого элемента уже находятся в желаемом порядке. Поэтому просмотры можно заканчивать на этом индексе.
Сортировка методом вставки
Алгоритм сортировки с помощью вставки можно описать следующим образом. При каждом шаге, начиная с i=2, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность на нужное место. В реальном процессе поиска подходящего места удобно сначала сравнивать извлеченный элемент с очередным элементом aj, а затем либо ajсдвигается вправо, либо ai вставляется на освободившеесяместо. Процесс поиска может закончиться при выполнении одного из двух следующих условий: либо найден элемент aj меньший, чем ai, либо достигнут левый конец массива.
Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом «барьера». Для этого необходимо расширить диапазон индекса в описании массива от 0 до n. Алгоритм сортировки приводится на рисунке 5.3.
Рис.5.2
Рис. 5.3
Метод Шелла
Метод состоит в том, что упорядочиваемый массив разделяется на группы таким образом, что в каждой группе находятся элементы, отстоящие друг от друга на расстоянии d. Каждая группа сортируется методом вставки, затем массив делится на новые группы с шагом d-1 и т.д. пока количество групп не станет равным единице. Обычно d выбирается таким образом, чтобы в каждой группе находилось два элемента, т.е. d=[n/2].