Сортировка вставок - пример средней сложности случая для доказательства формулы для среднего случая - PullRequest
Новая
       10

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

0 голосов
/ 28 апреля 2018

Меня смущает, почему мой работающий пример для среднего случая для сортировки вставок сильно отличается от формулы, которую я нашел для вычисления среднего случая.

Код вставки сортировки, который я использую, приведен ниже. 

int[] myNumbers = {1, 2 3, 4};      
    int j;
    int key;
    int i;

    for (i = 1; i < myNumbers.length ; i++){
        j = i - 1;
        key = myNumbers[i];

        while (j >= 0 && myNumbers[j] > key) {        
            myNumbers[j + 1] = myNumbers[j];
            j--;
        }
        myNumbers[j+1] = key;
    }

Предполагая, что вы хотите отсортировать четыре значения: 1, 2, 3, 4 и каждая перестановка входов одинаково вероятна, число сравнений для каждого возможного ввода выглядит следующим образом: 

3 comparisons for inputs 1234, 2134 
4 comparisons for inputs 1243, 1324, 2143, 2314, 3124, 3214 
5 comparisons for inputs 1342, 1423, 2341, 2413, 3142, 3241, 4123, 4213 
6 comparisons for inputs 1432, 2431, 3412, 3421, 4132, 4231, 4312, 4321

Среднее тогда будет = (3 * 2) + (4 * 6) + (5 * 8) + (6 * 8) / 24 = 4.9166666

Но формула, которую я нашел для расчета среднего числа сравнений, была (n ^ 2 - n) / 4, который дает 3, который не может быть правильным? 3 - лучший случай.

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

Любая помощь будет принята с благодарностью!

...