Question

Show that the shaker sort has$\mathit{O}\left(n^2\right)$complexity measured

in terms of the number of comparisons it uses.

Short answer

Shaker sort has $O\left(n^2\right)$complexity measured in terms of the number of comparisons it uses.

Step-by-step solution

Shaker Sort

Shaker sort compares two consecutive elements in the list and interchanges them if they are not in the correct order The algorithm first moves from left to right through the list, then from right to left, then from left to right again and so on.

Let the list contains n elements.

On the first iteration, there arecomparisons, because there is n - 1 consecutive pairs.

On the second iteration, there are n -2comparisons, because we already know that the last element is in the correct position (and thus we check one pair less).

Similarly, there will be n - kcomparisons on the kth iteration, until there is only I comparison made

Number of comparisons

In total, the number of comparisons is then:

$$\begin{gathered} (n-1)+(n-2)+\dots +3+2+1=\sum _{i=1}^{n-1} i\left[\sum _{i=1}^n k=\frac{n(n+1)}{2}\right] \\ =\frac{(n-1)n}{2} \\ =\frac{1}{2}{n}^2-\frac{1}{2}n \end{gathered}$$

Thus, there is $=\frac{1}{2}{n}^2-\frac{1}{2}n$compassion and $\frac{1}{2}{n}^2-\frac{1}{2}n$is$O\left(n^2\right)$ .