Insertion Sort in C++ and Time Complexity Analysis

Hello everyone,

Insertion sort of process is shown in below:

Insertion sort is a very simple method, but it will be take much time to sort your data.

Pseudocode :

INSERTION-SORT( A )

  for j = 2 to length[A]
     do key = A[j]
        i = j - 1
        while i > 0 and A[j] > key
            do A[i+1] = A[i]
                i = i - 1
         A[i+1] = key

Time Complexity:

We shall assume that each execution of line takes time ci, and ci is a constant.

Pseudocode :

INSERTION-SORT( A )                         cost          times

  for j = 2 to length[A]                    c1            n               
     do key = A[j]                          c2            n - 1
        i = j - 1                           c4            n - 1
        while i > 0 and A[j] > key          c5            [n(n + 1) / 2] - 1
            do A[i+1] = A[i]                c6            (n(n - 1) / 2)
                i = i - 1                   c7            (n(n - 1) / 2)
         A[i+1] = key                       c8            n - 1

Worst-case:

T(n) = c1 n + c2 (n - 1) + c4 (n - 1) + c5 ([n(n + 1) / 2] - 1) + c6 ((n(n - 1) / 2))

           + c7 ((n(n - 1) / 2)) + c8 (n - 1)

        =( c5/2 + c6/2 + c7/2  ) n^2 + ( c1 + c2 + c4 + c5/2 -  c6/2 - c7/2 + c8 ) n - ( c2 + c4 + c5 + c8 ) .
     
        = Big-o (n^2)


Best-case:


T(n) = c1 n + c2 (n - 1) + c4 (n - 1) + c5 ([n(n + 1) / 2] - 1)  + c8 (n - 1)

       = (c1 + c2 + c4 + c5 + c8) n - (c2 + c4 + c5 + c8)

       = Big-o (n)



Implemented in C + + :

#include <iostream>

template <class KeyType>
class sort{
private:
    int i,j;
    KeyType KeyValue;
public:
    inline sort(){
        i=j=0;
    }

   inline ~sort(){
        std::cout<<"Destructor has been executed!!";
    }

    inline void insertion_sort(KeyType *array,int num){
        for(int j=1;j<num;j++){
            KeyValue=*(array+j);
            i=j-1;
            while((i > -1)&&( *(array+i) > KeyValue)){
                *(array+i+1)=*(array+i);
                i=i-1;
            }
            *(array+i+1)=KeyValue;
        }
        std::cout<<std::endl;
        std::cout<<"The Array has been sort!"<<std::endl;
    }
};


int main()
{
    using namespace std;
    int size=0;
    cout<<"Please key in your array size"<<endl;
    cin>>size;
    cout<<"Please key in the key of array"<<endl;
    int A[size];
    for(int i=0;i<size;i++){
        cin>>A[i];
    }
    sort<int> Sort;
    Sort.insertion_sort(A,size);
    for(int i=0;i<size;i++){
            cout<<A[i]<<" ";
        }
    cout<<endl;
    return 0;
}

Reference book : INTRODUCTION TO ALGORITHMS (second edition)
Authors:
                  THOMAS H. CORMEN
                  CHARLES E. LEISERSON
                  RONALD L.  RIVEST
                  CLIFFORD STEIN

The C ++ code is write by myself  ; )

Thanks

By   Victor