7
$\begingroup$

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm wrong):

binary-search(A,x):
    A[0]=-∞
    A[n+1]=∞    //|A|=n
    l=0
    h=n+1
    m=⌊(l+h)/2⌋
    while (h != l+1)
        if (x<=A[m])
            h=m
        else
            l=m
        m=⌊(l+h)/2⌋
    return h    //success if A[h]=x

fun-sort(A):
    for i=1 to n:
        success=false
        while (!success):
            success=true
            h=binary-search(A,A[i])
            if (A[h]!=A[i]):
                success=false
                if (i<(h-1)):
                    swap(i,h-1)
                elif (i>h):
                    swap(i,h)

As you can see, this sorting algorithm uses a binary search on a not necessarily sorted array. I realized that to get the average-case running time for Fun-sort, I needed the average number of iterations for its while cycle which I defined to be a random variable X. X would be geometrically distributed, so E[X]=1/p, where p is the probability of success of the binary-search procedure. I am stuck trying to get this probability of success.

So... any help would be very much appreciated =)

EDIT: I've been considering that binary-search will definitely fail when i < m and A[i]<=A[m]. In fact, every time the elements being compared in binary-search are an inversion, it will fail (thanks to Jorge M.). In other words, binary-search will end up in success if (x,A[m]) is not an inversion in each of the log n iterations. Now: what is the probability of (x,A[m]) being an inversion, in general?

EDIT2: I posted this on stackoverflow before I realized cs.stackexchange was a better option.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Interesting article. Empirical results indicate that the average number of failures is about $N^2/8$ for arrays of size $N\le 1000$. The analysis looks ugly, since every failure rearranges the array in such a way as to reduce the number of inversions, so it would seem that the probability of $(x, A[m])$ being an inversion changes over time. I'd guess that some sort of amortized analysis might be appropriate, but I'd also guess that it would be gruesome. $\endgroup$ – Rick Decker May 30 '14 at 20:47
  • $\begingroup$ Have you tried the standard approaches? $\endgroup$ – Raphael♦ Oct 13 '15 at 14:28
  • $\begingroup$ @Raphael They don't work. $\endgroup$ – Yuval Filmus Oct 13 '15 at 15:14
  • $\begingroup$ Your approach doesn't work, since the trials are not independent. $\endgroup$ – Yuval Filmus Oct 13 '15 at 15:14

Your Answer

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

Browse other questions tagged or ask your own question.