Сортировка

[Сорокина Елена]

Рассмотрим следующий алгоритм сортировки: последовательным просмотром чисел а(1)...а(n) найти наименьшее i такое, что а(i)>а(i+1). Поменять местами а(i) и а(i+1) и возобновить просмотр с начала массива. Когда не удастся найти такое i, массив будет упорядочен. Написать программу, реализующую этот алгоритм если данные представлены в виде массива, файла, списка одной и той же совокупности целых чисел, выбранных случайным образом из некоторого промежутка. Сравнить время работы программ для каждого случая. Результаты отображать на экране.

[s-andriano]

Странный какой-то алгоритм.
Подозреваю, что его сложность O(N^3).

[TinMan]

Я согласен с s-andriano, что алгоритм несколько странный.. Сложность его зависит от неупорядоченности. В самом плохом случае она может оказаться и больше, чем O(N^3), но в среднем наверное будет около O(N^(2.5 или 3)). Но вот зато реализация его изумительно проста!
Для случая массива:

  i:= 2;
  while i<=m do
    if a[i-1]>a[i] then begin
      b:= a[i-1];
      a[i-1]:= a[i];
      a[i]:= b;
      i:= 2
    end
    else
      inc(i);

Причем, при беглом взгляде может показаться, что сложность O(N)

[Paster Fob]

Сообщение от s-andriano

Странный какой-то алгоритм.
Подозреваю, что его сложность O(N^3).

Сообщение от TinMan

больше, чем O(N^3), но в среднем наверное будет около O(N^(2.5 или 3)).... сложность O(N)

И что это значит?Как это вы измеряете сложность?

[Leshii]

Ну насколько понимаю TinMan пытался бегло донести что программа довольно таки линейной сложности себто O(n);

Время работы программы линейно обычно когда каждый элемент входных данных требуется обработать лишь линейное число раз.

из за этого

 while i<=m do

= O(1), но я думаю что стоит прибавить к этому ещё 1 из за проверки внутри цикла.

Если один цикл вложен в другой и т.д. и циклы зависят от размера одной и той же переменной, то к примеру

for i:=1 to n ... 
 for j:=1 to n ... 
  for c:=1 to n ...

сложность алгоритма O(N^3);

Но я могу и ошибаться.