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

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

- Prev by Date:
**tictactoe script - commented - may have pedagogical value** - Next by Date:
**[Tutor] beginning to code** - Previous by thread:
**Creating a python client for an external service advice** - Next by thread:
**A good way to unpack a matrix** - Index(es):