Версия для печати темы

Автор: KerK 8.11.2006 14:25

Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Автор: volvo 8.11.2006 15:32

KerK, если

, то что делать с 2-мя вот такими векторами:
A = (1, 2, 3, 4, 5)
и
B = (2, 3, 4, 5, 6)?

Здесь ведь нет такого i, при котором a[i] = b[i] ...

Автор: lapp 8.11.2006 15:47

volvo, у него нумерация начинается с 1, а k>=0. Так что для твоего случая как бы k=0.
Но тогда непонятно, в чем вообще суть. Что делать с i>k+1 ? На них вообще никаких условий не накладывается?... Странно как-то

Автор: volvo 8.11.2006 15:52

Вот и я про то же (что странно)... Кстати, вроде именно лексикографическая сортировка была где-то на форуме... Да и вообще алгоритмов сортировок штук 10 выложено, причем с описанием, какой требует меньше памяти, а какой - работает быстрее... Или основная проблема как раз и есть в определении отношения больше/меньше между векторами?

Автор: Michael_Rybak 8.11.2006 15:55

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


http://en.wikipedia.org/wiki/Bucket_sort здесь не подходит, потому что у нас нет ограничений на числа. Поступим по аналогии.

Идея: сначала сортируем векторы по первому элементу. Затем пробегаем по ним в этом порядке (в порядке неубывания первого элемента), выделяем группы векторов, у которых первый элемент одинаковый, и для каждой такой группы вызываем рекурсивно сортировку по второму элементу, и т. д.

Чтобы не тратить кучу времени на обмен местами векторов, сами вектора не трогаем, а сортируем только номера векторов.

Примерно так:

//не тестил и не компилил
//volvo, ты мне простишь неработающие в TP комментарии "//"?

var vv: array[1 .. n, 1 .. len] of integer;
    sorted: array[1 .. n] of integer; //сортируемый массив номеров векторов

procedure SortAt(low_bound, up_bound, sort_by: integer)
  //отсортировать группу от sorted[low_bound] до sorted[up_bound] по элементу sort_by

  var i, j, t: integer;
begin
  if sort_by = len + 1 then //сортировка по (len+1)му элементу -> процесс окончен
    exit;

  //сортируем пузырьком
  for i := 1 to up_bound - low_bound + 1 do
    for j := low_bound to up_bound - 1 do
      if vv[sorted[j], sort_by] > vv[sorted[j + 1], sort_by] then 
      begin
        //меняем вектора местами
        t := sorted[j];
        sorted[j] := sorted[j + 1];
        sorted[j + 1] := t;
      end;
      
  //теперь выделяем группы и рекурсивно их сортируем
  i := low_bound;
  while i <= up_bound do begin
    j := i;
    while (j < up_bound) and (vv[sorted[j + 1], sort_by] = vv[sorted[j], sort_by]) do
      Inc(j);

    //у векторов от sorted[i] до sorted[j] совпадает элемент sort_by
    SortAt(i, j, sort_by + 1);
    i := j + 1;
  end;
end;

var i: integer;
begin
  ...//читаем вектора
  
  //изначальный порядок
  for i := 1 to n do
    sorted[i] := i;

  SortAt(1, n, 1);
  ...
end.

Пузырьком я, понятно, для наглядности. Вставь там какую-нибудь быструю сортировку.

Сложность этого алгоритма будет O(len * n log n). Быстрее, надеюсь, нельзя
И памяти дополнительной - O(n). Пробуй, спрашивай.

Автор: KerK 8.11.2006 17:34

Большой фенкс! Сегодня вечером попробую!