November 2nd, 2009

О гриппе и масках в частности

Задача

В прошлом посте с задачей анонимный комментатор предложил ещё одну.

При исследовании барьеров обучения один из испытуемых предложил следующий алгоритм сортировки массива: "Нужно просто двигать элементы, пока не получится правильный ответ." Уточним этот алгоритм таким образом:
Пока (массив a не отсортирован) {
  Выбрать два случайных индекса i и j в массиве;
  Поменять a[i] и a[j] местами;
}

1. Какова в среднем сложность работы этого алгоритма?
2. Как она изменится, если менять местами элементы только тогда, когда больший из них имеет меньший индекс?