Предыстория :
Есть ~млн строк длиной до ~100 символов. Добавляются (на данный момент - в массив) с нуля, но не по порядку (не сортированы вообще). 

Суть трабла : хочу добавлять строки не тупо подряд, а "со смыслом". Чтобы потом небыло проблем с сортировкой. Ну, тобы потом осталось только "собрать" в нужном порядке и получить ~млн сортированных строк. Может кто знает что можно почитать по теме или (хотя бы) на какаую тему гуглить. 

Доп. условия :
1. Количество используемой памяти значения не имеет.
2. Скорость "сборки" должна быть линейной и без "худшего случая" (в идеале).

Спасибо.

ЗЫ
Reiser4 не предлагать.



Это сообщение отредактировал(а) GrayCardinal - 8.12.2006, 21:39

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена! 

sergejzr, 
Извините, в каком месте это домашнее задание/курсовая ?  Это даже не работа   
Может тогда лучше было бы в алгоритмы ?

Добавлено @ 23:02 
  
И нету у меня никакого зачета. И не горит у меня нигде   
  

Почитай про Heap(бинарная куча), он дает возможность держать строки (и не только) в отсортированом порядке. Добавление строки занимает O(Log(N)).

В атаче отрывок из лекций Павлова.

Присоединённый файл ( Кол-во скачиваний: 9 )
 heap.doc 38,50 Kb