Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A published version of Bubblesort is analyzed via correctness arguments and the failure of these arguments leads to the discovery of a subtle bug. A simple change produces a correct version and a not-so-trivial proof of termination completes the total correctness demonstration for the revised algorithm. Several important lessons are extracted from this experience.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Algorithms, Design, Human Factors, Theory, Verification