1236. Сортировка

Сортировка

Задачи на идею
Дерево отрезков, декартово дерево, √-декомпозиция
Олимпиадные задачи на русском языке

11/09/2009	Заочный тур личного первенства (B)
14/07/2016	Лето 2016 - 9 (E)

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)

program BubbleSort;
var
  Arr:Array[1..100000] of Integer;
  n, i, Temp, Count, NLoop : Integer; 
  Flag : Boolean; 
begin
  read(n);
  for i:=1 to n do
    read(Arr[i]);
  Count := 0;
  NLoop := 0;
  repeat
    Flag := False;
    for i := 1 to n - 1 do
      if Arr [i] > Arr [i + 1] then
      begin 
        Temp := Arr [i]; 
        Arr [i] := Arr [i + 1];
        Arr [i + 1] := Temp; 
        Flag := True;
        inc(Count);
      end;
    inc(NLoop);
  until not Flag;
  writeln(Count,' ',NLoop);
end;

#include <stdio.h>
int Arr[100000];
int n, i, Temp, Count=0, NLoop=0, Flag;
int main()
{ scanf("%d",&n);
  for(i=0; i<n; ++i)
    scanf("%d",&Arr[i]);
  do
  { Flag=0;
    for(i=0; i<n-1; ++i)
      if(Arr[i]>Arr[i+1])
      { Temp=Arr[i];
        Arr[i]=Arr[i+1];
        Arr[i+1]=Temp;
        Flag=1;
        ++Count;
      }
    ++NLoop;
  } while(Flag);
  printf("%d %dn",Count,NLoop);
  return 0;
}

4
10 1 2 1

4 3