В моей книге по программированию в ней есть сортировка «Выбор», в которой каждый раз выполняется n проходов. Есть ли ситуация, когда нужен n-й проход? Разве n-1-й проход не будет каждый раз заменять n-1-й элемент на n-й?
Требуется n-1 проходов. Общее количество сравнений составляет (n-1) + (n-2) + …… + (n-k) +… 3 + 2 + 1 = n (n-1) / 2, а сложность составляет O (n ^ 2)