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

The first thing I noticed is even though there is a selected value, there is no corresponding selected index. So that had to be added and used.

Second thing is that the selected value is only a boundry. And each time the currently sorted value has to bubble it's way down.

So all in all this is just a standard insertion sort. (That is if I understood the algorithm correctly.)

Renamed the variables i and j to to_sort_idx and look_at_idx.

void twowaysort( int a_size, int a[] )
{
    if ( a_size < 2 )
        return;

    int selected_idx   = 0;
    int selected_value = a[ selected_idx ];

    for ( int to_sort_idx = 1; to_sort_idx < a_size; to_sort_idx++ )
    {
        if ( a[ to_sort_idx ] > selected_value )
        {
            int look_at_idx = to_sort_idx;

            while ( look_at_idx > selected_idx && a[ look_at_idx ] < a[ look_at_idx - 1] )
            {              
                std::swap( a[ look_at_idx -1 ], a[ look_at_idx  ] );
                --look_at_idx;
            }
        }
        else //if ( a[ to_sort_idx ] <= selected_value )
        {
            int look_at_idx = to_sort_idx - 1;

            while ( look_at_idx >= 0 && a[ look_at_idx ] > a[ look_at_idx + 1 ] )
            {
                std::swap( a[ look_at_idx ], a[ look_at_idx + 1] );
                --look_at_idx;
            }

            ++selected_idx;
        } 
    }
}

Answer 2

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--;                
        }
    }
}

Answer 3

The issue here is your algorithm is only making one pass at the array where integers are being swapped. Because of the swapping of 93 to the back on the first pass, the second iteration looks at a[2] which is now 33 (not 58). So you have essentially skipped over processing 58. This algorithm only partially sorts the array. You would have to make multiple passes here to get what you want...

void twowaysort(int n, int a[])
{
    int j;
    int first;

    for (int k = 0; k < n; ++k)
    {
        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;
                }
            }
        }
    }

}

output: 11 13 32 33 41 58 58 63 87 93