Can anyone help me find the error of this implementation in Python what am I
doing with this TBiS algorithm?
Algorithm:
Function b = TBiSort(a, n, k, dir)
if n == 1 then
b = a;
else
h1 = TBiSort(a(1:n/2), n/2, k, dir);
h2 = TBiSort(a(n/2+1:n),n/2,k, -dir);
b = TBiMerge( [h1,h2], n, k, dir)
Function b = TBiMerge(hh, n, k, dir)
[hmin, hmax] = minmax(hh(1:n/2),hh(1+n/2:n));
bmin= TBiMerge(hmin, n2, k, dir);
if n == 2k then
b = bmin;
else
bmax = TBiMerge(hmax, n/2, k, dir);
if dir == 'up'
then
b = [bmin,bmax];
else
b = [bmax,bmin];
For conceptual clarity we present the algorithm in recursion fashion. Wecomment
on the truncation. The TBiSort recursion goes downward first portioning the
initial data list a all the way to the base level (sublist length 1), then goes
upward with monotonic merges. In TBiMerge, the min max function renders the
minimal and maximal between each element pair on the two input lists. The
truncation begins at, and continues from, the point where the monotonic
sublists reach in size to k. At each merge step, bmax, the upper part of the
merged list is purged, and the total data is reduce d by half. By TBiMerge, the
merged sublists never exceed k in size.
Implementation:
def TBiSort(a, n, k, direction):
if n == 1:
b = a
else:
h1 = TBiSort(a[0:n/2], n/2, k, direction)
h2 = TBiSort(a[n/2:n], n/2, k, -direction)
print h1
print h2
b = TBiMerge(h1 + h2, n, k, direction)
return b
def TBiMerge(hh, n, k, direction):
p1 = [ min(hh[0:n/2]), max(hh[0:n/2]) ]
print p1
p2 = [ min(hh[n/2:n+1]), max(hh[n/2:n+1]) ]
print p2
bmin = TBiMerge(p1, n/2, k, direction)
if n == 2 * k:
b = bmin
else:
bmax = TBiMerge(p2, n/2, k, direction)
if direction == 1:
b = bmin + bmax
else:
b = bmax + bmin
return b
a = [3,7,4,8,6,2,1,5]
k = 4
direction = 1
teste = TBiSort(a, len(a), k, direction)
print teste
--
https://mail.python.org/mailman/listinfo/python-list
