CODEWITHSUNDEEP
c++algorithmsortinginsertion-sort
user3420507
user3420507

Reputation: 19

Insertion Sort algorithm ignoring first element

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

Upvotes: 2

Views: 2278

Answers (2)

cranbanan
cranbanan

Reputation: 102

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.

Upvotes: 1

user2076694
user2076694

Reputation: 836

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.

Upvotes: 6

Related Questions