spring2013:Funnel sort - kostja/lectures GitHub Wiki

Нужно реализовать cache-oblivious сортировку FunnelSort.

• Frigo et. al. - 1999 - Original whitepaper
• Brodal and Fagerberg - 2002 - Funnel Heaps/Lazy FunnelSort
• Brodal and Fagerberg - 2008 - Engineering a Cache-Oblivious Sorting Algorithm

• Xiao, Zhang, and Kubricht - 2000 - Improving Memory Performance of Sorting Algorithms
• Frederik Rønn - 2003 - Cache-Oblivious Searching and Sorting, M.Sc. Thesis
• Brodal and Fagerberg - 2003 - Engineering a Cache-Oblivious Sorting Algorithm

Максим Филипенко
Евгений Николаев
Кондратьев Михаил([email protected])
Андрей Мельников

1. Функция должна работать с данными неизвестного размера и неизвестным типом, так что оформить создание стоит так:
   struct Funnel *funnel_create(void *out, size_t nmemb, size_t size, cmp_t cmp);,
   где cmp_t это typedef int (*cmp_t)(const void *, const void *); Внутренняя структура struct Funnel остаётся на ваше усмотрение.

2. Передавать кол-во данных и их размер во внутрь нужно с помощью первых двух аргументов командной строки (argc and argv).

3. Генерация данных допускается:

   • В начале старта программы из функции rand().
   • До запуска программы генерируется файл, название которого передаётся третьим аргументом командной строки.

4. Создать Makefile с, как минимум, двумя таргетами:

   • all: - компиляция исходных кодов программы.
   • test: - тестирование на предзаданных файле/размере данных/кол-ва данных (Пример использования)

5. (желательно) Комментарии по вашей реализации.

• Желательно реализовывать на платформе Linux.
• Вы можете сравнить производительность по памяти с эталонной реализацией qsort в glibc.
• Замер времени можно производить с помощью утилиты time.
• По памяти - с помощью valgrind --util=cachegrind.