Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Heapsort не работает при большом размере массива

Автор: Lacoste1024 18.3.2012, 15:13

Есть реализация сортировки кучей (heapsort):

Код


void Heapify(int *A, int x, int size)
{
    int left = (2*x)+1;
    int right = (2*x)+2;
    int max, buf;
    
    if ((left < size) && (A[left] > A[x])) max = left;
    else max = x;
   
    if ((right < size) && (A[right] > A[max])) max = right;
    
    if (x != max) {
        buf = A[x]; A[x] = A[max]; A[max] = buf;
        Heapify(A, max, size);
    }
}

void BuildMaxHeap(int *A, int size)
{
    int i;
    
    for (i = size/2; i >= 0; i--) 
        Heapify(A, i, size);
}

void HeapSort(int *A, int size)
{
    int i, buf;
    
    BuildMaxHeap(A, size);
    for (i = size-1; i >= 1; i--) {
        buf = A[0]; A[0] = A[i]; A[i] = buf;
        size--;
        Heapify(A, 0, size);
    }
}

При размере массива сортируемых данных 10^4 и меньше всё прекрасно работает. Если размер массива 10^5, выводится "Ошибка сегментирования". Данные в программу поступают из текстового файла. На этих же данных пробовал другие методы сортировки - всё прекрасно работает. В чём причина неисправности? Если возможно, дайте ссылку на работающий код

Автор: ambler 19.3.2012, 14:26

Как вариант, т.к. тут рекурсия, может стек заканчивается?

Автор: borisbn 19.3.2012, 14:33

Логичное предположение. Можно проверить: в функции MaxHeapify объявить внутренний массив элементов эдак на 10000. Если станет падать на меньших размерах, то предположение верное.

Автор: Lacoste1024 19.3.2012, 20:10

В Maxheapify объявил простой массив int размером 100000. Всё так же работает и при 100, 1000, 10000. А при 10^5 Ошибка сегментирования. Кстати попробовал поперебирать значения входного массива. На 18000 выдаёт ошибку. Это и при старом и при новом коде(с объявленным массивом внутри MaxHeapify)

Попробовал решить проблему при помощи глобальной переменной. Не помогло =(

Добавлено @ 20:21
Проблема решена. нашёл другой код. Работающий =)

Код


void Heapify(int *A, int x, int size)
{
    int left = (2*x)+1;
    int right = (2*x)+2;
    int max, buf;
    
    if ((left < size) && (A[left] > A[x])) max = left;
    else max = x;
   
    if ((right < size) && (A[right] > A[max])) max = right;
    
    if (x != max) {
        buf = A[x]; A[x] = A[max]; A[max] = buf;
        Heapify(A, max, size);
    }
}

void BuildMaxHeap(int *A, int size)
{
    int i;
    
    for (i = size/2; i >= 0; i--) 
        Heapify(A, i, size);
}

void HeapSort(int *A, int size)
{
    int i, buf;
    
    BuildMaxHeap(A, size);
    for (i = size-1; i >= 1; i--) {
        buf = A[0]; A[0] = A[i]; A[i] = buf;
        size--;
        Heapify(A, 0, size);
    }
}

Автор: borisbn 20.3.2012, 06:13

Если включена оптимизация, то компилятор просто выкинул объявление неиспользуемого массива

Автор: feodorv 20.3.2012, 20:12

Цитата(Lacoste1024 @ 19.3.2012, 21:10

)

Проблема решена. нашёл другой код. Работающий =)

Код одинаков smile

Автор: sergioK1 21.3.2012, 10:40

Цитата(feodorv @ 20.3.2012, 19:12)

Цитата(Lacoste1024 @ 19.3.2012, 21:10

)

Проблема решена. нашёл другой код. Работающий =)

Код одинаков smile

A Я думал что только мне показалось, Lacoste1024 массив на стеке ?
должно упасть в момент выделения памяти,
на хипе пробовал ?

Автор: volatile 21.3.2012, 14:28

а нет, ошибся. сорри. удалил.

Автор: borisbn 21.3.2012, 14:33

volatile, max по любому будет инициализирована в этих строках

Код


if ((left < size) && (A[left] > A[x])) max = left;
    else max = x;

а т.к. приведённая Вами строка идёт после этих, то всё д.б. хорошо smile

Автор: volatile 21.3.2012, 14:40

Цитата(borisbn @ 21.3.2012, 14:33

)

т.к. приведённая Вами строка идёт после этих, то всё д.б. хорошо

borisbn, да, что-то я седня не выспался. smile