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

Question

Исправьте положительные целые числа n и k.

Пусть A будет массивом длины n с A[i] массивом длины k, где каждая запись n-i,Например, для n=5 и k=1 это просто

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

, а для n=5 и k=2 это

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

Цель - всплытьсортируйте этот массив массивов, меняя числа в соседних массивах (например, меняйте местами A[i][j1] с A[i+1][j2]), пока каждая запись A[i] не будет i+1 для каждого i.

Вопрос в следующем: сколько нужно обменов и Какой оптимальный алгоритм ?

ПРИМЕЧАНИЕ: Есть много, много лучших алгоритмов сортировки для использования.Однако по этому вопросу меня интересует только использование пузырьковой сортировки, как описано выше.Я могу обмениваться записями только из соседних массивов, и меня интересует только минимальное количество таких необходимых обменов.Я ценю все предложения по другим алгоритмам сортировки, но я пытаюсь понять эту проблему.

ПРИМЕРЫ:

Для k=1 это хорошо известно.Число свопов - это число инверсии A, рассматриваемое как перестановка, поэтому минимальное количество свопов - это биномиальный коэффициент (n choose 2) = n(n-1)/2, и этого можно достичь, меняя любую пару из неупорядоченного порядка: A[i] > A[j].Для первого примера вот оптимальная сортировка пузырьков:

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

Для k=2, использование той же стратегии даст ограничение на 2 (n choose 2) необходимых свопов.Для приведенного выше примера это означает 20 свопы.Но есть решение, которое использует только 15 свопы:

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

Это решение является оптимальным для n=5 и k=2 (подтверждение методом грубой силы, чтобы найти все решения).Для n=6 лучшее решение требует 22 свопов, но решение выглядит не так хорошо, как для n=5 (следуйте 5 справа, затем 1 слева, затем 5 справа и т. Д.), ПоэтомуЯ до сих пор не знаю оптимальной стратегии, тем более формулы или лучшего определения количества свопов.

Я думал об этом уже пару дней и ничего не придумалпоучительно.Если у кого-то есть мысли по этой проблеме, то, пожалуйста, поделитесь ими.Я был бы рад узнать больше о деле k=2.Еще лучше для любых мыслей по общему делу.

РЕДАКТИРОВАТЬ: Я прошу прощения, если я не могу мотивировать эту проблему по своему вкусу, но вот попытка: количество видов пузырьков, необходимых для сортировки перестановки, является очень важной статистикой в ​​комбинаторике и теории чисел, называемой числом инверсииперестановки.Вы можете сортировать неупорядоченную перестановку, используя гораздо лучшие алгоритмы, но это тот, который дает вам алгебраическое значение.Если это не поможет, возможно, эта связанная статья SO может: Для чего нужна сортировка пузырьков?

---

ОБНОВЛЕНИЕ : самый старый ответ ниже дает нижнюю (и верхнюю) границу для числа обменов. второй самый старый ответ дает алгоритм, который действительно приближается к этой нижней границе (часто достигая ее).Было бы замечательно, если бы кто-то мог улучшить оценку или, что еще лучше, доказать, что приведенный ниже алгоритм является оптимальным.

Answer 1

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

Основная идея основана на получении информации. Предположим, что A = {[i, j]: 1 <= i <= n, 1 <= j <= n} представляет <em>конфигурацию . На каждом шаге мы имеем 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] <-> A [1] [1]. Таким образом, наша цель состоит в том, чтобы выбрать обмен, который имеет высокий прирост информации, когда нам нужно перейти от одной конфигурации к другой конфигурации.

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

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] ]

Answer 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 прохода, потому что a должно быть, осталось от b в некоторой точке.
• Если a > d, то мы получим 1/2 прохода, потому что a будет справа от d в некоторой точке.
• Если c < d, то мы получим 1/2 прохода, потому чтоd должно быть, осталось от c в какой-то момент.
• Если c < b, то мы получим 1/2 прохода, потому что b будет справа от c в некоторой точке.

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

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

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

Answer 3

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

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

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

Идея состоит в следующем:

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

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

3: Если это один из самых больших элементов,

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

В противном случае

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

Примечание: shift эквивалентно «пузыриванию» этого значения с наименьшим (соответственно наибольшим) элементом каждой пары.

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

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

Пример 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 были оптимальными, как вы ожидали.