Why is arr[pre+1] = curr used if swapping already places the element correctly?

Question

In this insertion sort implementation, is the line arr[pre + 1] = curr; optional?
Since we are already swapping elements inside the while-loop, won't the current element automatically reach its correct position without explicitly assigning it at the end?”

void insertionSort(int* arr, int n) {
    for (int i = 1; i < n; i++) {
        int curr = arr[i];
        int pre = i - 1;
        while (pre >= 0 && arr[pre] > curr) {
            swap(arr[pre], arr[pre + 1]);
            pre--;
        }
        // arr[pre+1] = curr; is this line optional ?
    }
}

Follow the code through on paper. Do it with and without that line that you aren't understanding, and see the difference. Pen and paper is a great tool for understanding algorithms — ChrisMM
– ChrisMM, Commented Nov 18 at 12:48
Side note : int* arr, int n C++ has std::span for this. Or use std::vector<int>&. Do not represent arrays by passing around pointers (that's so pre C++98) — Pepijn Kramer
– Pepijn Kramer, Commented Nov 18 at 12:49

Proteus · Accepted Answer · 2025-11-18 12:53:50Z

5

In your implementation the commented line is in fact not crucial to sort the array. The thing is, by using swap() your'e doing something more similar to bubble sort - moving curr left until it matches the sorted part. The "actual" insertion sort would instead push all elements right and add curr to the empty space left at pre+1:

// a std::vector<int>& is also a good option - thx comments
void insertionSort(int* arr, int n) {
    for (int i = 1; i < n; i++) {
        int curr = arr[i];
        int pre = i - 1;
        while (pre >= 0 && arr[pre] > curr) {
            arr[pre+1] = arr[pre];
            pre--;
        }
        arr[pre+1] = curr; // now it's important
    }
}

I think this approach is better than swapping because of the reduction of assignments per element sorted - swap() uses a temp variable.

answered Nov 18 at 12:53

Proteus

7023 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Marek R Nov 18 at 13:22

godbolt.org/z/8xGnTzPds

Ben Voigt Nov 18 at 15:23

Note that in the general case, this "reduction of assignments" optimization may actually make performance worse. To fix that, use std::move. Not needed in the specific case of int.

Collectives™ on Stack Overflow

Why is arr[pre+1] = curr used if swapping already places the element correctly?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related