Skip to content

Sorting

Hint

The standard algorithms for sorting containers are std::sort and std::stable_sort.

These snippets include extra functions describing how these tasks can be implemented with many other classic sorting algorithms. They are mostly relevant for people studying sorting algorithms for the first time.

1
std::vector<int> v = {5, 4, 9, 8, 6, 3};

1
2
3
4
5
// - std::sort is what you would use daily
// - don't implement your own version unless you're studying the algorithms
std::sort(v.begin(), v.end());
std::copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

1
2
3
4
// Elements that compare equal don't change their relative positions
std::stable_sort(v.begin(), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

1
2
3
4
// Elements that compare equal don't change their relative positions
std::stable_sort(v.begin(), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
template <class It, class C> void selection_sort(It first, It last, C comp) {
    // For each position
    for (auto it = first; it != std::prev(last); ++it) {
        // Swap the current with the min_element
        std::iter_swap(it, std::min_element(it, last, comp));
    }
}

template <class It> void selection_sort(It first, It last) {
    // If no comparison function is provided, use `std::less`
    selection_sort(first, last, std::less<std::decay_t<decltype(*first)>>());
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
template <class It, class C> void insertion_sort(It first, It last, C comp) {
    // For each position
    for (auto i = std::next(first); i != last; ++i) {
        // Push the element to the sorted subarray to the left
        rotate(upper_bound(first, i, *i, comp), i, i + 1);
    }
}

template <class It> void insertion_sort(It first, It last) {
    // If no comparison function is provided, use `std::less`
    insertion_sort(first, last, std::less<std::decay_t<decltype(*first)>>());
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
template <class It, class C> void merge_sort(It first, It last, C comp) {
    // While more than 1 element
    if (last - first > 1) {
        It middle = first + (last - first) / 2;
        // Sort left-hand side
        merge_sort(first, middle, comp);
        // Sort right-hand side
        merge_sort(middle, last, comp);
        // Merge left and right-hand sides
        inplace_merge(first, middle, last, comp);
    }
}

template <class It> void merge_sort(It first, It last) {
    // If no comparison function is provided, use `std::less`
    merge_sort(first, last, std::less<std::decay_t<decltype(*first)>>());
}

1
2
3
4
5
6
7
8
9
template <typename T, class C> constexpr T median(T t1, T t2, T t3, C comp) {
    return (comp(t1, t2)) ? ((comp(t2, t3)) ? t2 : ((comp(t1, t3)) ? t3 : t1))
                          : ((comp(t1, t3)) ? t1 : ((comp(t2, t3)) ? t3 : t2));
}

template <class It> void median(It first, It last) {
    // If no comparison function is provided, use `std::less`
    median(first, last, std::less<std::decay_t<decltype(*first)>>());
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class It, class C> void quick_sort(It first, It last, C comp) {
    // If there is more than 1 element to sort
    if (first != last && std::next(first) != last) {
        It middle = first + (last - first) / 2;
        // Choose a pivot based on the median element
        auto pivot = median(*first, *middle, *std::prev(last), comp);
        // Partition the vector based on the pivot
        It split1 =
            partition(first, last, [&](auto x) { return comp(x, pivot); });
        It split2 =
            partition(split1, last, [&](auto x) { return !comp(pivot, x); });
        // Sort left-hand side
        quick_sort(first, split1, comp);
        // Sort right-hand side
        quick_sort(split2, last, comp);
    }
}

template <class It> void quick_sort(It first, It last) {
    // If no comparison function is provided, use `std::less`
    quick_sort(first, last, std::less<std::decay_t<decltype(*first)>>());
}

1
2
3
selection_sort(v.begin(), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

1
2
3
insertion_sort(v.begin(), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

1
2
3
merge_sort(v.begin(), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

1
2
3
quick_sort(v.begin(), v.end());
copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
std::cout << '\n';

Share Snippets