osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Algorithm of ordering in Python using recursion


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