Перестановка элементов массива местами

Перестановка элементов массива

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

Обмен двух элементов

Чтобы поменять местами элементы с индексами i и j, поступают так же, как с обычными переменными:

c := a[i]; a[i] := a[j]; a[j] := c

Здесь a[i] и a[j] играют роль двух переменных, а c временно хранит значение, чтобы оно не потерялось.

Переворот массива

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

Разбор примера

Для массива из n элементов с индексами от 1 до n переворот выполняет цикл, где счётчик i идёт от 1 до n/2, и на каждом шаге меняются местами a[i] и a[n+1-i]. Так первый встаёт на место последнего, второй — на место предпоследнего.

Частые ошибки. Прогоняют цикл до конца массива, и переворот «отменяется». Забывают вспомогательную переменную и теряют значение элемента. Ошибаются в формуле парного индекса — пишут n - i вместо n + 1 - i при нумерации с единицы.

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

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

Зачем нужны перестановки

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

Кратко о главном

• Элементы массива меняют местами через вспомогательную переменную.
• Обмен a[i] и a[j] аналогичен обмену обычных переменных.
• Переворот массива меняет первый с последним, второй с предпоследним и т. д.
• Цикл переворота идёт только до середины массива.
• Парный элемент к a[i] при нумерации с 1 — это a[n+1-i].