Reference no: EM131452900

The shaker sort (or bidirectional bubble sort) successively compares pairs of adjacent elements, exchanging them if they are out of order, and alternately passing through the list from the beginning to the end and then from the end to the beginning until no exchanges are needed

1. Show the steps used by the shaker sort to sort the list 3, 5, 1, 4, 6, 2.

2. Express the shaker sort in pseudo code.

3. Show that the shaker sort has O(n2) complexity measured in terms of the number of comparisons it uses.

4. Explain why the shaker sort is efficient for sorting lists that are already in close to the correct order.

5. Show that (n log n + n²)³ is O(n⁶).

6. Show that 8x³+ 12x + 100 log x is O(x³).

7. Give a big-O estimate for (x2 + x(log x)³) · (2^x+ x³).