In this dissertation, we focus on the study of the partial sorting (generalized sorting) problem and the initialization problem. The partial sorting problem is
to find the first k smallest (or largest) elements among n input elements and to report them in nondecreasing (or nonincreasing). The initialization problem on a multiprocessor system is to assign each of n input elements a unique identification number, from 1 to n. This problem can be regarded as a special case of the sorting problem in which all input elements have the same value. We propose
some algorithms for solving these problems. The main result is to give precise analysis for these algorithms.
On the traditional model, we modify two algorithms, based on insertion sort and quicksort, to solve the partial sorting problem. Our analysis figures out the whole race between the two partial sorting algorithms and shows that the partial insertion sort algorithm obtains the leading position from k = 1 (the beginning) until k 3
5pn. After that, the partial quicksort algorithm will take the leading position on the way to the end.
We also extend the partial sorting problem on the Single-Hop wireless network with collision detection (WNCD) model. The extension fits in with the wireless trend and may be a foundation for studying divide-and-conquer. With the repeat
maximum finding scheme, we propose a partial sorting algorithm and prove that its average time complexity is (k + log (n − k)). For the initialization problem on the WNCD model, we can invoke the sorting algorithms directly for solving it. However, those sorting algorithms would not be better than the method of building a partition tree. We show that the partition tree method requires 2.88n time slots in average. After reconstructing and analyzing the method, we improve the result from 2.88n to 2.46n.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0119106-120724 |
| Date | 19 January 2006 |
| Creators | Shiau, Shyue-Horng |
| Contributors | Sing Ling Lee, D. J. Guan, Biing-Feng Wang, Shi-Jinn Horng, Rong-Jaye Chen, C. B. Yang, Y. L. Wang, Yaw-Ling Lin, Hsien-Kuei Hwang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0119106-120724 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0022 seconds