tag

#correctness

6 pages tagged

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.24 Common Bugs

6.24 Common Bugs Sorting bugs usually come from boundary errors, invalid invariants, or misunderstood comparison rules. Many implementations work on ordinary random inputs but fail on empty arrays, duplicate-heavy arrays, reverse sorted arrays, or arrays with custom records. Problem You have a sorting implementation that appears correct on common inputs. You want to identify the failure patterns that most often break sorting algorithms. Off-by-One Errors Sorting code frequently works with...
algorithms sorting bugs correctness May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.23 Testing Sort Correctness

6.23 Testing Sort Correctness Sorting implementations are easy to get almost right and hard to get completely correct. Subtle bugs often appear only on edge cases, duplicate-heavy inputs, or adversarial patterns. A disciplined testing strategy verifies both the ordering and permutation properties under a wide range of inputs. Problem You have implemented a sorting algorithm. You want to verify that it is correct, stable when required, and robust across inputs....
algorithms sorting testing correctness May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.17 Custom Comparators

6.17 Custom Comparators Sorting depends on a comparison relation. A custom comparator defines that relation for user-defined types and nontrivial ordering rules. The correctness of a sort relies on the comparator being consistent. When the comparator is inconsistent, the algorithm may produce incorrect output or fail to terminate. Problem You have elements that are not naturally ordered, or you need an order different from the default. You want to sort...
algorithms sorting comparators correctness May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.1 Sorting Contracts

6.1 Sorting Contracts Sorting begins with a contract. An algorithm is correct only if it satisfies two conditions: the output is ordered, and the output is a permutation of the input. Every implementation detail, optimization, and variation must preserve these two properties. Problem You are given a sequence A and a comparison relation ≤ . You need a procedure that returns a sequence B such that B is ordered under...
algorithms sorting correctness May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.20 Testing Hash Logic

5.20 Testing Hash Logic Problem You need confidence that a hash-based structure is correct, stable, and performs well under realistic inputs. Hash table bugs are often subtle. A map may pass small examples but fail after resizing. A set may work until keys collide. A deterministic hash may appear stable until another language, platform, or encoding rule is introduced. Solution Test both logical behavior and structural stress cases. Basic behavior:...
algorithms hashing testing correctness May 4, 2026
Programming › Algorithm Cookbook › Chapter 1. Foundations ›

1.4 Loop Invariants

Loop invariants are the primary tool for reasoning about iterative algorithms. They formalize what remains true at each step of a loop and provide a bridge between local updates and global correctness. A loop invariant is not an observation after the fact. It is a design component that guides how the loop is written. Problem You need a reliable method to prove that a loop-based algorithm is correct, especially when...
algorithms computer-science complexity foundations correctness May 3, 2026