It is well known that a non-Manhattan channel router always uses fewer rout
ing tracks than a Manhattan router in a channel, To our knowledge, for a bu
bble-sorting-based non-Manhattan channel routing (BSNMCR) problem, Chaudhar
y's O(kn(2)) heuristic algorithm [8] and Chen's O(k(2)n) optimal algorithm
[9] have been, respectively, proposed, where n is the number of terminals a
nd k is the number of routing tracks in a channel. However, the time comple
xity of the two algorithms is in O(n(3)) time in the worst case. In this pa
per, based on optimality-oriented swap-direction selection in an optimal bu
bble-sorting solution, an improved optimal algorithm for a BSNMCR problem i
s proposed, and the time complexity of the proposed algorithm is proven to
be in O(kn) time and in O(n(2)) time in the worst case.