Ошибка сортировки при двусторонней вставке

Question

Я пытаюсь сделать двустороннюю сортировку вставок.Он должен принимать самое первое значение в массиве, а затем сортировать следующие числа в массиве, сравнивая его с этим первым значением.Если число больше, оно помещается позади первого в массиве, если оно меньше, оно помещается впереди.

Вот изображение, иллюстрирующее процесс.

Массив здесь равен 6 5 3 1 8 7 2 4, чтение сверху вниз - это каждый шаг процесса сортировки.Он сравнивает число 6 с остальными числами и затем размещает их соответственно.

Пока у меня есть этот код:

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

Хотя это работает с массивом выше, кажетсяне выполнить сортировку следующего: 13 93 58 33 58 63 11 41 87 32. Это заставляет меня поверить, что где-то есть ошибка.

Любая помощь будет оценена.

Answer 1

Первое, что я заметил, - хотя выбранное значение не существует, соответствующего выбранного индекса нет. Так что это должно было быть добавлено и использовано.

Во-вторых, выбранное значение является только границей. И каждый раз, когда отсортированное в данный момент значение всплывает вниз.

Так что в целом это просто стандартная сортировка вставок. (Это если я правильно понял алгоритм.)

Переименованы переменные i и j в to_sort_idx и 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

Я реализовал это с помощью вектора, я сохраняю позицию начального числа, затем вставляю влево, если число меньше или вправо, если число больше.Затем числа идут влево или вправо, пока они не станут больше или ниже.

Надеюсь, это поможет

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

Проблема в том, что ваш алгоритм делает только один проход в массиве, где меняются целые числа. Из-за перестановки 93 в обратном направлении при первом проходе вторая итерация рассматривает [2], которое теперь составляет 33 (а не 58). Таким образом, вы по существу пропустили обработку 58. Этот алгоритм только частично сортирует массив. Вам нужно сделать несколько проходов, чтобы получить то, что вы хотите ...

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

}

вывод: 11 13 32 33 41 58 58 63 87 93