Programming 11/12: Sorting Practice

Complete the practice questions with a partner. Check your responses with another group when done.

1. An algorithm takes exactly S(n) = n – 3n2 + 2n3 steps to solve a Rubik’s cube of size n.
  a) Calculate the exact number of steps to solve a 10x10x10 cube.
  b) Estimate the number of steps to solve a 10x10x10 cube.
  c) Express the complexity of the algorithm using the order of magnitude.

2. With respect to n, how many times will the message box appear?
  a) Exact
  b) Estimate
  c) Order

For i = 1 to 2*n
  For j = 0 to n
    For k = -n to n
      MsgBox("Spam")
    Next k
  Next j
Next i

3. How many steps are required to sort an array with 50 elements using monkey sort?

4. How many steps are required to sort an array with 50 elements using merge sort?

5. How are selection sort and bubble sort similar? How are they different? List as many similarities and differences as you can.

6. Give an example of an array where bubble sort is a) faster than selection sort. b) slower than selection sort.

7. Sort the list {9, 0, 2, 1, 4} in ascending order using the algorithm below. Show your work.
  a) selection sort
  b) bubble sort
  c) merge sort