Premium
Pattern analysis as a tool for inventing algorithms
Author(s) -
Hart Richard
Publication year - 1980
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380100508
Subject(s) - merge (version control) , algorithm , computer science , merge algorithm , merge sort , binary number , sort , sorting algorithm , parallel computing , mathematics , arithmetic , information retrieval , sorting
A method for inventing algorithms and several examples are presented. The Julian conversion is useful for all date calculations and for switching to daylight saving time. The algorithm rotates the calendar by 2 months and performs a few straightforward calculations on the new month‐day‐year to produce the Julian date (and back again). The butterfly sort is based on the work on Woodrum. The algorithm repeatedly delivers two linked lists to a merge machine that produces a single linked list for further use. The length of the two lists going into the merge machine never differs by more than one. This accounts for the theoretical minimal number of comparisons 5 . The algorithm uses patterns within a simple binary counter to schedule the delivery of these lists. This accounts for the minimal number of steps between each comparison 3 .