Algorithm of ordering in Python using recursion
Leo
leonardoafonso at gmail.com
Wed Sep 13 21:49:25 EDT 2017
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
More information about the Python-list
mailing list