📦 A collection of sorting algorithms written in C.
- Bogo sort
- Bubble sort
- Bucket sort
- Cocktail sort
- Comb sort
- Counting sort
- Gnome sort
- Heap sort
- Insertion sort
- Merge sort
- Odd-even sort
- Pancake sort
- Quick sort
- Radix sort
- Shell sort
- Tree sort
- Sorting is a simple and well-defined problem, which makes it perfect for studying.
- Sorting algorithms cover important concepts like divide-and-conquer, data structures, and randomized algorithms.
- Sorting is a common computer task. At one point a quarter of all mainframe cycles were spent sorting.
Many languages are based on C, so the syntax will be familiar to most developers.
The sorting functions have the following prototype:
void sort(int arr[], int n)
arr
is the array to be sorted.
n
is the number of elements in arr
.
The function name will be the same as the filename, e.g. merge_sort
for merge_sort.h.
Algorithm analysis determines the efficiency of different algorithms.
One approach to determine the running time of an algorithm is to count the number of steps an algorithm takes to complete. Most commonly, simple operations (+
, \
, *
, -
, =
, if
) are understood to take one step to complete. Loops and subroutines are made up of the number of steps that they perform.
Consider an algorithm that performs 2 steps for each element in its input array (of length n). In total, it performs 2n steps. This can be expressed as a function that defines the time complexity of the algorithm as a function of its input: T(n)=2n.
Many algorithms perform a different number of steps depending on the state of the input. For example, some sorting algorithms complete almost immediately if the array is already sorted.
- The best-case complexity is the minimum number of steps taken to complete.
- The worst-case complexity is the maximum number of steps taken to complete.
- The average-case complexity is the average number of steps taken to complete.
Worst-case complexity is most often used in algorithm analysis. This because the worst-case is both likely to occur (best-case is usually not) and easy to calculate (average-case is usually not).
Big O notation is a way to classify algorithms according to the their growth rate.
Time complexity functions often contain a lot of detail, for example: f(n)=1234n² + 1228n + 92lg₂n + 8736. This level of detail is not much more informative than stating that "the time grows quadratically with n". Big O notation hides the extra detail from functions.
A non-rigorous explanation is that big O notation allows you to ignore constant factors and low-order terms. For example, the functions f(n)=4n+3 and f(n)=12n+9 can both be expressed as O(n) in big O.
Note: for a complete understanding, read the formal definition of big O on Wikipedia.
Big O notation creates classes of algorithms. The following table describes the most common classes:
Big-O | Name | Description |
---|---|---|
O(1) | constant | This is the best. The algorithm always takes the same amount of time, regardless of how much data there is. Example: looking up an element of an array by its index. |
O(log n) | logarithmic | Pretty great. These kinds of algorithms halve the amount of data with each iteration. If you have 100 items, it takes about 7 steps to find the answer. With 1,000 items, it takes 10 steps. And 1,000,000 items only take 20 steps. This is super fast even for large amounts of data. Example: binary search. |
O(n) | linear | Good performance. If you have 100 items, this does 100 units of work. Doubling the number of items makes the algorithm take exactly twice as long (200 units of work). Example: sequential search. |
O(n log n) | "linearithmic" | Decent performance. This is slightly worse than linear but not too bad. Example: the fastest general-purpose sorting algorithms. |
O(n^2) | quadratic | Kinda slow. If you have 100 items, this does 100^2 = 10,000 units of work. Doubling the number of items makes it four times slower (because 2 squared equals 4). Example: algorithms using nested loops, such as insertion sort. |
O(n^3) | cubic | Poor performance. If you have 100 items, this does 100^3 = 1,000,000 units of work. Doubling the input size makes it eight times slower. Example: matrix multiplication. |
O(2^n) | exponential | Very poor performance. You want to avoid these kinds of algorithms, but sometimes you have no choice. Adding just one bit to the input doubles the running time. Example: traveling salesperson problem. |
O(n!) | factorial | Intolerably slow. It literally takes a million years to do anything. |