Insertion Sort by swapping

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 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 1

Time complexity for both the approaches is O(N^2) in worst case. But number of operations in the second approach is more as compared to the first because second approach performs the same number of swaps as the number of shifts in the first approach but swap require 3 assignments as compared to just one in in shift-based approach. Hence, method proposed by you will be slower as compared to just shifting the elements.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>

void insertion_shift(int* arr, int n){
    int i,j,k;
    for(i=1;i<n;++i){
        int temp=arr[i];
        for(j=i;j>0 && arr[j-1]>temp;--j)
            arr[j]=arr[j-1];
        arr[j]=temp;
    }
}
void swap(int* a, int* b){
  int temp= *a;
  *a= *b;
  *b= temp;
}

void insertion_swap(int* arr, int n){
   int i,j,k;
   for(i=1;i<n;++i){
      int temp=arr[i];
      for(j=i;j>0 && arr[j-1]>temp;--j)
         swap(&arr[j-1],&arr[j]);
   }
 }      

void print_arr(int* arr, int n){
   int i;
   for(i=0;i<n;++i)
      printf("%d ",arr[i]);
   printf("\n");
}

int main(){
   int n;
   scanf("%d",&n);
   int* arr1= (int*)malloc(sizeof(int)*n);
   int* arr2= (int*)malloc(sizeof(int)*n);
   int i;
   for(i=0;i<n;++i){
      scanf("%d",&arr1[i]);
      arr2[i]=arr1[i];
   }

   struct timespec start, end;
   clock_gettime(CLOCK_MONOTONIC_RAW,&start);
   insertion_shift(arr1,n);
   clock_gettime(CLOCK_MONOTONIC_RAW,&end);
   uint64_t time_shift= (end.tv_sec - start.tv_sec)*1000000 +
                        (end.tv_nsec - start.tv_nsec)/1000;
   printf("using shift: %lld microseconds\n",time_shift);

   clock_gettime(CLOCK_MONOTONIC_RAW,&start);
   insertion_swap(arr2,n);
   clock_gettime(CLOCK_MONOTONIC_RAW,&end);

   uint64_t time_swap= (end.tv_sec - start.tv_sec)*1000000 +
                       (end.tv_nsec - start.tv_nsec)/1000;
   printf("using swap: %lld microseconds\n",time_swap);

}

Here is what I got when I called both functions on the same array of size 10000. Compilation and execution for 10000 elements array. If still not convinced, try to generate a random array of size 1000-10000 and run the above code to observe the difference.

Answer 2

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²), 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]);
        }
    }
}