Оптимальный алгоритм сортировки пузырьков для массива массивов чисел

Ответ 1

Это не оптимальный ответ, но я хотел бы поделиться своей попыткой, так как кто-то может его улучшить. Я не думал о том, чтобы найти формулу для вычисления минимального количества свопов, а скорее по оптимальному алгоритму. Алгоритм основан на k = 2.

Основная идея основана на усилении информации. Предположим, что A = {[i, j]: 1 <= я <= n, 1 <= j <= n} представляет конфигурацию. На каждом шаге у нас есть 4 * (n-1) возможное переключение для перехода от одной конфигурации к другой. Например, если n = 2 (т.е. A = [{2,2}, {1,1}]), то у нас есть 4 возможных подкачки A [0] [0] → A [1] [0], A [0] [0] ↔ A [1] [1], A [0] [1] ↔ A [1] [0] и A [0] [1] ↔ А [1] [1]. Таким образом, наша цель состоит в том, чтобы выбрать swap, который имеет высокий коэффициент усиления информации, когда нам нужно перейти от одной конфигурации к другой.

Сложной частью будет "как вычислить коэффициент усиления информации". В моем решении (ниже) коэффициент усиления информации основывается на расстоянии от его правильного положения. Позвольте мне показать вам мой код (написанный на С++), чтобы понять, что я пытаюсь сказать:

const int n = 5;
const int k = 2;

int gain(int item, int from, int to)
{
    if (to > from)
        return item - to;
    else
        return to - item ;
}

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

void print_config (int A[][k])
{
    cout << "[";
    for (int i=0; i<n; i++) {
        cout << " [";
        for (int j=0; j<k; j++) {
            cout << A[i][j] << ", ";
        }
        cout << "\b\b], ";
    }
    cout << "\b\b ]" << endl;
}

void compute (int A[][k], int G[][4])
{
    for (int i=0; i<n-1; i++)
    {
        G[i][0] = gain(A[i][0], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
        G[i][1] = gain(A[i][0], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
        G[i][2] = gain(A[i][1], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
        G[i][3] = gain(A[i][1], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
    }
}

int main()
{
    int A[n][k];
    int G[n-1][k*k];

    // construct initial configuration
    for (int i=0; i<n; i++)
        for (int j=0; j<k; j++)
            A[i][j] = n-i;

    print_config(A);

    int num_swaps = 0;
    int r, c;
    int max_gain;

    do {
        compute (A, G);

        // which swap has high info gain
        max_gain = -1;
        for (int i=0; i<n-1; i++)
            for (int j=0; j<k*k; j++)
                if (G[i][j] > max_gain) {
                   r = i;
                   c = j;
                   max_gain = G[i][j];
                }

        // Did we gain more information. If not terminate
        if (max_gain < 0) break;

        switch (c)
        {
            case 0: swap(A[r][0], A[r+1][0]); break;
            case 1: swap(A[r][0], A[r+1][1]); break;
            case 2: swap(A[r][1], A[r+1][0]); break;
            case 3: swap(A[r][1], A[r+1][1]); break;
        }

        print_config(A);
        num_swaps++;

    } while (1);
    cout << "Number of swaps is " << num_swaps << endl;
}

Я выполнил приведенный выше код для случаев n = 1,2,... и 7. Ниже приведены ответы (количество свопов) соответственно: 0, 2, 5, 10, 15, 23 (очень близко) и 31. Я думаю, что функция gain() не работает хорошо, когда n четно. Можете ли вы подтвердить это, подтвердив количество свопов при n = 7. Нижняя граница вашего уравнения равна 31, поэтому это оптимальное количество свопов при n = 7.

Я печатаю здесь вывод, когда n = 5 (поскольку вы ищете шаблон):

[ [5, 5],  [4, 4],  [3, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [5, 4],  [3, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [5, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [2, 3],  [5, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [2, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [5, 4],  [2, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [5, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [1, 3],  [5, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [1, 3],  [1, 2],  [5, 5] ]
[ [4, 3],  [2, 1],  [4, 3],  [1, 2],  [5, 5] ]
[ [1, 3],  [2, 4],  [4, 3],  [1, 2],  [5, 5] ]
[ [1, 3],  [2, 4],  [1, 3],  [4, 2],  [5, 5] ]
[ [1, 3],  [2, 1],  [4, 3],  [4, 2],  [5, 5] ]
[ [1, 1],  [2, 3],  [4, 3],  [4, 2],  [5, 5] ]
[ [1, 1],  [2, 3],  [2, 3],  [4, 4],  [5, 5] ]
[ [1, 1],  [2, 2],  [3, 3],  [4, 4],  [5, 5] ]

Ответ 2

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

Минимальное количество свопов, например m, для k=2 ограничено:

2 * (n choose 2) >= m >= (2n choose 2) / 3

Почему это работает?

Верхняя граница приступает к сортировке пузырьков по первым элементам массивов, за которыми следует сортировка пузырьков на вторых элементах массивов. Эта часть не так сложна.

Нижняя граница немного сложна, но вот как я к ней пришел. Позвольте подсчитать количество проходов, где проходит пропуск, когда большее число перемещается слева от меньшего числа справа от этого числа. Это может произойти в 1 обмене a и b, причем a больше и в массиве слева от b. Он также может принимать 2 своп, если a перемещается в массив с помощью b за один обмен, а затем переходит к более позднему свопу. Чтобы правильно отслеживать вещи, счетчик проходит пополам в этом случае. Чтобы упростить подсчет, он также считается проходом, когда два одинаковых числа разделяются, а затем рекомбинируются.

Массив полностью сортируется после прохождения (2n choose 2), поэтому единственный вопрос в том, сколько проходов может произойти с одним обменом. Здесь простой пример, где a и c меняются местами:

... [a,b] , [c,d] ... 
... [c,b] , [a,d] ... 

Теперь подсчитайте количество проходов максимум, которое могло произойти:

• Так как a > c, мы обязательно получаем 1 полный проход.
• Если a > b, то мы получим 1/2 pass, потому что в некоторой точке a осталось от b.
• Если a > d, то мы получим 1/2 pass, потому что a будет в некотором смысле правым от d.
• Если c < d, то мы получим 1/2 pass, потому что в некоторой точке d осталось c.
• Если c < b, то мы получим 1/2 pass, потому что b будет правым от c в некоторой точке.

Поэтому лучшее, что вы можете сделать при свопинге, - это получить 3 прохода (1 полный и 4 половинки).

Почему это не полный ответ?

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

Ответ 3

Вот интуитивный алгоритм, о котором я думал. Это дает конструктивное доказательство оптимального решения, которое я думаю.

Вот алгоритм:

Я попробовал это для n = 4 5 6 7 9 и дал те же результаты, что и у badawi:

Идея такова:

1: выбрал одно экстремальное значение, которое не находится на последнем месте (1 или n для начала)

2: найдите крайнее значение, которое ближе всего к его последней позиции (помечено стрелкой в ​​моем примере ниже)

3: Если он входит в число наибольших элит,

затем переместите его на другую сторону и shifht все наименьший элемент пары влево

иначе

переместите его в другую сторону и сдвиньте весь самый большой элемент каждой пары вправо.

Примечание. Перемещение равносильно "пузырению" этого значения с помощью элемента smalles (resp most) каждой пары.

4: вернитесь к шагу 2, но если вы выбрали один из больших, возьмите один из маленьких и наоборот.

Это довольно интуитивно понятное и, похоже, работает:

Пример n = 5:

11 22 33 44 55 
^
|
12 23 34 45 51 (4 moves) // shifted all larger numbers to the left
          ^
          |
52 13 24 43 51 (3 moves) // shifted all smaller numbers to the right
   ^
   |
52 34 24 35 11 (3 moves) // shifted all larger numbers to the left
          ^
          |
55 24 34 32 11 (3 moves) // smaller to the right
   ^
   |
55 44  33 22 11 (2 moves) // larger to left

Всего 15 шагов.

второй пример n = 7:

11 22 33 44 55 66 77 // 6 moves
 ^
12 23 34 45 56 67 71 //5 moves
                ^
72 13 24 35 46 56 71 //5 moves
   ^
72 34 25 36 46 57 11 // 4 moves
                ^
77 24 35 26 36 45 11 //4 moves
   ^
77 45 36 26 35 42 11 //1 move
       ^       
77 65 34 26 35 42 11 //2 moves
         ^
77 65 34 56 34 22 11 //2 moves
          ^
77 66 54 53 34 22 11 //1 move
          ^
77 66 54 45 33 22 11 //1 move
          ^
77 66 55 44 33 22 11

всего: 31

Не стесняйтесь задавать мне вопросы, если я не понимаю.

Это довольно легко сделать это вручную. Вы можете попробовать это самостоятельно с помощью 6 или 7 или написать алгоритм.

Я попробовал это с 6, это дало 23. , с 7 дал 31, а 9 дал 53, для вычисления его вручную требуется одна минута, не вычисляя ничего

Почему это решение оптимально:

Каждый раз, когда вы перемещаете один большой элемент на противоположную сторону, вы перемещаете все самое маленькое из пары влево.

Таким образом, перемещение всего большого элемента не заставит вас потерять какой-либо ход для перемещения всего самого маленького.

Вы всегда перемещаете элемент в "правильном направлении"

Кроме того, для перемещения экстремальных элементов вы делаете минимальное количество ходов. (это потому, что алгоритм берет крайнее значение, самое близкое к его последней позиции, что никакое движение не теряется)

Обоснование для маленького элемента одинаково.

Этот алгоритм дает вам оптимальные ходы, поскольку он не делает никаких ненужный ход.

Надеюсь, я не ошибся.

Это доказывает, что результаты badawi были оптимальными, как вы ожидали.