어떤 책장에 $1$번부터 $n$번까지 번호가 붙은 책들이 적당한 순서로 꽃혀있다. 도서관 사서는 이 책을 아래와 같은 방식으로 정리하고자 한다. 원래 있어야 할 위치보다 오른쪽에 있는 번호가 $k$번인 책을 뽑아서 $k$번째 자리에 그 책을 넣는다. 예를 들어 책장에 책이 $1$, $3$, $2$, $4$가 있었다면 $2$번 책을 꺼내서 두 번째 자리에 꼽으면 그 후 책은 $1$, $2$, $3$, $4$로 맞는 순서로 정렬이 된다.

(a) 이 과정을 반복한다면, 책을 어떤 순서로 사서가 뽑던지간에 언젠가는 책이 정확한 순서로 정렬됨을 보여라.
(b) 최악의 경우 최대 몇번 이 작업을 해야 하는가?