1 Introduction

1.5 Sorting

This is an example of probabilistic discrete algorithms.

Let us look on a probabilistic version of Quicksort. Quicksort is a recursive algorithm. The set of elements S to be sorted are split ito two parts S₁, S₂ by an element y in S so that S₁ contains all elementst smaller than y and S₂ the rest. S₁,S₂ are then sorted in the same way giving as result the sorted elements of S₁ followed by y and then the sorted elements of S₂. In Quicksort the element y is chosen deterministically, for instance the middle element in the unsorted set.

In Randomized Quicksort we choose y at random in S.

Algorithm RandQS:

Input: A set of numbers S.
Output: The elements S in increasing order.

1. Choose an element y at random from S: every element has equal probabiliy to be chosen.

2. By comparing each element of S with y (except y), determine the set S₁ of elements smaller than y and the set S₂ of elements larger than or equal to y.

3. Recursively sort S₁ and S₂. Output the sorted version of S₁, followed by y, and then the sorted version of S₂.

This algorithm has the expected running time equal O(n log n), which is the least possible. It should be noted that the expected running time holds for every input. It can also be proved that with very high probability the running time of the algortihm is not much more than the expectated running time.

1.6 Summary

There are two principal advantages to randomized algorithms. The first is performance -- for many problems, randomized algorithms run faster than the best known deterministic algorithms. Second, many randomized algorithms are simpler to describe and implement than deterministic algorithms of comparable performance. We will present algorithms that enjoy these advantages. The randomized algorithms described in this introduction are typical examples of such algorithms.