How do you reverse an array in place?
Short answer: Use two indices, low at the start and high at the end. Swap the elements, move low up and high down, and stop when they meet. O(n) time, O(1) extra space.
#include <stddef.h>
void reverse_array(int *arr, size_t n)
{
if (n < 2) return;
size_t low = 0, high = n - 1;
while (low < high) {
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
low++;
high--;
}
}
/* {1, 3, 5, 7, 8, 9} -> {9, 8, 7, 5, 3, 1} */
Dry run for {1, 3, 5, 7, 8, 9}: swap (0,5) → 9 3 5 7 8 1; swap (1,4) → 9 8 5 7 3 1; swap (2,3) → 9 8 7 5 3 1; low = 3, high = 2, stop. Three swaps for six elements: n/2 swaps.
Why n < 2 first: with size_t (unsigned), n - 1 for an empty array wraps to SIZE_MAX and high points far outside the array. Hard-coding high = 5 in main hides this problem; pass the length in.
Why low < high and not low <= high: when they are equal (odd length), the middle element would be swapped with itself, which is harmless but wasted work.
Pointer version:
void reverse_ptr(int *first, int *last) /* last points at the final element */
{
while (first < last) {
int t = *first; *first++ = *last; *last-- = t;
}
}
Where reversal is used: as the building block for rotating an array, reversing words in a string, and converting between byte orders in a buffer.