snbk97 - 11 days ago 4x

C Question

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`

`temp`

`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(N ^{2})**, 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)

Comments