Блог

Главная - Вопросы по программированию - Если количество элементов достигает 30000, будет ли программа переполнять стек?

Если количество элементов достигает 30000, будет ли программа переполнять стек?

#c #sorting #quicksort

Вопрос:

Я работаю с большим массивом, около 14400 элементов.

Это моя функция быстрого рассасывания:

 void quickSort(slist_struct a[], int l, int h)
{
    if (l >= h) return;
    slist_struct pivot = a[(l   h) / 2];
    int i = l, j = h;
    while (i < j)
    {
        while (a[i].data > pivot.data) i  ;
        while (a[j].data < pivot.data) j--;
        if (i <= j)
        {
            if (i < j) swap(a[i], a[j]);
            i  ;
            j--;
        }
    }
    quickSort(a, l, j);
    quickSort(a, i, h);
}

Программа работает хорошо.

Если число элементов достигает 30000, будет ли программа переполнять стек? Спасибо.

Комментарии:

1. Это будет зависеть от размера стека.

2. может быть. может быть, и нет. Зависит от вашего окружения.

3. Если вы хотите уменьшить потребление стека, я предлагаю избавиться от локальной struct переменной pivot , в этом вообще нет необходимости. Вы можете заменить его указателем или использовать a[...] напрямую

4. Если ваша цель не состоит в том, чтобы узнать, как реализовать/оптимизировать алгоритм быстрой сортировки, я предлагаю использовать qsort стандартную функцию

5. Если вы хотите проанализировать использование стека вашей функции, что ж, тогда вам нужно проанализировать ее. Какова средняя глубина рекурсии? Это должно быть O(log(n)), где n — длина массива. Что в худшем случае? Если вы каждый раз получаете наихудший возможный разворот, то разворот будет наименьшим (или наибольшим) элементом, и в этом случае глубина рекурсии будет O(n), и на самом деле это будет n. Так что это зависит от размера массива, а также от того, сильно ли вам не повезет.

Ответ №1:

Попробуйте это изменение:

     while (i <= j)             /* was while (i < j) */

Ответ №2:

Программа не может переполнить стек.если это произойдет, вместо этого используйте структуру данных очереди. Во-первых, пусть очередь пуста, назовем количество элементов,которые вы хотите отсортировать, равным N. Первый элемент очереди содержит 1, N (очередь[0].L = 1; очередь[0].R = n) .Теперь используйте функцию сортировки (очереди[0].Очереди L..описание[0].Р) но менять
быстрая сортировка(в, Л, к);
быстрая сортировка(с, Я, ч);
к чему-то любит эту
очередь.толчок(я,з);
очередь.нажимаем(л,к);
очередь.поп();
повторите это, пока очередь пуста,
ты нужен полный код?

Метки: ,