3

Код представлен на С++, рекурсивная функция сортировки слиянием, _с - это количество сравнений, m -количество перемещений, intVec - vector

 void CSort::simpleMerge(intVec& _sortingVec, int64_t& _c, int64_t& m, int begin = 0,int end = -1) {
    if (end == -1) {
        end = _sortingVec.size();
    }
    if (end - begin< 2) {
        
        return;
    }
    else if (end - begin == 2) {
            _c++;
        if (_sortingVec.at(begin) > _sortingVec.at(begin+1)) {
            m++;
            int b = _sortingVec.at(begin);
            _sortingVec.at(begin) = _sortingVec.at(begin + 1);
            _sortingVec.at(begin + 1) = b;
        }
        return;
    }
    simpleMerge(_sortingVec,_c,m, begin, begin + (end - begin) / 2);
    simpleMerge(_sortingVec, _c, m, begin + (end - begin) / 2,end);
    intVec c;
    size_t begin1 = begin;
    size_t begin2 = begin + (end - begin) / 2;
    size_t end1 = begin2;
    while (c.size() < end-begin)
    {
            _c++;
        if ((begin1>=end1) or(begin2<end and _sortingVec.at(begin2) <= _sortingVec.at(begin1))) {
            
            c.push_back(_sortingVec.at(begin2));
            m++;
            begin2++;
        }
        else {
            c.push_back(_sortingVec.at(begin1));
            m++;
            begin1++;
        }
    }
    for (size_t i = begin; i < end; i++)
    {
        _sortingVec.at(i) = c.at(i-begin);
    }
}

1 ответ 1

4

Первая часть вашего алгоритма выполняется за константное время, затем идут два вызова с грубо половинным размером от исходного, потом часть, выполняемая за линейное время (цикл по элементам). Если, конечно, intVec — это обычный вектор с операциями O(1) добавления в конец и получения элемента.

Тогда время работы T(n) можно описать как

T(n) = 2*T(n/2) + С*n 

Чтобы не писать всю теорию, берете "Алгоритмы. Построение и анализ. 3 издание" Кормена и на стр. 120 находите основную теорму, которую и применяете. Это ее второй случай. Более того, внизу на стр. 121 решено именно это уравнение, так что готовый ответ

T(n) = Θ(n log n)

Верно ли написан алгоритм — это я не смотрел :)

1

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.