Здравствуйте, MichaelP, Вы писали:

MP>Собственно это я имел ввиду в своем доказательстве.

"Иметь в виду" это все могут
Словами надо говорить.
Как можно короче, яснее и неоспоримее.
Но ты всё равно молодец

Здравствуйте, Pushkin, Вы писали:

К>>Будьте проще, и к вам undefined behaviour не потянется.

P>Вот уж точно по Паркинсону.
P>Самое большое сопротивление обычно вызывает самое безобидное место.

По врачу Паркинсону?

P>Вы задачу, блин решайте, умные!

Кстати о блинах. Масленица ж!

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, mrhru, Вы писали:

P>

P>for(int i=0;i<N-1;i++)
P>  if(a[i]<a[i+1])
P>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>return a[N-1];
P>

Это сортировка пузырьком, первый проход.

Вопрос: а сколько обменов будет совершено здесь?

К>Это сортировка пузырьком, первый проход.

К>Вопрос: а сколько обменов будет совершено здесь?

И, собственно, ответ:

Пусть на отрезке [0..k] было S(k) обменов. При этом a[k] стал наибольшим.
В паре a[k], a[k+1] обмен не состоится, если a[k+1] — максимум из a[0..k+1].

Т.е. матожидание S(k+1) = S(k) + k/(k+1)

Получаем ряд:

S(N) =   0 +   1/2 +   2/3 +   3/4 + ... +   (N-1)/N =
     = 1-1 + 1-1/2 + 1-1/3 + 1-1/4 + ... + 1-    1/N =

     = N - (1+1/2+1/3+...+1/N)

Здравствуйте, Кодт, Вы писали:

К>>Это сортировка пузырьком, первый проход.
К>>Вопрос: а сколько обменов будет совершено здесь?
К>И, собственно, ответ:
К> N — (1+1/2+1/3+...+1/N)


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

Здравствуйте, Pushkin, Вы писали:

P>Логическим завершением будет вопрос о количестве присваиваний
P>во всей пузырьковой сортировке массива из N элементов.
P>Но на него я пока ответить не могу

Могу!

Сначала немного модифицируем алгоритм пузырьковой сортировки. В классическом варианте мы должны сначала сравнить и если надо обменять первую пару.Затем вторую и так далее до конца. Затем прделать это много раз, снижая границу.

Но заметим, что обслужив вторую пару, мы вполне можем ДО того, как обслужим все оставшиеся СРАЗУ обслужить первую по второму разу. От этого ровно ничего не изменится, никакие сравнения не изменят результата. Далее надо обслуживать третью пару, никуда не деться. Но потом можно сразу вторую по второму разу и первую по третьему.

Смотрите, что получается. Впереди бежит фронт и с каждым шагом пускает назад упорядочивающую волну. В результате весь хвост всегда полностью упорядочен. Назовём это пузырьковой сортировкой в форме реверсивного упорядочивания. Ещё раз подчёркиваю, она полностью эквивалентна классическому алгоритму. Мы не изменили ни числа сравнений ни числа присваиваний — просто перестановили свои операции.

Но в этой форме всё становится совершенно прозрачным!
Раз хвост всегда упорядочен, то в процессе волны надо просто найти место головному элементу. Ясно, что ему всё равно где остановиться — данный элемент группы с одинаковой вероятностью оказывается на любом месте в упорядоченном массиве. Значит средний путь n-того элемента до своего места n/2. Теперь надо просто сложить эти числа от 1 до N — получится простой ответ

F(N) = 1/2 + 2/2 + 3/2 + ... (N-1)/2 = N*(N-1)/4

Замечательный квадратичный рост.
Такой же как у числа сравнений.
Точнее, ровно в 2 раза меньше!
Это немедленно рождает желание как-нибудь поспекулировать на тему того, что каждое второе сравнение успешно. Но, я не думаю, что тут есть очевидное объяснение. Ведь совершенно ясно, что в процессе всплывания первого пузырька мы чем дальше, тем увереннее выполняем обмен. Т.е. вероятность разных результатов сравнений вовсе не фифти-фифти. Именно поэтому для числа обменов при первом протаскивании мы получили N-lnN а вовсе не N/2. С другой стороны, протащив один раз, мы явно что-то упорядочили сзади, и при следующем проходе сравнения будут уже смещены в сторону не-обмена.

И наконец, последнее замечание.
Реверсивное упорядочивание эквивалентно классическому алгоритму. Но оно лучше! Потому что может быть улучшено. Действительно, раз там всё сзади упорядочено, то на фига продолжать сравнивать после первой неудачи? Как только нашли новому элементу место, так и бросаем это дело! Таким образом, число сравнений оказывается практически равно числу присваиваний (всего лишь на N больше), т.е. для больших N ополовинивается.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Pushkin, Вы писали:

P>>Логическим завершением будет вопрос о количестве присваиваний
P>>во всей пузырьковой сортировке массива из N элементов.
P>F(N) = N*(N-1)/4

Для простой сортировки всё проще (и лучше!), чем для пузырьковой.

for(int n=N;n>1;n++)
{
  int im,m=-MAX_INT;
  for(int i=0;i<n;i++)
  if(a[i]>m)
  {
    im=i;
    m=a[i];    
  }
  a[im]=a[n-1];
  a[n-1]=m;
}

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

S(n)=1+1/2+1/3+...+1/n

то для всех проходов их будет

S(N)+S(N-1)+...S(1) = N*S(n)+S(n)-N

Те 2N присваиваний, которые в конце внешнего цикла можно добавить,
но это не меняет дела — рост NlnN — гораздо лучше, чем у пузырьков.

Может показаться разумным не заводить специальную ячейку m,
а сразу копить максимум в последнем элементе массива.

for(int n=N-1;n>0;n++)
  for(int i=0;i<n;i++)
    if(a[i]>a[n])
      SWAP(a[i],a[n]);

Казалось бы, мы ничего не теряем по сравнению с предыдущим случаем,
более того даже слегка упорядочиваем левую часть, подтаскивая к концу большие элементы.
Всяко число обменов не должно быть больше, чем NlnN

Но запрограммив таким образом я испытал шок — квадратичный рост! (0.075*N^2)
Точно выводить ручками я поленился, но качественно в чём дело, понял. Дело в том, что подтаскивая по ходу дела большие элементы поближе к концу массива мы делаем себе не лучше, а хуже! Если бы они в начале остававались, то рано попадали бы в ячейку максимума и не пускали остальных. А так, мы вынуждены пихаться малышами в начале, а потом ещё пихаться тяжеловесами в конце. Приравниваний получается больше.

Как всё забавно, на пустом месте казалось бы

Здравствуйте, Pushkin, Вы писали:


P>

P>for(int n=N-1;n>0;n++)
P>  for(int i=0;i<n;i++)
P>    if(a[i]>a[n])
P>      SWAP(a[i],a[n]);    
P>

P>Казалось бы, мы ничего не теряем по сравнению с предыдущим случаем,
P>более того даже слегка упорядочиваем левую часть, подтаскивая к концу большие элементы.
P>Всяко число обменов не должно быть больше, чем NlnN

P>Но запрограммив таким образом я испытал шок — квадратичный рост! (0.075*N^2)
P>Точно выводить ручками я поленился, но качественно в чём дело, понял. Дело в том, что подтаскивая по ходу дела большие элементы поближе к концу массива мы делаем себе не лучше, а хуже! Если бы они в начале остававались, то рано попадали бы в ячейку максимума и не пускали остальных. А так, мы вынуждены пихаться малышами в начале, а потом ещё пихаться тяжеловесами в конце. Приравниваний получается больше.

А может так попробовать:

for(int n=N-1;n>0;n--)
  for(int i=n-1;i>=0;i--)
    if(a[i]>a[n])
      SWAP(a[i],a[n]);

К сожалению, на эксперименты времени нет

Здравствуйте, MichaelP, Вы писали:

MP>А может так попробовать:
MP>

MP>for(int n=N-1;n>0;n--)
MP>  for(int i=n-1;i>=0;i--)
MP>    if(a[i]>a[n])
MP>      SWAP(a[i],a[n]);    
MP>

Вся эта задача — сплошь обманутая интуиция.
Я в принципе ожидал, что не улучшится, суть-то не изменилась — всё равно мы оттаскиваем нужные числа подальше, а потом подольше до них мудохаемся. Но чтобы время ухудшилось, этого даже я не предполагал. Нет, зависимость осталась квадратичной, но коэффициент перед N^2 увеличился с 0.8 до 2.4