A quadratic time 2-approximation algorithm for block sorting

The block sorting problem is the problem of minimizing the number of steps to sort a list of distinct items, where a sublist of items which are already in sorted order, called a block, can be moved in one step. We give an approximation algorithm for the block sorting problem with an approximation ratio of 2 and run time O ( n 2 ). The approximation algorithm is based on the related concept of block deletion. We show that finding an optimum block deletion sequence can be done in O ( n 2 ) time, even though block sorting is known to be N P -hard. Block sorting has importance in connection with optical character recognition (OCR) and is related to transposition sorting in computational biology.

Authors

• Wolfgang W. Bein
• Lawrence L. Larmore
• Linda Morales
• I. Hal Sudborough

Keywords

• Design and analysis of algorithms
• Approximation algorithms
• Block sorting
• Transposition sorting
• Optical character recognition