Consider the following algorithm for sorting an array segment A[0..n-1]. In the first step the algorithm performs the bubble-up operation on the range [0..n-1] and it places the smallest item on position 0. In the second step it performs the bubble-down operation on the range [1..n-1] and it places the largest item on position n-1. In the third step it performs bubble-up operation on the range [1..n-2] and it places the second smallest item on position 1. In the fourth step it performs the bubble-down operation on the range [2..n-2] and it places the second largest item on position n-2. The algorithm continues alternating bubble-up and bubble-down operations until the range consists of a single field.

(i) What is the number of swap operations performed in the worse case? Explain.

(ii) What is the average number of swap operations performed by this algorithm? Explain.