Efficient Text Formatting: A Comparative Analysis of Algorithmic Approaches

Efficient text formatting, especially when printing with mono spaced fonts, is a very important factor. In an attempt to address the problem of printing clean paragraphs, this work has been presented in the form of implementing and trying to demonstrate the efficiency of a large variety of algorithms. The algorithms include Binary Search, Shortest Path, Greedy Approach, Branch and Bound, Divide and Conquer, and Brute Force. This problem tries to format a set of texts into lines of fixed given width, where at a time it looks appropriate and readable, trying to minimize the number of vacant places and blank spaces. Hence, this dissertation dwells on a text formatting technique that possesses the least number of vacant places and blank spaces yet manages to look nice. In general, a comparison of the methods in the number of vacant places on a line raised to the cube, as a cost metric and the runtime complexity. Performance testing on a very broad spectrum of test scenarios is also there, which is low word count, random content, fixed character length, and fixed word count. The implementation of this problem will help us understand what method is effective and where so that it can be used in a real-world scenario. Text formatting jobs in domains like publishing, academia, and web development are crucial processes for efficient communication. Among these, the Dynamic Programming and Divide and Conquer algorithms achieved the highest performance, with a minimal total cost of 2529 and optimal line breaks in fixed character-length paragraphs. The results demonstrate that these algorithms strike an ideal balance between runtime efficiency and formatting quality, making them well-suited for real-world applications.