огрубление слияния - PullRequest
Новая
       67

огрубление слияния

0 голосов
/ 20 октября 2019

Я только начал CLRS. Первая проблема 2-й главы заключается в укрупнении алгоритма сортировки слиянием с использованием сортировки вставкой, когда подрешетка достигает определенного минимального размера. Я написал модифицированный код, и я думаю, что он правильный, так как я проверил его на некоторых входах и различных значениях грубость . Я не уверен в некоторых скрытых угловых случаях. Кто-нибудь может сказать мне, если это может быть импровизировано дальше. Вот модифицированная процедура сортировки слиянием (ее время выполнения в тета-записи (nk + nlg (n / k)): 

void mergesort(int arr[], int p, int r, int k) { // k is the coarseness
    int q = (p + r) / 2;

    if (r - p + 1 > k) { // when the size of the subarray is atmost k, sort using insertion sort
    mergesort(arr, p, q, k);
    mergesort(arr, q + 1, r, k);

        merge(arr, p, q, r); // merge is the standard procedure

    }
    else {
        insort(arr, p, r); // insort is the standard insertion sort procedure
    }

}

Более того, в части 3 вопроса задается наибольшее значение k, при которомвремя выполнения этой процедуры совпадает со стандартным алгоритмом сортировки слиянием. Я попытался приравнять тета-нотации обеих процедур (nk + nlg (n / k) = nlgn), но можно ли это сделать? Я не получаю разумного ответа. Любая помощь будет оценена. Спасибо.

...