Bogo sort!

Consider an algorithm that randomly shuffles the list, check if the list is sorted, and return.

additional information

Expected Running Time

The expected running time is the number of iterations (\(n!\), in expectation) times the time per iteration (\(n\)).

So the expected running time is \(O\qty(n n!)\).

Worst Case Running Time

Infinite (i.e. if randomness is fixed it will take forever).

Some Expectations of Bogo Sort Characteristics

Let \(X_{i} = 1\) if \(A\) is sorted after iteration \(i\), \(0\) otherwise. Assuming distinct entries, then \(\mathbb{E}[X_{i}] = \frac{1}{n!}\) (because your list has \(n\) things, so the chance of any given shuffling being sorted is \(\frac{1}{n!}\).)

how many times do you have to do the trial to get at least one success

constituents

• \(p\) is the probability of one individual success
• \(x\) is the number of trials

requirements

\begin{equation} P(X = x) = \qty(1-p)^{x-1} p \end{equation}

which represents the probability of getting a success on the \(x\) trial

additional information

\begin{equation} \mathbb{E}[X] = \frac{1}{p} \end{equation}

A Las Vegas algorithm is a randomized algorithm that always works and its probably fast.

(This is as opposed to monte-carlo algorithm, which is always fast and probably works.)

A randomized algorithm for sorting.

1. pick a pivot
2. partition the array into bigger and less than the pivot (see k-select)
3. recurse on L, R
4. return concatenated L, pivot, R

additional information

stability

quicksort is not stable (it doesn’t preserve equal elements’ order).

recurrence relationship

\begin{equation} T\qty(n) = T\qty(|L|) + T\qty(|R|) + O\qty(n) \end{equation}

recurse on left, recurse on right, the partitioning. In an idea world, suppose the array is split exactly in half, then: