Insertion Sort Printing Wrong Output

Question

I am trying to sort an array using the code below:-

The expected output should be an array which is sorted in ascending order.

But when i tried to run this code the output comes out to be 59 (6 times)

I have tried debugging it added a watch at first array declaration and added a breakpoint on the first for loop it gives out the error to be :-

->->error-begin 
A syntax error in expression, near `A[6]={31,41,59,26,41,58}'.
#include<iostream>
using namespace std;
int main()
{
    int A[6]={31,41,59,26,41,58};;
int j;
int length = 6;
    for(j=2;j<length;j++)
    {
        int key;
        key = A[j];
        int i;
        i=j-1;
        while(i>0 && A[i]>key)
        {
            A[i+1]=A[i];
            i=i-1;
        }
    A[i+1]=key;
cout<<A[j];

    }


return 0;
}

Update:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int A[6] = { 31, 41, 59, 26, 41, 58 };
    int temp;
    int j;
    int length = 6;
    for (j = 2; j < length; j++) {
        int key;
        key = A[j];
        int i;
        i = j - 1;
        while (i > 0 && A[i] > key) {
            temp = A[i + 1];
            A[i + 1] = A[i];
            A[i] = temp;
            i = i - 1;
        }
        A[i + 1] = key;
    }
    cout << A[j];

    return 0;
}

It's working is supposed to be like a bubble sort I do know about

std::sort(std::begin(A), std::end(A));

But I am curious why this code isn't working, I have already tried looking up wiki and other sites for similar code but i can't seem to find anything relevant.

Answer 1

For starters this loop

 for (j = 2; j < length; j++) {
      ^^^^^

has an incorrect initial setting. It will not sort an array that has only two elements or the second element will be never swapped with the first element if the second element is less than the first element.

It would be correctly to write the statement like

 for (j = 1; j < length; j++) {
      ^^^^^

The inner loop

while (i > 0 && A[i] > key) {

does not touch the element A[0] due to the condition i > 0, Thus the subcondition A[0] > key will be never checked.

It is better instead of swapping each pair of elements that satisfy the condition just to copy elements and then to write the "added" element in the required position.

The program can look the following way.

#include <iostream>

int main()
{
    int a[] = { 31, 41, 59, 26, 41, 58 };
    const size_t N = sizeof(a) / sizeof(*a);

    for (int x : a) std::cout << x << ' ';
    std::cout << std::endl;

    for (size_t i = 1; i < N; i++)
    {
        int value = a[i];
        size_t j = i;

        for (; j != 0 && value < a[j - 1]; --j)
        {
            a[j] = a[j - 1];
        }

        if (j != i) a[j] = value;
    }

    for (int x : a) std::cout << x << ' ';
    std::cout << std::endl;

    return 0;
}

The program output is

31 41 59 26 41 58
26 31 41 41 58 59

Answer 2

Replace:

while(i>0 && A[i]>key)

by:

while (i >= 0 && A[i] > key)//notice the equality sign!

It was just checking till the 1st index while the zeroth index was not touched

And you might want to print the contents of the array like this:

for(int i=0;i<6;i++)
    cout << A[i]<<" ";