Generalization of Sorting in Single Hop Wireless Networks

Shyue-Horng SHIAU; Chang-Biau YANG

doi:10.1093/ietisy/e89-d.4.1432

Generalization of Sorting in Single Hop Wireless Networks

Shyue-Horng SHIAU, Chang-Biau YANG

Full Text Views

0

Share
Cite this

Summary :

The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.4 pp.1432-1439

Publication Date: 2006/04/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.4.1432

Type of Manuscript: PAPER

Category: Computation and Computational Models

Cite this

Copy

Shyue-Horng SHIAU, Chang-Biau YANG, "Generalization of Sorting in Single Hop Wireless Networks" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 4, pp. 1432-1439, April 2006, doi: 10.1093/ietisy/e89-d.4.1432.
Abstract: The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.4.1432/_p

Copy

@ARTICLE{e89-d_4_1432,
author={Shyue-Horng SHIAU, Chang-Biau YANG, },
journal={IEICE TRANSACTIONS on Information},
title={Generalization of Sorting in Single Hop Wireless Networks},
year={2006},
volume={E89-D},
number={4},
pages={1432-1439},
abstract={The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.},
keywords={},
doi={10.1093/ietisy/e89-d.4.1432},
ISSN={1745-1361},
month={April},}

Copy

TY - JOUR
TI - Generalization of Sorting in Single Hop Wireless Networks
T2 - IEICE TRANSACTIONS on Information
SP - 1432
EP - 1439
AU - Shyue-Horng SHIAU
AU - Chang-Biau YANG
PY - 2006
DO - 10.1093/ietisy/e89-d.4.1432
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2006
AB - The generalized sorting problem is to find the first k largest elements among n input elements and to report them in a sorted order. In this paper, we propose a fast generalized sorting algorithm under the single hop wireless networks model with collision detection (WNCD). The algorithm is based on the maximum finding algorithm and the sorting algorithm. The key point of our algorithm is to use successful broadcasts to build broadcasting layers logically and then to distribute the data elements into those logic layers properly. Thus, the number of broadcast conflicts is reduced. We prove that the average time complexity required for our generalized sorting algorithm is Θ(k + log(n - k)). When k = 1, our generalized sorting algorithm does the work of finding maximum, and when k = n, it does the work of sorting. Thus, the analysis of our algorithm builds a connection between the two extremely special cases which are maximum finding and sorting.
ER -