Добавление элемента в отсортированную структуру.

← →
Riply © (2007-04-11 05:27) [0]

Здравствуйте !
Допустим, у нас есть некая структура, отсортированная в соответствии с неким правилом.
Нам надо добавить в нее новый элемент, сохранив сортировку.
Для наглядности возьмем TList.
Добавить элемент можно двумя способами:
1.
List.Add(NewElement);
List.Sort(SortCompare);
2.
Находим индекс для вставки (в соответствии с нашим правилом сортировки)
List.Insert(Index, NewItem);

Допустим, у нас есть List с N элементами, и мы хотим добавить еще M элементов.
Как выбрать, из перечисленных выше способов добавления, наиболее оптимальный
для конкретных значений N и M ?

← →
SlymRO © (2007-04-11 05:41) [1]

1. Сортируем множество M
2. Вставляем M[i] в List по нужному индексу
3. Для нахождения дальнейших индексов за начало списка List брать предыдущий индекс.

//forward declaration
procedure Sort(array or list);
function FindMinIndex(First,Last,Value,List):integer;
//...

Sort(M);
index:=0;
for i:=0 to length(M)-1 do
begin
index:=FindMinIndex(index,List.Size-1,M[i],List);
List.Insert(M[i]);
end;

← →
SlymRO © (2007-04-11 05:44) [2]

SlymRO © (11.04.07 5:41) [1]
List.Insert(M[i],Index);

← →
SlymRO © (2007-04-11 05:51) [3]

Модификация 2.:
First мы ограничили предыдущим индексом
Но можно и ограничит и Last произведя предварительно поиск и вставку последнего элемента M-

Sort(M);
index:=0;
LastIndex:=FindMinIndex(index,List.Size-1,M[High(M)],List);
List.Insert(M[High(M)],LastIndex);
for i:=Low(M) to High(M)-1 do
begin
index:=FindMinIndex(index,LastIndex,M[i],List);
List.Insert(M[i],index);
end;

← →
MBo © (2007-04-11 06:13) [4]

Решение задачи зависит от порядка N и M.
Если сразу добавлять M, сравнимое с N, то проще просто добавить, затем пересортировать.
Вообще для динамического поддержания сортированного порядка есть специальные структуры данных - например, бинарные деревья (лучше сбалансированные - например, RB или AVL), очереди по приоритетам или кучи (Heap). Они позволяют выполнить операции вставки за O(LogN) времени, в то время как массив или список требует O(N) времени (у массива - на сдвиг, у списка - на поиск).

← →
MBo © (2007-04-11 06:24) [5]

Пардон, антитезу забыл дописать
>Если сразу добавлять M, сравнимое с N, то проще просто добавить, затем пересортировать.

Если же M заметно меньше N, то можно отдельно отсортировать эти новые элементы и выполнить слияние сортированных массивов - время O(MLogM +(M+N))~O(N+M)

← →
Думкин © (2007-04-11 08:57) [6]

> MBo © (11.04.07 06:24) [5]

Сам и ответил на вопрос, который дал в ветке на сообразительность. :(

>Думкин
Ну это я извращенно - сначала ответил, потом спросил ;)
А ты сюда не читай, ты туда только читай :)) // © Джент. удачи

Спасибо !
P.S. А про какую ветку идет речь ?

>А про какую ветку идет речь ?
http://delphimaster.net/view/15-1176199472/

Добавление элемента в отсортированную структуру. Найти похожие ветки