K do
i <-- i - 1
end
end SEQSRCH
"Better is the end of a thing than the beginning thereof" - Ecclesiates 7:8
These are some of the basic search/sort algorithms.
Note: This page will always be under construction.
procedure SEQSRCH(F,n,i,K)//Search a file F with key values K1, ...,Kn for a record Ri such that Ki = K. If there is no such record, i is set to 0//
K0 <-- K; i <-- n
while Ki K do
i <-- i - 1
end
end SEQSRCH
This algorithm requires O(log n) key comparisons.
procedure BINSRCH(F,n,i,K)//Search an ordered sequential file F with records R1, ...,Rn and the keys K1
K2 ... Kn for a record Ri such that Ki = K; i = 0 if there is no such record else Ki = K. Throughout the algorithm, l is the smallest index such that Kl may be K and u the largest index such that Ku may be K//
l <-- 1; u <-- n
while l u do
m <-- [(l + u)/2] //compute index of middle record//
case
:K > Km: l <-- m + 1 //look in upper half//
:K = Km: i <-- m; return
:K < Km: u <-- m - 1 //look in lower half//
end
end
i <-- 0 //no record with key K//
end BINSRCH
This algorithm requires O(log2 n) key comparisons.
procedure INSERT(R,i)//Insert record R with key K into the ordered sequence R0, ...,Ri in such a way that the resulting sequence is also ordered on key K. Assume that R0 is a record (maybe a dummy) such that K
K0//
j <-- i
while K < Kj do
//move Rj one space up as R is to be inserted left of Rj//
Rj+1 <-- Rj; j <-- j - 1
end
Rj+1 <-- R
end INSERT
This algorithm requires O(n
) key comparisons.
procedure QSORT(m,n)//Sort records Rm, ...,Rn into nondecreasing order on key K. Key Km is arbitrarily chosen as the control key. Pointers i and j are used to partition the subfile so that at any time Kl
K, l < i and Kl K, l > j. It is assumed that Km Kn+1//
if m < n
then [i <-- m; j <-- n + 1; K <-- Km
loop
repeat i <-- i + 1 until Ki K;
repeat j <-- j - 1 until Kj K;
if i < j
then call INTERCHANGE(R(i),R(j))1
else exit
forever
call INTERCHANGE(R(m),R(j))
call QSORT(m,j - 1)
call QSORT(j + 1,n)]
end QSORT
This algorithm requires O(nlog2 n) key comparisons.1INTERCHANGE(x,y) performs t <-- x; x <-- y; y <-- t.
|