Перестановка наоборот (инверсия)

Инверсия (от английского inverse – обратный) – это такая перестановка, когда первый

элемент становится последним, второй – предпоследним и т.д.

Эта простая задача имеет один подводный камень. Пусть размер массива N. Тогда элемент

A[0] надо переставить с A[N-1], A[1] с A[N-2] и т.д. Заметим, что в любом случае сумма

индексов переставляемых элементов равна N-1, поэтому хочется сделать цикл от 0 до N-1, в котором переставить элементы A[i] с A[N-1-i]. Однако при этом вы обнаружите, что массив не изменился. Обратим внимание, что перестановка затрагивает одновременно и первую, и вторую половину массива. Поэтому сначала все элементы будут переставлены правильно, а затем (когда i> N/2) будут возвращены на свои места. Правильное решение – делать перебор, при котором переменная цикла доходит только до середины массива.

Циклический сдвиг

При циклическом сдвиге (вправо) первый элемент переходит на место второго, второй на

место третьего и т.д., а последний элемент – на место первого.

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

Сортировка массивов

Сортировка – это расстановка элементов некоторого списка в заданном порядке.

Существуют разные виды сортировки (по алфавиту, по датам и т.д.), они отличаются лишь

процедурой сравнения элементов. Мы рассмотрим простейший вариант сортировки – расстановку элементов массива в порядке возрастания.Программисты придумали множество методов сортировки. Они делятся на две группы:

• понятные, но не эффективные

• эффективные, но непонятные (быстрая сортировка и т.п.).

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

Метод пузырька

Название этого метода произошло от известного физического явления – пузырек воздуха

в воде поднимается вверх. В этом методе сначала поднимается «наверх» (к началу массива) самый «легкий» элемент (минимальный), затем следующий и т.д.

Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно, то

меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать

При следующем проходе наша задача – поставить на место элемент A[1]. Делаем это так же,но уже не рассматриваем A[0], который стоит на своем месте. Сделав N-1 проходов, мы установим на место элементы с A[0] по A[N-2]. Это значит, что последний элемент, A[N-1], уже тоже стоит на своем месте (другого у него нет).

Метод пузырька работает медленно, особенно на больших массивах. Можно показать, что при увеличении размера массива в 10 раз время выполнения программы увеличивается в 100 раз(метод имеет порядок N2). К сожалению, все простые алгоритмы сортировки имеют такой(квадратичный) порядок.