0

I am going through my professor's lectures and implementing his code in order to better understand each sorting algorithm.

We went over insertion sorts and noted there were 3 different types:

  • Regular Insertion Sort
  • Insertion Sort till Located
  • Insertion Sort with Flag

The one I am having issues implementing is the Insertion Sort till Located which is written as such: same as the basic insertion sort, except the j-loop (inner loop) terminates as soon as the element being located is sorted with respect to the preceding element. The termination is valid since all preceding elements are already sorted. The algorithm is as follows:

for i = 2 to n
   j = i
   while (a[j] < a[j-1]) and (j>1)
       swap (a[j],a[j-1]), set j=j-1
   endwhile
 endfor

His pseudocode algorithm is strange because it is assuming an array starts at 1 so when I implement it in C++ it obviously will not sort the first element. When I want it start assuming 0 is the first element I go outside my range. I am obligated to do a check in outer loop which will allow a successful sort.

Here is the C++ implementation I used before:

void insertionSortTilLocated(vector<int>vector)
{
    for (int i = 2; i < vector.size(); i++)
    {
        int j = i;
        while (vector[j] < vector[j - 1] && j > 1)
        {
            swap(vector[j], vector[j - 1]);
            j = j - 1;
        }
     }
     cout << "Insertion sort til located" << endl;
     for (int k = 0; k < vector.size(); k++)
     {
         cout << vector[k] << endl;
     }
}

The added check swap I implemented that is successful is:

void insertionSortTilLocated(vector<int>vector)
{
    for (int i = 2; i < vector.size(); i++)
    {
        ...
        //Swap Check added
        if (vector[0] > vector[1])
        {
             swap(vector[0],vector[1]);
        }
     }
     ...
}

Even though I managed to deal with my issue, I am wondering though, where can I find a better algorithm? I wasn't able to find it doing a search and find results for "Insertion Sort Till Located", and the textbook I am using doesn't tackle this with this algorithm. Can someone provide an enhanced version of the algorithm so it makes more sense? Or at least an enhanced explanation of it so it makes more sense?

Thanks

gradytrain
  • 189
  • 1
  • 2
  • 11
  • 2
    Very helpful: [How to implement classic sorting algorithms in modern C++.](http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) – 101010 Jul 25 '14 at 20:38
  • 1
    Your problem is that ``for(int i = 2; i < vector.size(); i++)`` should set ``i = 1`` for a zero-indexed array. And the termination condition in the ``while`` loop should be ``j>0``, not ``j>1``. – aruisdante Jul 25 '14 at 20:54
  • Such parameter naming `vectorvector` is probably a bad idea. – πάντα ῥεῖ Jul 25 '14 at 20:58

0 Answers0