순열의 인버전 수를 생각하자. 연산에서 실제로 자리를 바꾸는 두 원소의 값을 라고 하자. 와 는 고른 구간에서 가장 작은 원소와 두 번째로 작은 원소이므로, 두 위치 사이에 있는 모든 원소는 보다 크다. 따라서 이 중간 원소들과 가 만드는 인버전의 총수는 교환 전후에 변하지 않고, 와 사이의 인버전 여부만 바뀐다. 그러므로 한 번의 연산은 전체 인버전 수를 정확히 만큼 증가시키거나 감소시킨다. 정렬하려면 모든 인버전을 없애야 하므로 필요한 연산 횟수는 처음 인버전 수 이상이다.
길이 인 구간 을 고르면 그 두 원소가 바로 가장 작은 원소와 두 번째로 작은 원소이므로 두 원소를 단순히 교환하는 연산이 된다. 따라서 인접한 역전쌍을 하나씩 교환하는 버블 정렬을 그대로 사용할 수 있다. 각 교환은 인버전을 정확히 하나 줄이고, 모든 인버전이 사라지면 정렬된다.
따라서 버블 정렬의 교환 횟수가 최소 연산 횟수이다. 시간 복잡도는 이고, 출력되는 연산 수도 최대 개이다. Solution written by GPT5.6
