Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Heapsort не работает при большом размере массива 
V
    Опции темы
Lacoste1024
Дата 18.3.2012, 15:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
Есть реализация сортировки кучей (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, выводится "Ошибка сегментирования". Данные в программу поступают из текстового файла. На этих же данных пробовал другие методы сортировки - всё прекрасно работает. В чём причина неисправности? Если возможно, дайте ссылку на работающий код

Это сообщение отредактировал(а) Lacoste1024 - 19.3.2012, 21:17
PM MAIL   Вверх
ambler
Дата 19.3.2012, 14:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 18
Регистрация: 27.10.2009

Репутация: нет
Всего: нет
Как вариант, т.к. тут рекурсия, может стек заканчивается?
PM MAIL   Вверх
borisbn
Дата 19.3.2012, 14:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
Lacoste1024
Дата 19.3.2012, 20:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 69
Регистрация: 20.3.2011

Репутация: нет
Всего: 1
В 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);
    }
}


Это сообщение отредактировал(а) Lacoste1024 - 19.3.2012, 21:18
PM MAIL   Вверх
borisbn
Дата 20.3.2012, 06:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

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


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
feodorv
Дата 20.3.2012, 20:12 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45
Цитата(Lacoste1024 @  19.3.2012,  21:10 Найти цитируемый пост)
Проблема решена. нашёл другой код. Работающий =)

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
sergioK1
Дата 21.3.2012, 10:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 417
Регистрация: 30.1.2011

Репутация: нет
Всего: нет
Цитата(feodorv @ 20.3.2012,  19:12)


Цитата(Lacoste1024 @  19.3.2012,  21:10 Найти цитируемый пост)
Проблема решена. нашёл другой код. Работающий =)

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

A Я думал что только мне показалось,  Lacoste1024  массив на стеке ?
должно упасть в момент выделения памяти, 
на хипе пробовал ? 
PM MAIL   Вверх
volatile
Дата 21.3.2012, 14:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
а нет, ошибся. сорри. удалил.


Это сообщение отредактировал(а) volatile - 21.3.2012, 14:39
PM MAIL   Вверх
borisbn
Дата 21.3.2012, 14:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
volatile, max по любому будет инициализирована в этих строках
Код

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

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


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
volatile
Дата 21.3.2012, 14:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85
Цитата(borisbn @  21.3.2012,  14:33 Найти цитируемый пост)
 т.к. приведённая Вами строка идёт после этих, то всё д.б. хорошо    


borisbn, да, что-то я седня не выспался.  smile 
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.2179 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.