Разница во времени выполнения сортировки вставками с использованием кода CLRS и кода Роберта Седжвика

Итак, совсем недавно, просто из любопытства, я купил книгу «Введение в алгоритмы» автора CLRS. Когда я начал читать книгу, я заметил, что некоторые очень типичные алгоритмы в книге реализованы совсем по-другому.

Реализация быстрой сортировки в CLRS сильно отличается от популярного алгоритма Хоара для быстрой сортировки.

Итак, приступая к моему вопросу...

void insertion_sort_by_robertsedgewick(int a[],int n)
{   
    for(int i=0;i<n;i++)
    {
        for(int j=i;j>0;j--)
        {
            if(a[j]<a[j-1])
            {
                swap(a[j],a[j-1]);
            }
        }
    }
}

это код, используемый Робертом Седжвиком в его курсе Coursera по алгоритмам.

Напротив, реализация сортировки вставками, представленная в CLRS, такова:

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

Что довольно странно, так это время работы. Вот мои результаты, когда я запустил две разные реализации:

Количество элементов в массиве: 10 000

Время реализации Роберта Седжвика: 0,235926 с.

Время реализации CLRS: 0,078608 с.

Может ли кто-нибудь объяснить мне эти результаты? Алгоритм примерно тот же. Только реализация разная. Как небольшая разница в реализации могла вызвать такую ​​огромную разницу во времени выполнения?


performance sorting algorithm clrs insertion-sort
person Suyash Shetty    schedule 20.10.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

Цитата из его книги Алгоритмы, в которой используется тот же код:

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

Подобно его коду быстрой сортировки в его курсе Coursera, см. -Way Partitioning: зачем лишний обмен?.

person Yu Hao    schedule 20.10.2014

arrow_upward
2
arrow_downward

Небольшая эффективность реализации CLRS, которую я вижу, заключается в том, что она не меняет местами элементы сразу, а только копирует элементы вверх и ждет, пока не будет получена позиция ключа. Затем он копирует ключ в правильное положение.

Если на любой итерации массив:

1 2 3 6 7 8 5
            ^

и указатель находится на 5, то в первой версии шаги будут такими:

1 2 3 6 7 5 8
1 2 3 6 5 7 8
1 2 3 5 6 7 8

тогда как в следующей версии шаги будут такими:

1 2 3 6 7 8 8
1 2 3 6 7 7 8
1 2 3 6 6 7 8
1 2 3 5 6 7 8
person Abhishek Bansal    schedule 20.10.2014