Разворот массива: итеративные и рекурсивные подходы

Кратко: разворот массива меняет порядок элементов на обратный. Рассмотрены два базовых метода: итеративный (обмен пар элементов в цикле) и рекурсивный (обмен с шагом внутрь). Приведены примеры на C++, Python и JavaScript, сравнение сложностей, тесты и рекомендации для практического применения.

Введение

Массив — это коллекция элементов, расположенных подряд в памяти. Разворот массива (reverse) — распространённая операция: используется в алгоритмах, задачах на интервью и преобразованиях данных. В этой статье вы увидите реализацию разворота двумя способами: с помощью циклов и с помощью рекурсии. Для каждого подхода приведу пример кода, анализ сложности и практические заметки.

Примеры входа и ожидаемого результата

Пример 1: arr = [45, 12, 67, 63, 9, 23, 74] → [74, 23, 9, 63, 67, 12, 45]

Пример 2: arr = [1, 2, 3, 4, 5, 6, 7, 8] → [8, 7, 6, 5, 4, 3, 2, 1]

Итеративный подход

Задача

Дан массив arr. Нужно развернуть элементы массива и напечатать результат. Реализуйте решение с циклами.

Подход с использованием цикла

Шаги:

1. Инициализируйте два индекса: i = 0 и j = size-1.
2. Пока i < j, меняйте местами arr[i] и arr[j].
3. Увеличивайте i на 1 и уменьшайте j на 1.
4. Остановитесь, когда i >= j.

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

C++: разворот массива с помощью циклов

// C++ program to reverse the elements of an array using loops
#include 
using namespace std;

void reverseArr(int arr[], int size)
{
    for(int i = 0, j = size - 1; i < size / 2; i++, j--)
    {
        swap(arr[i], arr[j]);
    }
}

void printArrayElements(int arr[], int size)
{
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    int arr[] = {45, 12, 67, 63, 9, 23, 74};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array:" << endl;
    printArrayElements(arr, size);

    reverseArr(arr, size);

    cout << "Reversed array:" << endl;
    printArrayElements(arr, size);

    return 0;
}

Вывод:

Original Array:
45 12 67 63 9 23 74
Reversed array:
74 23 9 63 67 12 45

Python: разворот списка с помощью циклов

# Python program to reverse the elements of a list using loops

def reverseList(arr, size):
    i = 0
    j = size - 1
    while i < j:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

def printListElements(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()

# Driver Code
arr = [45, 12, 67, 63, 9, 23, 74]
size = len(arr)

print("Original Array:")
printListElements(arr, size)

reverseList(arr, size)

print("Reversed Array:")
printListElements(arr, size)

Вывод:

Original Array:
45 12 67 63 9 23 74
Reversed array:
74 23 9 63 67 12 45

JavaScript: разворот массива с помощью циклов

// JavaScript program to reverse the elements of an array using loops
function reverseArr(arr, size) {
    for (let i = 0, j = size - 1; i < size / 2; i++, j--) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

function printArrayElements(arr, size) {
    let out = "";
    for (let i = 0; i < size; i++) {
        out += arr[i] + " ";
    }
    console.log(out.trim());
}

// Driver Code
var arr = [45, 12, 67, 63, 9, 23, 74];
var size = arr.length;

console.log("Original Array:");
printArrayElements(arr, size);

reverseArr(arr, size);

console.log("Reversed Array:");
printArrayElements(arr, size);

Вывод в консоли:

Original Array:
45 12 67 63 9 23 74
Reversed array:
74 23 9 63 67 12 45

Рекурсивный подход

Задача

Дан массив arr. Нужно развернуть элементы массива и напечатать результат. Реализуйте решение с рекурсией.

Подход с использованием рекурсии

Шаги:

1. Инициализируйте два индекса: start = 0 и end = size-1.
2. Если start >= end — остановка рекурсии.
3. Меняем местами arr[start] и arr[end].
4. Рекурсивно вызываем функцию с start+1 и end-1.

Идея: каждый рекурсивный вызов обрабатывает одну внешнюю пару и сужает диапазон.

C++: разворот массива с помощью рекурсии

// C++ program to reverse an array using recursion
#include 
using namespace std;

void reverseArr(int arr[], int start, int end)
{
    if (start >= end)
    {
        return;
    }
    swap(arr[start], arr[end]);
    reverseArr(arr, start + 1, end - 1);
}

void printArrayElements(int arr[], int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main()
{
    int arr[] = {45, 12, 67, 63, 9, 23, 74};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array:" << endl;
    printArrayElements(arr, size);

    reverseArr(arr, 0, size - 1);

    cout << "Reversed array:" << endl;
    printArrayElements(arr, size);

    return 0;
}

Вывод:

Original Array:
45 12 67 63 9 23 74
Reversed array:
74 23 9 63 67 12 45

Python: разворот списка с помощью рекурсии

# Python program to reverse an array using recursion

def reverseList(arr, start, end):
    if start >= end:
        return
    arr[start], arr[end] = arr[end], arr[start]
    reverseList(arr, start + 1, end - 1)

def printListElements(arr, size):
    for i in range(size):
        print(arr[i], end=" ")
    print()

# Driver Code
arr = [45, 12, 67, 63, 9, 23, 74]
size = len(arr)

print("Original Array:")
printListElements(arr, size)

reverseList(arr, 0, size - 1)

print("Reversed Array:")
printListElements(arr, size)

Вывод:

Original Array:
45 12 67 63 9 23 74
Reversed array:
74 23 9 63 67 12 45

JavaScript: разворот массива с помощью рекурсии

// JavaScript program to reverse an array using recursion
function reverseArr(arr, start, end) {
    if (start >= end) {
        return;
    }
    [arr[start], arr[end]] = [arr[end], arr[start]];
    reverseArr(arr, start + 1, end - 1);
}

function printArrayElements(arr, size) {
    let out = "";
    for (let i = 0; i < size; i++) {
        out += arr[i] + " ";
    }
    console.log(out.trim());
}

var arr = [45, 12, 67, 63, 9, 23, 74];
let size = arr.length;

console.log("Original Array:");
printArrayElements(arr, size);

reverseArr(arr, 0, size - 1);

console.log("Reversed Array:");
printArrayElements(arr, size);

Вывод:

Original Array:
45 12 67 63 9 23 74
Reversed array:
74 23 9 63 67 12 45

Анализ сложности и памятка

Fact box — ключевые числа:

• Временная сложность: O(n) для обоих методов.
• Память: итеративный — O(1) дополнительной памяти; рекурсивный — O(n) глубина стека в худшем случае.
• Количество обменов: floor(n/2).

Когда выбирать метод:

• Используйте итеративный подход для больших массивов и в продуктивном коде — он экономит стек.
• Рекурсия подходит для учебных задач и если код читается легче с рекурсией, но следите за глубиной стековых вызовов.

Сравнение подходов

Когда метод не подходит

• Рекурсия может привести к переполнению стека для очень больших массивов (зависит от лимита стека в среде выполнения).
• Если массив неизменяем (например, кортежи в некоторых языках), требуется создать новый массив вместо in-place обменов.
• Для потокобезопасности в многопоточной среде нужно синхронизировать доступ к общему массиву.

Альтернативные подходы

• Встроенные функции: std::reverse в C++, list.reverse() или reversed() в Python, Array.prototype.reverse() в JavaScript.
• Создать новый массив и копировать элементы в обратном порядке (полезно для неизменяемых структур).
• Использовать срезы в Python: arr[::-1] — кратко и быстро для большинства задач.

Тесты и критерии приёмки

Тестовые случаи:

1. Пустой массив → пустой массив.
2. Массив из одного элемента → тот же элемент.
3. Чётная длина и нечётная длина.
4. Массив с повторяющимися значениями.
5. Большой массив (проверка на производительность).

Критерии приёмки:

• Выходной массив содержит те же элементы в обратном порядке.
• Решение работает за O(n) времени.
• Для in-place реализации — дополнительная память O(1).

Контрольный список по ролям

Для разработчика:

• Реализовать in-place обмен или вернуть новый массив при необходимости.
• Добавить юнит-тесты для перечисленных случаев.
• Обработать пустые и некорректные входные данные.

Для человека на интервью:

• Объяснить временную и пространственную сложность.
• Спросить про ограничения: размер массива, возможность in-place изменений.
• При необходимости привести оба варианта кода.

Для преподавателя:

• Показать пример с рекурсией и объяснить стек вызовов.
• Сравнить с встроенными методами языка.

Мини-методология для быстрой реализации

1. Проверить длину: если size < 2, вернуть как есть.
2. Установить i = 0, j = size - 1.
3. Пока i < j: обмен и i++, j–.
4. Вернуть результат или напечатать.

Частые ошибки и как их избежать

• Ошибка: использовать условие i < size/2 вместо i < j. Решение: сравнивайте индексы i и j.
• Ошибка: неправильные границы при подсчёте размера — используйте надежный способ len/sizeof.
• Ошибка: не учитывать неизменяемые структуры — создавайте новый массив.

Важно: рекурсивный подход читабелен, но требует аккуратности для больших входных данных из‑за лимита стека.

Короткие шаблоны для документации

SOP для внедрения разворота в кодовой базе:

1. Определить требования (in-place или новый массив).
2. Выбрать метод (итеративный или встроенная функция).
3. Реализовать и покрыть тестами.
4. Профилировать при больших n.

Резюме

Разворот массива — простая, но фундаментальная операция. Итеративный метод надёжен и экономичен по памяти. Рекурсивный метод часто короче и нагляден, но использует стек вызовов. В большинстве производственных задач предпочтителен итеративный in-place разворот или использование проверенной стандартной функции языка.