snbk97 - 11 days ago 4x
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.

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]);
}
}
}
``````
Source (Stackoverflow)