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

[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 15:52

[sheka]

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

procedure PCube_Init(var Cube: PCube; const p, m, n: word);
   var
     i, j, k: word;
     curr : Word;
   begin
     curr := 1;
     for i := 1 to p do
       for k := 1 to n do     //эта   
          for j := 1 to m do //и эта строки у Вас были наоборот. 
         
         begin
           Cube^[i]^[j]^[k] := R[curr];
           Inc(Curr);
         end;
   end;

Меня интересует вот какой вопрос: почему там, где массив отсортирован, где этих обменов вообще нет, а только проверка условия, значения 40*40 и 400*4 совпадают, и очень отличаются от 4*400 ?

По ходу у меня комп глючный. Проверил еще на 3х - нормально. Сейчас еще в DOSboxe перепроверю - и завтра сдавать