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.