Тестирование алгоритмов сортировки с разными размерами наборов чисел
У меня есть код C, который сначала реализует алгоритм пузырьковой сортировки, а затем AVL Сортировка для разных размеров наборов чисел. У меня есть 4 разных файла .txt, которые включают разные размеры наборов чисел (10000 - 100000 - 1000000 - 10000000). Когда я пробую оба алгоритма с большим количеством маленьких наборов чисел или даже пробую их только с одним набором чисел, оба алгоритма работают нормально и дают истинные результаты. Но когда я вызываю их последовательно в функции main, программа консоли прерывается и перестает работать. Вот мои вызовы в основной функции;
int main()
{
test("10000.txt", 10000);
test("100000.txt", 100000);
test("1000000.txt", 1000000);
test("10000000.txt", 10000000);
return 0;
}
Здесь то, что делает функция test(), - это чтение всех строк из файлов .текст и их вставка в AVL Tree и в несортированный массив. Затем работают алгоритмы AVL Сортировка и Пузырьковая сортировка, прошедшее время записывается и выводится на консоль. Несмотря на то, что я комментирую коды AVL-сортировки и запускаю только пузырьковую сортировку, она прерывается, когда я последовательно вызываю функцию test() в основном. Вот моя функция пузырьковой сортировки;
void bubblesort(unsigned long long *arr, int n)
{
int i, j;
unsigned long long temp = 0;
for(i = 0; i<n; i++)
{
for(j = 0; j<n-i-1; j++)
{
if ( arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
Это консольный вывод, когда я последовательно вызываю test (), так как вы можете видеть только первый файл .txt с 10000 протестированными элементами, а затем программа была прервана;
Итак, есть ли кто-нибудь, кто может объяснить мне, в чем проблема? Спасибо за помощь.
Обновлено: для тех, кто хотел, чтобы я поделился функцией test (), я удалил строки о дереве AVL и упростил его, показав только часть пузырьковой сортировки. Это просто не сокрушает, когда пузырьковая сортировка одна, она сортирует 10.000 элементов за 0 секунд, 100000 элементов за 44 секунды, но когда дело доходит до 1.000.000 элементов, он просто ждет слишком долго, может быть, более 10 минут, но все же может Выхода не даю. Это нормально для пузырьковой сортировки тратить слишком много времени на сортировку такого количества элементов?
void test(char *fname, int n)
{
time_t start, end;
FILE *fp;
int i = 0;
unsigned long long number;
unsigned long long *unsorted = (unsigned long long *)malloc(sizeof(unsigned long long)*n);
fp = fopen(fname, "r+");
for(i = 0; i<n; i++)
{
fscanf(fp, "%llu\n", &number);
unsorted[i] = number;
}
fclose(fp);
time(&start);
bubblesort(unsorted, n);
time(&end);
printf("bubblesort function's time spent is %ld second for %d number of elements.\n", (end - start), n);
free(unsorted);
}
Это действительно длинный код, я могу поделиться им?
Как вы создаете массивы? Если вы используете VLA (массив переменной длины), вы, вероятно, взорвали свой стек. Если вы используете malloc() и др., Все будет в порядке; если вы используете глобальную переменную или даже статическую переменную в функции, все должно быть в порядке (по крайней мере, в этом отношении).
@OzanYurtsever Если он действительно длинный, попробуйте сократить его до минимума кода, в котором все еще есть проблема.
Прочтите, как создать MCVE (минимальный воспроизводимый пример), где «полная» так же важна, как и «минимальная». Обычно это означает изменение (копию) вашей программы, иногда довольно серьезно. Но да, вы должны показать достаточно кода, чтобы облегчить воспроизведение вашей проблемы. Не очевидно, что проблема в функции, которую вы показываете. Например, можно ли обойтись без сортировки дерева AVL, если вы считаете, что проблема в пузырьковой сортировке, или наоборот?
@mnistic, я выложил его полную форму, сейчас попробую сократить.
Почему вы открываете файл в режиме обновления? Вы ведь не записываете результаты во входной файл?
@Jonathan Leffler, нет, отсортированные результаты хранятся только в массивах и даже не печатаются. Для файлов .txt обновлений нет, они останутся прежними. Основная цель - вычислить время сортировки и сравнить их.
Текущий код не компилируется (отсутствует определение number). Перед обновлением проверьте и убедитесь, что проблема с кодом не устранена.
@mnistic, Когда я упростил функцию, то по ошибке удалил некоторые необходимые объявления переменных. Теперь я исправил это
Вы действительно тестировали упрощенную функцию? Он все еще рушится?
@mnistic Добавляет проверки после mallocing и fopen.
@mnistic, на самом деле, когда я попробовал еще раз, он просто не давит, когда пузырьковая сортировка одна, сортирует 10.000 элементов за 0 секунд, 100000 элементов за 44 секунды, но когда дело доходит до 1.000.000 элементов, он просто тоже ждет долго, может быть, более 10 минут, но все равно не может дать никакого результата. Это нормально для пузырьковой сортировки тратить слишком много времени на сортировку такого количества элементов?
Когда я использую код, кажется, что он работает. На 10000 случайных чисел требуется меньше секунды; на 100 000 случайных чисел потребовалось около 17 секунд. Я все еще использую сортировку 1 000 000 - это, вероятно, займет около получаса. Я не буду рассчитывать время сортировки 10M; это слишком долго. (Использование GCC 8.2.0 на MacBook Pro под управлением macOS 10.14.1 Mojave.) Итак, как и раньше, проблема явно не в коде, который вы показываете. Обратите внимание, что пузырьковая сортировка - это алгоритм O (N²), поэтому, когда вы умножаете ввод на 10, его выполнение занимает примерно в 100 раз больше времени.
@OzanYurtsever Да, пузырьковая сортировка ужасная: vinayakgarg.wordpress.com/2011/10/25/…
@JonathanLeffler, мне кажется, я понимаю, в чем я ошибаюсь. Я не освобождаю свое дерево после тестирования одного файла .txt.
Спасибо всем, я собираюсь написать функцию, чтобы освободить свое дерево, и поделюсь результатами отсюда.
В ПОРЯДКЕ; это, вероятно, объяснило бы это. Дерево будет занимать значительно больше места, чем массив. Это также демонстрирует, что вы должны ошибаться при проверке операций открытия файлов и операций выделения памяти.
Вы забыли опубликовать код функции
test().