snbk97 snbk97 - 1 month ago 16
C Question

Insertion Sort by swapping

I've just started to DSA, and had a question about insertion sort.

This the version from textbooks / tutorials.

void insertion_sort(int A[], int n) {
for (int i = 0; i < n; i++) {
int temp = A[i];
int j = i;

while (temp < A[j - 1] && j > 0) {
A[j] = A[j - 1];
j = j - 1;
}
A[j] = temp;
}
}


I was thinking would it make a difference, if we used
swapping
numbers instead of shifting the numbers and inserting the
temp
value in the correct hole position.

void insertionSort(int A[], int n) {
for (int i = 0; i < n; i++) {
int temp = A[i];
int j = i;

while (temp < A[j - 1] && j > 0) {
swap(A[j], A[j - 1]);
j--;
}
}
}


Swap Code:

void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}


Oh, and it would be really awesome if someone could explain the Time Complexities of both.

Answer

Your proposed alternative is incomplete, you did not post the code for swap(). In C, swap must be a macro and such a macro is easy to botch, whereas in C++, it can be a function that takes both arguments by reference.

Furthermore, you should test j > 0 before dereferencing A[j - 1]. As posted, the code invokes undefined behavior.

Regarding your questions, both functions are equally slow with a time complexity of O(N2), but the second is potentially slower because swapping involves more reads and writes than simply shifting the values by one position, but it could be faster on a sorted array because the first version has redundant stores.

Note that you can further simplify the code at the price of efficiency this way:

void insertionSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && A[j] < A[j - 1]; j--) {
            swap(A[j], A[j - 1]);
        }
    }
}