0

is my implementation to insertion sort correct?

for(int i = 0; i < n; i++)
{
    for(int j = i; j > 0; j--)
    {
        int t;
        if(a[j] < a[j - 1])
        {
            t = a[j - 1];
            a[j - 1] = a[j];
            a[j] = t;
        }
    }
}
1

Yes, this is an insertion sort.

Consider using sensible variable names if you don't want to put comments in your code to assist with readability.

1

well, by the eye, this should sort the array, although technically you don't need to swap elements in insertion sort.

in addition to @Daniel Lee's point about using descriptive variable names, here are some points:

  • you don't need to start at i = 0 since the first element is already sorted.
  • here is some pseudocode that may help you get closer to a more typical implementation:

    for i = 1 to n - 1, increment i by 1
        set temp to a[i]
        set j to i
    
        // shift greater elements to the right
        while j > 0 and a[j - 1] > temp
            set a[j] to a[j - 1]
            decrement j by 1
    
        // insert current element at its correct position
        set a[j] to temp
    

watch the short on insertion sort for more details: https://youtu.be/TwGb6ohsvUU!

3
  • I wondered why you set j>0 since it will always start from 1? – user27301 Jan 8 '17 at 10:10
  • @user27301, not sure what you're suggesting? – kzidane Jan 8 '17 at 11:22
  • Why not just put a[j-1] > temp ? Why add j>0? – user27301 Jan 10 '17 at 14:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .