Insertion sorting Algorithm comparison

Question

I recently came across sorting techniques and of particular, 'insertion sorting'.

Although the logic and method is fairly understandable, the actual function seemed a bit complex (given below).

void InSort(int AR[], int size)
{
    int tmp,j; 
    AR[0]=INT_MIN;  //defined in limits.h , basically the smallest possible value 

     for(int i=1;i<size;i++)
     {  
       tmp=AR[i];
       j=i-1;

        while(tmp<AR[j])
         {
           AR[j+1]=AR[j];
           j--;
          }

       AR[j+1]=tmp;
     }

}

Please note that the elements for the above function are entered from AR[1].

I then tried my own attempt to perform the sort in a more simple way as illustrated below. (ascending)

void iSort(int Arr[] , int size)
{
  Int temp;
  for(int i=1 ; i<size ; i++)
  {

    for(int j=0 ; j<i ; j++)
    {
       if(Arr[i]<Arr[j])
       {
        temp=Arr[i];
        Arr[i]=Arr[j];
        Arr[j]=temp;
        }
    }
  }
}

To my dismay, someone told me that although this method will perform the sort, it does not qualify as an 'Insert Sort', but I still believe that it does follow the same principle.

Is this so? Then, what is particularly wrong with my attempt? More Importantly, does the second function qualify as an insertion sort?

--

I would like to mention that I'm relatively very new to programming in general, so do forgive my seemingly primitive attempt, all I want to do is learn! Also, this isn't the recent C++ version, its actually stone age old, so apologies in advance!

I'd be happy for any inputs received , thanks in advance!

Answer 1

The second algorithm is called Bubble Sort, not Insertion Sort.

The idea is that in Insertion Sort, you take an element in the array, look for where it should be in the whole array, then "insert" it at that spot, shifting all the elements once. You only do this insertion once per element.

With Bubble Sort, you always look at two adjacent elements, and swap them if needed. The name comes from the idea that the highest elements will slowly "bubble up" to the top of the array, since they're only moving up one step at a time.

Then, what is particularly wrong with my attempt?

Nothing. You just happened to write a different algorithm by accident. Both of these algorithms have O(n^2) worst-case and average-case time complexity (since they do more or less the same comparisons and assignments in different orders), so it's not like you made it any worse.

I agree that Bubble Sort is usually a simpler algorithm to read and write in code, so if performance is a non-issue (and your language doesn't have a sort() function for some reason) then feel free to use that. However, Insertion Sort often performs better on arrays where most of the elements are already in the right place.

Of course, heapsort and mergesort are O(n log n) worst-case, and quicksort is O(n log n) average-case, so if you ever do care about sort performance you should probably look at one of those.