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

[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]

Допустим. Что-то не верится, но сейчас обязательно посмотрю.

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


Вот сделал с "тиками" http://volvo71.narod.ru/time_count.htm#time_rdtsc_32.

Нижняя таблица - относительно максимального (в промилле).
Что-то не очень уж точно, есть заскоки, но такого заскока, как я выше описал не наблюдается.

Не могли бы вы попробовать это запустить под DOSoм, может нормально получится:
с GetTime:  forWin.rar ( 4.39 килобайт ) Кол-во скачиваний: 451

с "Тиками":  forWin_tics.rar ( 4.72 килобайт ) Кол-во скачиваний: 492


Сообщение отредактировано: sheka - 17.04.2011 22:42