Re: Сортировка огромного объема в "реальном времени"

From

Pertzel Family ()

To

Mike Makhov

Date

2002-09-04T20:54:57Z

Area

RU.ALGORITHMS

From: "Pertzel Family" <voldemar@relhum.org>


"Mike Makhov" <Mike.Makhov@f909.n5020.z2.fidonet.org> wrote in message news:1031153811@f909.n5020.z2.fidonet.ftn...

>   Может кто пояснит алгоpитм "соpтиpовки слиянием" для данного конкpетного
> случая ?

есть объект А -- отсортированный файл (для
определенности -- по возрастанию), есть
объект Б -- тоже что-то отсортированное
строим объект Г -- отсортированный файл

определяем два текущих элемента а и б
читаем элемент а из А (самый маленький)
и б из Б.
в цикле, который заканчивается, когда
очередное чтение невозможно {
  если а < б, то {
    /* тут можно выбрасывать устарелые записи */
    записываем а в Г
    читаем элемент а из А
  } иначе  {
    /* тут можно выбрасывать дубли */
    записываем б в Г
    читаем элемент б из Б
  }
}
записываем в Г тот который был бОльший
при последнем сравнении; все оставшиеся
элементы, (они все в обном объекте).

Всё.

Итого, числа и чтений и сравнений и записей
не превосходят мощности объекта Г.
Быстрее не выйдет.

--- ifmail v.2.15dev5
 * Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)