Civil Engineering Reference
In-Depth Information
At any level of subdivision, pivots can be inserted in all the lists by scanning through all
the n items in the lists. Hence, the number of operations required to sort an array of n items
can be estimated by
N ≈ kn ≈ nlog(n)
In the worst case, the pivots always cut at the head or the tail of a list such that the
length of the sub-list is reducing at a very slow rate, resulting in an order
O
(n
2
) algorithm.
However, the asymptotic performance of quick sort for random or evenly distributed data
is of order
O
(nlog(n)), and thus, it is one of the most efficient and reliable sorting algo-
rithms available.
Although the pivot can be chosen at random, it is more advantageous to pick the middle
element as the pivot, as shown in Figure 2.36, for the sorting of the array [7, 9, 4, 1, 3, 6, 8].
As shown in Figure 2.36, the hatched elements serve as pivots, and their final positions
are shaded. Once a pivot is selected, all the elements smaller than the pivot are placed to the
left of the pivot by means of element swaps, and automatically, all the elements greater than
or equal to the pivot will stay on the right of the pivot. When all the elements on the list are
scanned through and the necessary swaps are done, the pivot will find its correct position on
the original list. As shown in Figure 2.36, in the first subdivision, '1' is chosen as the pivot,
and as it is the smallest number in the list, all the numbers are placed to the right or at the
lower part of the list. As a result, '1' occupies the first position of the list, and it turns out to
be the correct position on the list. In the next level of subdivision, '7' is chosen as the pivot;
three numbers are smaller than '7', and they are put to the left or on the upper part of the
list, and the result is that '7' is on the fourth position of the sub-list and the fifth position of
the entire list if the head of the list is properly recorded, i.e. '6' is at the second position of
the original list. At the third level of subdivision, two sub-lists are generated, each of which
is assigned a pivot. '4' is the pivot for the first sub-list and '9' is the pivot for the second
sub-list, and all the numbers find their correct positions on the original list after fixing the
positions of the pivots by element swapping.
Although the quick sort can be easily implemented by means of recursive programming,
the process could be speeded up by avoiding the recursive procedure using a loop over the
sub-lists, provided that the bounds of the sub-lists are well kept track of. The following is
the
pseudo-code
of the quick sort algorithm based on a loop over the sub-lists.
7
1
6
9
3
9
4
4
4
4
3
1
6
7
3
7
3
6
8
6
9
8
9
8
8
Figure 2.36
How lists are divided by pivots in Quicksort.
