Sorting algorithm with infinite swaps

Question

I would like some help with the following problem I found in a textbook.

sort (array[], nr_of_item)
{
   while(true)
     i:=value from an n-sided fair dice roll
     j:=value from an n-sided fair dice roll
     if (i > j)
       swap i and j
     if (array[i] > array [j])
       swap array[i] and array[j]
     end while
}

Now, it says that it does NOT describe a correct algorithm. But then they say:

After a while the array should be sorted and prove that the number of comparisons to sort the array is O(n^3) if the input is unsorted.

One other question is:

verify if the algorithm will sort the array in O(n) time

I really can't understand how you could prove this because of the randomness of i and j.

I guess it's a probabilistic thing. As the number of iterations increases, the probability that the array is unsorted decreases, and there's probably an asymptotic relationship. — Barmar
but here your loop runs for infinite time, I mean what stops or breaks your while() ? — Basheer_CAD
It is not meant to stop. The algorithm given in the textbook is wrong because it never stops. But the two questions should still be answerable. — user3143696

Unknown Unknown · Accepted Answer · 2015-01-02T09:05:50

The i and j refers to the index and j is always adjusted to be the greater of the two. This means the element specified by index i, denoted as x, will locate to the left of the element at index j, denoted as y.

Then you swap the element only if y and x are unsorted, meaning x is greater than y and by the position of their indexing, is located to the left of y, and hence is out of order. This guarantees that the function only gets closer (not further away) to the sorted state.

Now, as for the complexity, imagine bubble sorting, which is designed to iterate through the array, as opposed to making selections at random. This has a complexity of n-squared. There is something else happening here though. You choose two elements at random, and hence n-choose-1 times the complexity of bubble sorting, which becomes n-cubed.

Each call of the function makes two comparisons, specifically 2. Therefore the complexity is n-cubed times 2 which can be denoted with a big-O notation as n-cubed.

Sorting algorithm with infinite swaps

1 Answers