On the Complexity of Sorting in Magnetic Bubble Memory Systems
- 1 July 1980
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-29 (7) , 553-563
- https://doi.org/10.1109/TC.1980.1675626
Abstract
In this paper the problem of sorting in various models of magnetic bubble memory systems is studied. Three basic parameters are of interest, namely, the number of steps to sort, the number of switches required, and the number of control states necessary for the switches. Several sorting algorithms are proposed with respective running times essentially n2, n/2, 1/2 n log2 n, 7/2 n, n log2n, respective numbers of switches essentially, 1, n, 2√n, 2√nlog2n , 1og2n, and respective numbers of control states essentially, 3, 2, 1/8 log2n, 1/8 log2n, and 3 log2n.Keywords
This publication has 9 references indexed in Scilit:
- On the Complexity of Permuting Records in Magnetic Bubble Memory SystemsIBM Journal of Research and Development, 1980
- A bubble string comparator for information processingIEEE Transactions on Magnetics, 1979
- The Movement and Permutation of Columns in Magnetic Bubble Lattice FilesIEEE Transactions on Computers, 1979
- Permutation of data blocks in a bubble memoryCommunications of the ACM, 1979
- The Generation of Permutations in Magnetic Bubble MemoriesIEEE Transactions on Computers, 1976
- Storage Management Operations in Linked Uniform Shift-Register LoopsIBM Journal of Research and Development, 1976
- Bubble ladder for information processingIEEE Transactions on Magnetics, 1975
- Dynamic Data Reallocation in Bubble MemoriesBell System Technical Journal, 1973
- Magnetic Bubble Memory OrganizationIBM Journal of Research and Development, 1972