Civil Engineering Reference
In-Depth Information
Algorithm QuickSort (n, A)
// H, T are integer arrays, H
L
= Head of list L, T
L
= Tail of list L
// I = Head of list, J = Tail of list, IP = Pivot position, L = Number of
// lists
{
L = 1; H
1
= 1; T
1
= n
While (L > 0) {
I = H
L
; J = T
L
; L = L - 1
Pivot (A, I, J, IP)
If (I < IP - 1) then
L = L + 1; H
L
= I; T
L
= IP - 1
End if
If (IP + 1 < J)
L = L + 1; H
L
= IP + 1; T
L
= J
End if }}
Procedure Pivot (A, I, J, IP)
// P = Pivot, IP = Position of pivot, I = Head of list, J = Tail of list,
// A
L
= Element at index L
{
K =(I + J)/2 // Get pivot value at the middle of the list
P = A
K
; A
K
= A
I
; A
I
= P; IP = I
Loop: L = I + 1,J
T = A
L
If (T < P) then
// If (T < P or T = P and IP < K) then
IP = IP + 1; A
L
= A
IP
; A
IP
= T // IP increases by 1 for each A
L
smaller
// than P
End if
End loop L
A
I
= A
IP
; A
IP
= P}
2.6.4 Bin sort
Bin sort is also known as bucket sort or address sort. In the previous sorting algorithms,
items are sorted by means of comparisons and element swaps without specific reference to
the actual values of the items, and as a result, the number of operations depends only on
the positions of the data but not on the values of the data to be sorted. Bin sort employs an
entirely different approach in which data are sorted based on their specific values and not
on their order on the list. As the name of the sorting method suggests, a number of bins are
prepared so that the items are spread into the bins according to their actual values, such that
data of smaller values are put in the top bins, and data of larger values are put in the bot-
tom bins in some linear interpolation manner. The number of bins used, N, depends on the
available memory, and usually it is more efficient to use a large N that is equal to 2n or 3n,
where n is the number of data to be sorted.
Let N be the number of bins available. Before a bin can be assigned to a particular value,
we have to find out the range of the data. Suppose x
min
and x
max
are, respectively, the mini-
mum and maximum values in the array; then the bin size, d, is given by
x
−
x
max
in
d
=
N
