Время выполнения алгоритма Опции

[sheka]

Упорядочить отдельно каждое сечение трехмерного массива А [p, m, n] насквозь по колонкам по неубыванию.

сортировка (Показать/Скрыть)

  function PCube_SelectExchange2_byTruthIndex(var Cube: PCube; const p, m, n: word): longint;
  var
    B: MyType;
    i,
    ks, js,
    jt, kt: word;
    StartTime, FinishTime: TTime;
  Begin
    with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds);
    for i := 1 to p do
      for ks := 1 to n do
        for js := 1 to m do
        begin
          for jt := js+1 to m do
            if Cube^[i]^[jt]^[ks] <= Cube^[i]^[js]^[ks] then
            begin
              b := Cube^[i]^[jt]^[ks];
              Cube^[i]^[jt]^[ks] := Cube^[i]^[js]^[ks];
              Cube^[i]^[js]^[ks] := b;
            end;
          for kt := ks+1 to n do
            for jt :=1 to m do
              if Cube^[i]^[jt]^[kt] <= Cube^[i]^[js]^[ks] then
              begin
                b := Cube^[i]^[jt]^[kt];
                Cube^[i]^[jt]^[kt] := Cube^[i]^[js]^[ks];
                Cube^[i]^[js]^[ks] := b;
              end;
        end;
    with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds);
    PCube_SelectExchange2_byTruthIndex := ResTime(StartTime, FinishTime);
  end;

Сортировка выдает удивительные вещи для разных размеров массива, хотя по идее должна выдавать одинаковые(как-бы логично):
Ведь если(допустим массив отсортирован) посчитать количество таких (первых)

выражений (Показать/Скрыть)

if Cube^[i]^[jt]^[ks] <= Cube^[i]^[js]^[ks] then

то получится p*n*(m²+m-2)/2, а таких (вторых)

выражений (Показать/Скрыть)

if Cube^[i]^[jt]^[kt] <= Cube^[i]^[js]^[ks] then

то получится p*m*(n²+n-2)/2*m
Если все это упростить и построить график http://www.wolframalpha.com/input/?i=plot+...10%2C+n%3D1..10 то он окажется почти симметричным относительно m и n, без резких перегибов в какую либо сторону.

Сообщение отредактировано: sheka - 16.04.2011 11:52

[volvo]

По заданию матрицы упорядочены насквозь по столбцам.

В программе присутствует выбор: упорядоченная/случайная/обратно упорядоченная? Присутствует. Зачем, спрашивается, если по заданию "матрицы упорядочены насквозь по столбцам." (С)?

//эта   
//и эта строки у Вас были наоборот. 

Не понял. Ничего, что мне нужно было заполнение именно в том виде, в котором я показал? Или, пардон, для того, чтоб делать тесты, мне надо получить указание, КАК их делать? Тогда кому нужны такие тесты? Я захотел, чтобы матрица инициализировалась ровно в том же порядке, в котором и создается: массив

   54   59   71   84   60   85   54   84   42   62   64   38   43   29   89    5
   96   27   38   47   79   81   52   47   56   39   92   83    7   33    8   64
    2   36   83   95   77   14   87   87   97   47   79   80   46   52   78   67
   11   72   63   58   14   53   94   75   52   10   41   47

привел к инициализации матрицы:

Layer:1
   54   59
   71   84
   60   85
   54   84
   42   62
   64   38

Layer:2
   43   29
   89    5
   96   27
   38   47
   79   81
   52   47

Layer:3
   56   39
   92   83
    7   33
    8   64
    2   36
   83   95

Layer:4
   77   14
   87   87
   97   47
   79   80
   46   52
   78   67

Layer:5
   11   72
   63   58
   14   53
   94   75
   52   10
   41   47

, т.е., построчно. Что в этом неправильного? Я создаю не упорядоченную матрицу, а случайную, как хочу, так и инициализирую. Кстати, заметь:

procedure PCube_FillRandom(var Cube: PCube; const p, m, n: word);
var
  i, j, k: word;
begin
  for i := 1 to p do
    for j := 1 to m do
      for k := 1 to n do
        Cube^[i]^[j]^[k] := random(p*m*n)+1
end;

, значит, правильно, а у меня - "наоборот"? Очень интересно. С чего бы это так? В своем глазу чего-то не замечаем? Продолжай в том же духе... Далеко пойдешь... У меня к твоей задаче интерес улетучился.


Кстати. Особое внимание я бы рекомендовал уделить проверке освобождения памяти. Ибо при запуске программы без моих исправлений после теста на 3-4 матрицах большого размера (порядка 100-400) в момент выхода из программы heaptrc печатает лог, где содержатся утечки (ну, это ты должен помнить, я где-то уже рассказывал, как ловить утечки памяти). Так вот печать этого лога занимает порядка двух минут. Там ДИКАЯ утечка. Не отрабатывают процедуры Destroy так, как они должны отрабатывать, не вся память чистится. К тому же выход из программы по Halt-у это плохой стиль.