Сортировка слиянием: превышение лимита времени - PullRequest
Новая
       13

Сортировка слиянием: превышение лимита времени

1 голос
/ 14 июня 2019

Почему я получаю time limit exceeded ошибку при сортировке массива с использованием алгоритма сортировки слиянием?Что не так с моим кодом?Я взял вход из 9 элементов.

Вход: 4 2 1 8 5 9 6 7 0

Выход: Time limit exceeded

#include <bits/stdc++.h>

using namespace std;
int a[100];

void merge(int a[], int l, int r, int m) {
    int t[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i <= m)
        t[k++] = a[i++];
    while (j <= r)
        t[k++] = a[j++];
    for (int i = l; i <= r; i++)
        a[i] = t[i - l];
}

void msort(int a[], int l, int r) {
    if (l > r)
        return;

    int m = (r + l) / 2;
    msort(a, l, m);
    msort(a, m + 1, r);
    merge(a, l, r, m);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    msort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

1 Ответ

1 голос
/ 15 июня 2019

В вашем коде есть некоторые проблемы:

  • Тест на завершение в msort() неверен: вы должны остановиться, когда срез содержит один элемент или меньше.В настоящее время вы зацикливаетесь на кусочки по 1 элементу. 

    if (l >= r) return;

  • Вы должны проверить в main(), если число n элементов, прочитанных пользователем, не превышает 100, размер глобального массива a, в который вы читаете элементы для сортировки.Вместо этого вы должны использовать локальный массив с правильным размером или выделить массив из кучи.Временный массив t в merge() также может быть слишком большим для автоматического выделения.Более эффективно выделить временное пространство один раз и передать его рекурсивно.

Обратите также внимание на то, что в C и C ++ идиоматично указывать фрагменты массива с индексом первого элемента и индексомэлемента после последнего.Это упрощает код и позволяет создавать пустые массивы и избегать особых случаев для типов индексов без знака.

Вот модифицированная версия с таким подходом: 

#include <bits/stdc++.h>

using namespace std;

void merge(int a[], int l, int r, int m, int t[]) {
    int i = l, j = m, k = 0;
    while (i < m && j < r) {
        if (a[i] < a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i < m)
        t[k++] = a[i++];
    while (j < r)
        t[k++] = a[j++];
    for (int i = l; i < r; i++)
        a[i] = t[i - l];
}

void msort(int a[], int l, int r, int t[]) {
    if (r - l > 1) {
        int m = l + (r - l) / 2;
        msort(a, l, m, t);
        msort(a, m, r, t);
        merge(a, l, r, m, t);
    }
}

void msort(int a[], int n) {
    if (n > 1) {
        int *t = new int[n];
        msort(a, 0, n, t);
        delete[] t;
    }
}

int main() {
    int n;

    cin >> n;
    if (n <= 0)
        return 1;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    msort(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    delete[] a;
    return 0;
}
...