Столкнулся с проблемой сортировки больших файлов.
Допустим есть файл, состоящий из целых чисел. Нужно его отсортировать. Но файл состоит не из 100 и не из 10000 записей, а намного больше. Размеры файла превышают 2 Гб. Не спрашивайте, зачем это нужно  , просто нужно, очень нужно...

Возможно, есть возможность подстроить методы стандартных сортировок, таких как сортировки пузырьком, перестановкой, пирамидой и т.д.

 если у тебя есть 2 гига оперативки свободной для твоего процесса - то сортируй quick sort.
 Если нет - то слиянием по Фон Нейману

 http://www.avhohlov.narod.ru/p2100ru.htm#msort

ммм спасибо, но тогда возникает еще один вопрос. У меня есть свой алгоритм сортировки для больших объемов данных, может кто знает - его опубликовал Крис Касперски. Так вот, с такими большими объемами, в силу того, что 2 гб и более оперативки не имею, работать нет возможности. Следовательно нужно разделять этот файл на n-ое кол-во частей, сортировать каждую из них, а далее их сливать. Так вот, есть ли алгоритмы слияния, и, если есть, какие из них наиболее эффективны для такого объема информации

Это сообщение отредактировал(а) Pori - 19.12.2007, 18:22

Ну собсно тупо режешь файл на куски такого размера, чтобы каждый кусок можно было взять полностью в память. Сортируешь каждый кусок по отдельности. Потом собираешь обратно слиянием, программно буферизуя чтение-запись в массивы-кольцевые буферы.
Преимущество - чтению с диска и записи на диск подлежит удвоенный объем исходного файла. А это (чтение-запись) куда как медленнее сортировки.

PS. Лет, наверное, с 10 назад я реализовывал такую фигню еще на TBasic в ДОСе - сортировку файла порядка 50 Мбайт... резал на ломти по 56 кбайт (уж не помню почему именно так), qsort каждого куска... вполне шустренько получалось.

Это сообщение отредактировал(а) Akina - 19.12.2007, 18:38

Вот об этом и хотелось бы услышать по подробнее: какие алгоритмы слияния существуют и какие из них наиболее рациональны для больших файлов

Pori, файл состоит именно из целых чисел или это только для примера? если из целых, то в каком они диапазоне?

Добавлено через 21 секунду
.. и есть ли повторы?

Я не заморачивался тогда теорией - буферизую клок каждого файла, по курсору на файл, из текущих элементов быстренько изыскиваем минимальный, спихиваем его в выходной поток и инкрементим соотв. курсор. Если где-то буфер опустел - подчитываем. Если входной буфер забился - скидываем. Все собсно.

А вообще stab прав - может, тебя устроит сортировка подсчетом?

это только для примера, числа могут быть отрицательными, так и дробными. Диапазон от - 2147483648 до 2147483647   
повторы не исключаются

Pori, если можно гарантировать, что массив уникальных значений списка поместится в памяти - сортировка подсчетом, и не надо обсуждать.

Я бы предложил сделать пороговую предобработку, т.е разделить на n групп k/n*(max-min)<A<(k+1)/n(max-min) трудоемкость 0(n) -- вычислить min и max и раскидать по группам, а потом эти группы можно легко склеить.
Недостаток то что группы получатся неравнозначными... но можно вычислить распределение данных и исправить это линейное разбиение
min и max можно делать не полным перебором а брать каждое 100  значение, по статистике не сильно ошибемся... только нужно будет сделать две группы A(0)<min и A(n+1)>max
 

Это сообщение отредактировал(а) dereyly - 20.12.2007, 01:09

Любопытно, что это за данные, как хранятся.
У меня была когда-то, еще на 486 такая задача - решал тупо:
- открывал файл
- закачивал сколько можно
- сортировал и сбрасывал, пока он не кончится.
А потом сливал, ровно по Кнуту.

На самом деле быстрее читать большой файл сразу в бинарное дерево и скидывать его в файлы простым обходом дерева - тогда не нужна сортировка кусков.

Во-первых тема старая,
Во-вторых при больших объемах данных 

с памятью напряги.

дерево в памяти размещать? или скидывать в файл? 0_о
если в памяти - то даже под сами данные памяти не хватит(о чем было отмечено), не говоря уж про дополнительные расходы на хранение указателей.

Эм... так как можно отсортировать файл с большим количество информации(Мой файл состоит из структур с фамилиями, именами, и другими данными.)? 

Если использовать алгоритм слияния, то памяти потребуется сразу на все данные, ведь если его разделить на 2 части для сортировки, и так рекурсивно. То в результате получится 2 отсортированных массива с общим размером равным исходному файлу. Как его теперь можно будет отсортировать, если в оперативную память не уместятся ВСУ данные из файла? Даже на примере с теми же 2 Гб(А если будет больше: 10Гб, 100Гб и т.д) это сложно сделать.

P.S: Попробовал сделать таким образом: 
Входные данные: в строке по 1 фамилии.(В данном примере, в дальнейшем будет много данных).
1) разбить файл на несколько частей(в примере на 10) и читать группами. 
2) отсортировать каждый в алфавитном порядке методом пузырька и перезаписать в тот же файл(двоичный). И так до конца файла. 
3) Потом начать с середины первой группы и перейти на 2 пункт.
4) Проделывать все это пока главный флажок(FLAG) поднят.
Не знаю почему, но что то идет не так: либо получается 1 фамилия на весь файл записал кучу раз, либо еще что.
Сама программа сначала из текстового файла читает данные и записывает во вновь созданный двоичный файл. И в этом самом файле происходит сортировка.
Вот сам код:


В прикрепленном файле есть файл с этим кодом, и входные данные.

Это сообщение отредактировал(а) DTL67 - 2.3.2009, 20:56

Присоединённый файл ( Кол-во скачиваний: 16 )
 sort_file.rar 1,57 Kb