Инверсия для вставки сортировки!

Question

Этот вопрос я нашел на сайте Википедии (я хочу очень хорошо изучить алгоритмы сортировки). Во всяком случае, это вопрос - не могли бы вы объяснить мне, как я могу это показать?

Упражнение: Показать, что алгоритм вставки Sort (A) выполняется за время O(n + I), учитывая, что I - число инверсий в массиве A.

Answer 1

Посмотрите на Implementation а также Analysis разделы этой страницы.

Рассмотрим алгоритм, представленный там:

private static void insertionsort()
{
    int i, j, t;
    for (i=1; i<n; i++)
    {
        j=i;
        t=a[j];
        while (j>0 && a[j-1]>t)
        {
            a[j]=a[j-1];
            j--;
        }
        a[j]=t;
    }
}

Обратите внимание, что цикл while работает для v[i] итерации, где v[i] количество инверсий, вызванных элементом i, Это должно сделать доказательство там очень простым для понимания.