c++algorithmsortinginsertion-sorttwo-way

Two-way insertion sorting error


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.

enter image description here

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.


Solution

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