Civil Engineering Reference
In-Depth Information
Algorithm BinSort (n, X)
// X = Array of data to be sorted, n = number of data points
// P, H, T are integer arrays, H
L
= Head of bin L, T
L
= Tail of bin L
// N = Number of bins with more than one data, points in bin i = {X
k
:
// k = P
i
+ 1,P
i+1
}
{
Bin (n, X, P)
N = 0
Loop i = 1,n
If Pi
i+1
> P
i
+ 1) then
N = N + 1; H
N
= P
i
+ 1; T
N
= P
i+1
End if
End loop i
While (N > 0) {
J = H
N
; K = T
N
; N = N - 1; L = K - J + 1
Bin (L, X(J), P)
// X
J
in BinSort = X
1
in Bin
Loop i = 1,L
If Pi
i+1
> P
i
+ 1) then
N = N + 1; H
N
= P
i
+ J; T
N
= P
i+1
+ J - 1
End if
End loop i }}
Procedure Bin (n, X, P)
// X
i
= value of array X at index i, P = Integer array, data in bin
// k = {X
j
, j = P
k
+ 1,P
k+1
}
{
Set P to zero, P
i
= 0, i = 1,n + 1
x
min
= X
1
; x
max
= x
min
Loop i = 2,n
y = X
i
if (y < x
min
) x
min
= y
if (y > x
max
) x
max
= y
End loop i
d =(x
max
- x
min
)/n
if (d < tolerance) return // tolerance = 10
-99
// Count the number of data points in each bin k, k = 1,n
Loop i = 1,n
k = INT((X
i
- x
min
)/d)+ 1
if (k > n) k = n
P
k
= P
k
+ 1
End Loop i
// Compute P
k
= Number of data points in bins 1 to k
Loop k = 2,n
P
k
= P
k
+ P
k-1
End loop k
P
n+1
= P
n
// Collect data points in each bin k, {Y
j
, j = P
k
+ 1,P
k+1
}
Loop i = 1,n
k = INT((X
i
- x
min
)/d)+ 1
if (k > n) k = n
j = P
k
; Y
j
= X
i
; P
k
= j - 1
End loop i
