Insertion Sort algorithm ignoring first element

Question

I am implementing a simple Insertion Sort in C++ shown below:

void insertion_sort(int a[], int size)
{
    int temp;
    for (int i = 2; i < size; i++)
    {
        temp = a[i];
        int j = i - 1;
        while (j > 0 && a[j] > temp)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
        print_array(a, size);
    }
    cout << "Final:" << endl;
    print_array(a, size);
}

However, this sorts all elements in my array apart from the first element. This is what the output looks like:

Original array:
5 2 4 1 3 0 
Insertion Sorted array:
5 2 4 1 3 0 
5 1 2 4 3 0 
5 1 2 3 4 0 
5 0 1 2 3 4 
Final:
5 0 1 2 3 4

If I change

j > 0

to

j >= 0

then,

Original array:
5 2 4 1 3 0 
Insertion Sorted array:
5 2 4 1 3 0 
1 5 2 4 3 0 
1 5 2 3 4 0 
0 1 5 2 3 4 
Final:
0 1 5 2 3 4

I know it's been some time, but were you using Introduction to Algorithms by Cormen? I just ran into this same problem trying to follow along with the first insertion sort example. In figure 2.2, it shows the array indices above as starting at 1 instead of 0. Odd that it left out the >= in the while condition also. — cranbanan
– cranbanan, Commented Dec 3, 2019 at 22:08

user2076694 · Accepted Answer · 2014-03-14 15:55:32Z

6

You just need to keep the condition ( j >= 0 ) and to change your starting point in your loop over i, you should start from 1 not from 2.

answered Mar 14, 2014 at 15:55

user2076694

8561 gold badge6 silver badges12 bronze badges

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

Comments

cranbanan · Accepted Answer · 2019-12-09 21:26:32Z

Your code works for arrays that are indexed starting on 1. The first element of arrays in c++ is always 0. Without changing any operators, you can just shift your array to start(or end) on 0, in the beginning of the for loop and when shifting down in the while loop:

void insertion_sort(int a[], int size)
{
int temp;
for (int i = 1; i < size; i++)
{
    temp = a[i];
    int j = i - 1;
    while (j > -1 && a[j] > temp)
    {
        a[j + 1] = a[j];
        j--;
    }
    a[j + 1] = temp;
    print_array(a, size);
}
cout << "Final:" << endl;
print_array(a, size);
}

Something else to note about this code: the && is short circuiting. If, in this case j = -1, then j > -1 is false, and a[-1] is not evaluated in while (j > -1 && a[j] > temp) because it is made irrelevant by j being > -1. Whatever a[j] is will not make the result true.

Collectives™ on Stack Overflow

Insertion Sort algorithm ignoring first element

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related