**
STEP 1. Choosing the pivot**

**Choosing the pivot is an essential step.**

Depending on the pivot the algorithm may run very fast, or in quadric time.**:**

**
**
- Some fixed element: e.g. the first, the last, the one in the middle
This is a bad choice - the pivot may turn to be the smallest
or the largest element,

then one of the partitions will be empty.

- Randomly chosen (by random generator ) - still a bad choice.
- The median of the array (if the array has N numbers, the median is the [N/2] largest number. This is difficult to compute - increases the complexity.
- The median-of-three choice: take the first, the last and
the middle element.

Choose the median of these three elements.

**Example:**

8, 3, 25, 6, 10, 17, 1, 2, 18, 5

The first element is 8, the middle - 10, the last - 5.

The three elements are sorted: [5, 8, 10] and the middle element is 8. This is the median.

**
STEP 2. Partitioning**

Partitioning is illustrated on the above example.

After finding the pivot the array will look like this:

**5,** 3, 25, 6, **8,** 17, 1, 2, 18, **10**
1. The first action is to get the pivot out of the way - swap it with the next to the last element

**5**, 3, 25, 6, 18, 17, 1, 2, **8, 10**

**
**
2. We want larger elements to go to the right and smaller elements
to go to the left.

Two "fingers" are used to scan the elements from left to right
and from right to left:

[5, 3, 25, 6, 18, 17, 1, 2, 8, 10]
^ ^
i j

**Note:** we know that the first element is smaller than the pivot, so the first
element to be processed is the element to the right. The last two elements are the pivot
and an element greater than the pivot, so they are not processed.

- While
**i** is to the left of **j**, we move **i**
right, skipping all the elements

less than the pivot.
If an element is found greater then the pivot, **i** stops
- While
**j** is to the right of **i**, we move **j **
left, skipping all the elements

greater than the pivot.
If an element is found less then the pivot, **j** stops
- When both
**i** and **j** have stopped, the elements are
swapped.
- When
**i** and **j** have crossed, no swap is performed,
scanning stops,

and the element pointed to by **i**
is swapped with the pivot .

In the example the first swapping will be between 25 and 2,
the second between 18 and 1.