2

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!

  • 2
    did you try to compare speed of these algorithms with different values for size? 32, 64, 128, 256,... up to, say, 65536 or even 131702 (these are powers of 2). You may also be interested to learn about bubble sort – gnat Jan 19 '15 at 15:34
  • 2
    How can the first one be correct, given that it overwrites the 0th element of AR before reading it. Also there is an undefined variable temp. You should make sure your code compiles and is reasonable before asking questions here. – Konstantin Weitz Jan 19 '15 at 15:49
  • 1
    @Konstantin, it looks like the actual data to sort is stored starting at index 1 in order to avoid adding j > 0 to the while loop condition. – Karl Bielefeldt Jan 19 '15 at 16:04
  • @Gnat , thanks I'll try that along with how many passes and time taken. – Vignesh Balchand Jan 19 '15 at 16:15
  • @Konstantin, I apologize for the inconvenience and I do understand . I've edited the post accordingly.I'll be glad if you can still consider helping. Thanks ! – Vignesh Balchand Jan 19 '15 at 16:19
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.

  • Thank you so much ! I think you're right. Instead of swapping two elements, if I just rather place them in between, I think I'd be able to get it done. I'll definitely have a look at the other faster sorts . – Vignesh Balchand Jan 20 '15 at 1:48
  • quicksort is actually O(n²) worst case, it does have O(n log n) average case with better (hidden) factors – ratchet freak Jan 20 '15 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.