I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the values ​​of $x$ and $y$.

Algorithm StoogeSort:
procedure StoogeSort(A[0...n −1])
    if n = 2 ∧ A[0] > A[1] then
        swap(A[0], A[1])
    else if n > 2 then
        m = ceil(2n/3)
        StoogeSort(A[n−m ...n−1])

The problem demands the following:

  • Show that the algorithm correctly orders the array A of n elements.
  • Would it work correctly if we replaced ceil($\frac{2n}{3}$) with floor($\frac{2n}{3}$)? Justify your answer.
  • Give a recurrence for the number of comparisons between elements of A that StoogeSort performs with n elements.
  • Solve the recurrence for the number of comparisons. (Hint: skip functions ceil and functions floors, solve exactly the result.)
  • Show that you execute at most $ {n}\choose{2} $ swap operations. (Hint: How many comparisons are required to locate the element in position k if it is at start?)

I intuit that item two works changing ceil by floor so if the length of the arrangement is odd it does not matter if I take the larger half at the beginning or after the middle of the arrangement. But how do I show this?

I have the following help:
For the first bullet, use induction: It is easy to see it works for 1 or 2 items. Prove that if it works for $n−1$ or fewer items, then it also works for n items. For the 3rd & 4th bullets, $c_1=0$, $c_2=1$ and $c_n=3c_m$. For the final bullet, show that any pair of items is never swapped more than once.

How should I interpret the help for bullets 4 and 5? Thanks in advance.

  • 1
    $\begingroup$ "Item two works." Have you checked when $n=4$, the first case when it might make a difference? $\endgroup$ – John L. May 20 '19 at 4:02
  • $\begingroup$ "Any pair of items is never swapped more than once" means exactly what it means. For example, suppose we just swapped (5,3) to be (3,5). Then 3 will always be before 5 from now on. The pair $\{5,3\}$ will not be swapped any more. $\endgroup$ – John L. Jun 5 '19 at 20:56

Here are some more hints:

  • The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.
  • When $n=4$, the algorithm sorts $a_1,a_2$, then $a_3,a_4$, then $a_1,a_2$. You can easily give an example showing that this doesn't work.
  • You should be able to solve this yourself.
  • The recurrence in the preceding bullet involves $m = \lceil \frac{2n}{3} \rceil$. This part asks you to replace $m$ with $\frac{2n}{3}$, and then solve the recurrence using the master theorem.
  • For a permutation $\pi$, the number of inversions is the number of pairs $i<j$ such that $\pi(j)<\pi(i)$. A permutation can have at most $\binom{n}{2}$ inversions (this is the number of pairs $i < j$). Each swap operation reduces the number of inversions by 1.
| cite | improve this answer | |
  • $\begingroup$ Thanks for your help!. It is correct for bullet 4 to say that if reorganizing the array takes linear time, the recurrence would be: $ C (n) = 3C (2n / 3) + O (n) $?, to which applying the master theorem will result in: $ C (n) = \Theta (n ^ {\ log_ {3/2} 3}) $ $\endgroup$ – FredieF May 21 '19 at 17:01
  • $\begingroup$ The exact recurrence depends on implementation details. If you implement it using pointers, you can improve $O(n)$ to $O(1)$. $\endgroup$ – Yuval Filmus May 21 '19 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.