Two-way insertion sorting error

Question

I'm trying to make a two-way insertion sort. It's supposed to take the very first value in an array, and then sort the following numbers in an array by comparing it to that first value. If the number is greater, it gets placed behind the first one in the array, if it's smaller, it is placed in front.

Here's an image that illustrates the process.

The array here is 6 5 3 1 8 7 2 4, reading from top to bottom is each step of the sorting process. It compares the number 6 with the rest of the numbers, and then places them accordingly.

So far I have this code:

void twowaysort(int n, int a[])
{
    int j;
    int first = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] > first) {
            j = i + 1;
            while (j <= n - 1 && a[j] < a[j - 1]) {
                swap(a[j - 1], a[j]);
                j = j + 1;
            }
        }
        if (a[i] < first) {
            j = i - 1;
            while (j >= 0 && a[j] > a[j + 1]) {
                swap(a[j + 1], a[j]);
                j = j - 1;
            }
        }
    }
}

While this works with the array above, it seems to fail sorting the following: 13 93 58 33 58 63 11 41 87 32. This makes me believe there's an error somewhere.

Any help would be appreciated.

Answer 1

I implemented this with a vector, I save the position of the starting number then insert left is the number is lower or right if the number is greater. Then numbers go to left or right until they are greater or lower.

Hope this helps

int poz = 0; //starting value position
vector<int> b;    
b.push_back(a[0]);//first value

for (int i = 1; i < n; i++)
{
    if (a[i] > prad)    //if greater
    {
        vector<int>::iterator it = b.begin() + poz;    //position of starting element
        it = b.insert(it + 1, a[i]); //insertion to the right
        int t = poz + 1;    //position of the inserted element
        while (t + 1 < b.size() && b[t] > b[t + 1])    
        {
            swap(b[t], b[t + 1]);   
            t++;                    //we go right until our number is greater
        }
    }
    else  //same here but instead of going right we go left until the value is lower
    {
        vector<int>::iterator it = b.begin() + poz;
        it = b.insert(it, a[i]);
        poz++; 
        int t = poz - 1;
        while (t > 0 && b[t] < b[t - 1])
        {
            swap(b[t], b[t - 1]);
            t--;                
        }
    }
}