Insertion Sort Algorithm in C

Question

I have a question about the following code for Insertion Sort:

void insertion(Item a[], int ell, int r)                
{               
    int i;          
        for (i=ell+1; i<=r; i++)            
           compexch(a[ell], a[i]);          
    {           
        for (i=ell+2; i<=r; i++)        
        {       
            int j=i;    
            Item v=a[i];    
            while(less (v, a[j-1])) 
            {   
                a[j]=a[j-1];
                j--;
            }   
            a[j]=v;
        }       

    }           
}

Ok, so my question is specifically about the while loop portion-I see that j is decremented and want to know what happens when j=0 and the a[-1] occurs. I do not understand how we can allow a negative index-what if the information we compare happens to work out and the while loops continues to run? Thanks.

What is that less() function? What does it do and why is it there? Also, the second { is bothering me. Why is that there? — e0k
– e0k, Commented Jan 23, 2016 at 2:41
Oh sorry-the less() function compares the two arguments to see if the first argument is less than the second. My professor explained this to us in class but did not provide the actual function. Same goes for the compexch() function, except it actually exchanges when it compares. — JFQue3316
– JFQue3316, Commented Jan 23, 2016 at 2:43
(Avoid to re-use loop control valiables: for (int i=ell+1 ; i<=r ; i++) {…} for (int i=ell+2 ; i<=r ; i++) {…}. Having the upper/right bound inclusive is less common than exclusive.) The value placed to be able to have just one loop condition is usually called sentinel. As Nate Eldredge points out, placing this value in a[ell] is what the first loop does. — greybeard
– greybeard, Commented Jan 23, 2016 at 8:47

Nate Eldredge · Accepted Answer · 2016-01-23 02:46:10Z

1

I assume compexch(x,y) does something like if (less(y,x)) { Item t = x; x=y; y=t }. So after the first for loop finishes, then a[ell] contains the least Item out of a[ell+1],...,a[r]. Now j is initialized with the value i, which is at least ell+2, so we have j > ell on entry to the while loop. If the while loop doesn't terminate sooner, we will eventually get down to j == ell. Since a[ell] has already been set to the least element in the range, less(v, a[ell]) will necessarily return false, and the loop will terminate then.

So j will never decrease to a value less than ell.

answered Jan 23, 2016 at 2:46

Nate Eldredge

62.4k7 gold badges78 silver badges121 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

e0k Over a year ago

@JFQue3316, I suggest using more descriptive variable names. In general, something longer than a single character that describes what purpose the variable serves.

JFQue3316 Over a year ago

@Nate EldredgeOh ok I think I get it now-so the purpose of the first for loop is to get the first element "sorted" for us...? That makes sense-thanks!

JFQue3316 Over a year ago

@e0k thanks for the feedback-I will change my professor's code next time and try to be a bit more descriptive when I ask a question.

Failed Scientist Over a year ago

@JFQue3316 Its considered quite unprofessional to copy and paste "professor's code" direct onto a post. You are lucky not to get a downvoting here. I would recommend you to have an overview of this site to observe related questions and have some idea of how to make a good post. Cheers! :)

JFQue3316 Over a year ago

@TalhaIrfan Ok thanks, I will remember that for next time. I'm still getting used to the site!

Collectives™ on Stack Overflow

Insertion Sort Algorithm in C

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related