Implementing Common Algorithms
Python implementations and study notes for common sorting, searching, linked-list, string, and combinatorial algorithms.
This article collects straightforward implementations of common algorithms for study and comparison.
Sorting
Bubble sort repeatedly swaps adjacent out-of-order values. Insertion sort grows a sorted prefix and inserts each new value into it. Heap sort builds a heap and repeatedly moves its root to the end. Quicksort partitions values around a pivot and recursively sorts both partitions. Linear-time sorts such as counting sort are possible when keys satisfy additional constraints.
Searching
A single scan can find both the minimum and maximum; pairing comparisons reduces the total number of comparisons. Binary search runs in logarithmic time on sorted input, but boundary handling must remain consistent about whether the upper bound is inclusive.
Linked lists and strings
Reverse a singly linked list by tracking the previous, current, and next nodes while walking once through the list. Dynamic programming can compute the longest common substring, longest common subsequence, and maximum subarray; each problem uses a different recurrence despite the similar names.
Permutations and combinations
Combination generation chooses whether to include each candidate while tracking how many values remain. Permutation generation chooses each unused value for the next position and backtracks afterward. Explicitly define how duplicates should be treated before selecting an implementation.