# A Nonoblivious Bus Access Scheme Yields an Optimal Partial Sorting Algorithm

The full text article is not available for purchase.

### Abstract:

This paper focuses on a linear array of n nodes with multiple shared buses as a practically feasible model for parallel processing. Let k be the number of shared buses. A nonoblivious scheme for mutually exclusive access to k shared buses is proposed. The effectiveness of the scheme is demonstrated by proposing an algorithm for solving a partial sort problem, which can be efficiently executed on the array according to the scheme. The partial sort problem with parameter m is the problem of sorting a subset S \' of a given set S , where S \' is the set of elements less than or equal to the m th smallest element in S . If m = 1, then it is solved by an algorithm for finding the smallest element in S , and if m = n , then it is solved by adapting normal sorting algorithm. The time complexity (9 m / k ) log 2 log 2 n + 3.467 $$\sqrt{n/k}\$$ + O ( m / k + ( n / k ) 1/4 ) of the proposed algorithm matches a lower bound Omega ( $$\sqrt{n/k}\$$ + m / k ) with respect to n and k , if m is small enough to satisfy m = O ( $$\sqrt{nk}\$$ /log log n ).

Document Type: Research Article

Affiliations: Faculty of Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashi-Hiroshima, 739, Japan

Publication date: April 1, 1996

Related content

#### Tools

• Export options +-
Favourites

#### Access Key

Free content
New content
Open access content
Subscribed content
Free trial content
X