Количество необходимых проходов для полной сортировки с помощью BubbleSort?

Question

Я изучаю математику за количеством проходов, необходимых для сортировки каждой из возможных комбинаций целых чисел [1,n] в array[n].

Например, с n = 3 есть 3! = 6 возможные перестановки чисел:

1,2,3 - 1,3,2 - 2,1,3 - 2,3,1 - 3,1,2 - 3,2,1.

• Одна из этих начальных перестановок требует k = 0 пропусков (1,2,3) для сортировки массива в порядке возрастания;
• Три из них требуют k = 1 проход (1,3,2 - 2,1,3 - 3,1,2) и
• Два требуют k = 2 проходов (2,3,1 - 3,2,1).

По сути, я хочу иметь возможностьматематически вывести набор чисел проходов {k} для данного n.

Для n = 4 число начальных перестановок P, для которых требуется k проходов, составляет P(n,k) = 1,7,10,6 for k = 0,1,2,3.

Конечно, когда-либо существует только 1 начальная перестановка для k = 0 (уже в порядке возрастания), то есть P(n,0) = 1, и число начальных перестановок для наибольшего значения k (которое равно n-1)это k !, то есть P(n,n-1) = (n-1)!.Или, по крайней мере, я так думаю ...

Я чувствую, что это проще, чем я делаю, и использует факторные формулы.

Answer 1

Алгоритм генерации перестановок: Алгоритм кучи .Этот код является методом грубой силы для расчета перестановок n объектов.Для каждой конфигурации количество проходов - это максимальная длина любого элемента от его отсортированной позиции, O(n).Учитывая n, это дает все P(n, k), выполняя гистограмму;время его работы экспоненциально в n, (в C)

#include <stdlib.h> /* EXIT */
#include <stdio.h>  /* printf */
#include <assert.h> /* assert */
#include <errno.h>  /* errno, ERANGE */

typedef void (*PermuteFunc)(const size_t a_size);

unsigned a[12];
const size_t a_max = sizeof a / sizeof *a;

/* https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 */
static void heaps_r(const size_t a_size, const unsigned k,
    const PermuteFunc func) {
    size_t i, j;
    assert(k && a_size);
    if(k == 1) { func(a_size); return; }
    for(i = 0; i < k; i++) {
        heaps_r(a_size, k - 1, func);
        if(i >= k - 1) continue;
        j = (k & 1) ? 0 : i; /* Odd/even. */
        a[j] ^= a[k-1], a[k-1] ^= a[j], a[j] ^= a[k-1]; /* Swap. */
    }
}

/* Generates all permutations of size `a_size` and passes them to `func`.
 @return Success. */
static int heaps(const size_t a_size, const PermuteFunc func) {
    size_t i;
    assert(func);
    if(!a_size || a_size > a_max) return errno = ERANGE, 0;
    for(i = 0; i < a_size; i++) a[i] = i + 1; /* Distinct numbers. */
    heaps_r(a_size, a_size, func);
    return 1;
}

static unsigned histogram[256]; /* This is good enough, right? */
static size_t histogram_size = sizeof histogram / sizeof *histogram;

/* @implements PermuteFunc */
static void print(const size_t a_size) {
    size_t i, bin = 0;
    assert(a && a_size);
    for(i = 0; i < a_size; i++) printf("%d ", a[i]);
#if 0 /* I misread the question. */
    /* O(n^2) way to calculate the Kendall tau distance. */
    for(i = 0; i < a_size; i++) {
        size_t j;
        for(j = i + 1; j < a_size; j++) if(a[i] > a[j]) bin++;
    }
#else
    /* Calculate the number of passes bubble-sort needs to make. */
    for(i = 0; i < a_size; i++) {
        size_t passes = abs(a[i] - i);
        if(passes > bin) bin = passes;
    }
#endif
    if(bin >= histogram_size) {
        fprintf(stderr, "Histogram too small for %d.\n", (unsigned long)bin);
        return;
    }
    histogram[bin]++;
    printf("-> %d\n", bin);
}

int main(int argc, char **argv) {
    int n;
    size_t k;
    const char *err = 0;
    do {
        if(argc != 2 || (n = atoi(argv[1]), n <= 0))
            { errno = EDOM; err = "Argument needed"; break; }
        if(!heaps(n, &print)) { err = "Heap's"; break; }
        printf("\n");
        for(k = 0; k < histogram_size; k++) if(histogram[k])
            printf("P(%d, %lu) = %u\n", n, (unsigned long)k, histogram[k]);
    } while(0);
    return err ? (perror(err), EXIT_FAILURE) : EXIT_SUCCESS;
}

Проходя 4, я получаю,

P(4, 1) = 1
P(4, 2) = 7
P(4, 3) = 10
P(4, 4) = 6

Я гуглил код расстояния Тау Кендалла и заметил, что это коэффициенты в разложении Product_ {i = 0..n-1} (1 + x + ... + x ^ i) , однако код с проходами пузырьковой сортировки не совпадаетлюбые документы.

Answer 2

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

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