Как правильно определить, какое число итераций необходимо?
А двавайте велосипед не выдумывать. Есть такой раздел вычислительной науки.  "Теория алгоритмов" называется.  Он-то как раз и занимается тем, что объясняет, как оценить вычислительную сложность алгоритмов, в том числе ОЦЕНИВАЕТ, сколько циклов, операций сравнения и пр. требуется для того или иного алгоритма. 
Просто после вопроса " единственный вариант -  сравнивать список "до" итерации и "после". Но в таком случае, не будет ли затраты на подобные сравнения "затратнее" холостых циклов?"  становиться понятным, что тут не на конкретный вопрос отвечать надо, а с азов начинать.  Ведь и то что это "единственный способ", и про то что сравнение можно сравнивать с холостым циклом -  про все это говориться в Теории алгоритмов. Причем как правило - с самого начала.
Можно завести флаг "менялись ли элементы в цикле". Перед циклом его сбросить, при перестановке двух элементов - установить. А сам внешний цикл можно сделать while.

Заранее определить, сколько будет итераций - очень сложно.