### Abstract

We study the grouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence of n numbers drawn from {0,1, 2,..., m-1} with repetitions allowed; we are to rearrange them, using as few swaps of adjacent elements as possible, into an order such that all the like numbers are grouped together. It is known that this problem is NP-hard. We present a probabilistic analysis of a grouping algorithm called MEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior of MEDIAN is within 10% of optimal and is asymptotically optimal as n/m→∞ or as n/m→0.

Original language | English (US) |
---|---|

Pages (from-to) | 192-206 |

Number of pages | 15 |

Journal | Algorithmica |

Volume | 6 |

Issue number | 1-6 |

DOIs | |

State | Published - Jun 1 1991 |

Externally published | Yes |

### Keywords

- Exponential of a matrix
- Grouping by swapping
- Memory compaction
- Probabilistic analysis of algorithms

### ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Probabilistic analysis of a grouping algorithm'. Together they form a unique fingerprint.

## Cite this

*Algorithmica*,

*6*(1-6), 192-206. https://doi.org/10.1007/BF01759041