Sorting

#include <iostream>
#include <ranges>
#include <vector>
#include <list>
#include <algorithm>
#include <random>
#include <iterator>

int main() {

    const auto printy = [](const auto& v) {
        std::cout << "n";
        std::ranges::copy(v, std::ostream_iterator<int>(std::cout, ",n"));
    };

    // Make container of random values
    std::vector<int> v(4);
    std::ranges::for_each(v, [](auto &x){ x = std::rand(); });
    printy(v);

    // Sort it
    std::ranges::sort(v);
    printy(v);

    // Sort it the other way
    std::ranges::sort(v, std::greater<int>());
    printy(v);

    // List has its own sort
    std::list<int> l{std::cbegin(v), std::cend(v)};
    l.sort();
    printy(l);
}

https://godbolt.org/z/srjrvoxT6

Quicksort usually has a running time of nlogn, but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat (worst-case) nlogn running time, since nlogn represents the minimum number of comparisons needed to know where to place each element. http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

std::sort uses Introsort:

Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort.

Introsort is in place and not stable. https://en.wikipedia.org/wiki/Introsort

If additional memory is available, stable_sort remains O(n ∗ logn). However, if it fails to allocate, it will degrade to an O(n ∗ logn ∗ logn) algorithm. https://leanpub.com/cpp-algorithms-guide

std::list

std::sort requires random access to the elements, so std::list has its own sort method, but it still (approximately) conforms to O(n log n). It can be implemented with merge sort as moving elements is cheap with a linked list.

Other sorting algorithms

All of these are Θ(n log n) in all cases apart from Timsort has a Ω(n) and Quicksort has a terrible O(n^2) (if we happen to always pick the worst pivot). Quicksort is a good all rounder with O(n log n) average case. But it does have a O(n^2) worst case. It is said that this can be avoided by picking the pivot carefully but an example could be constructed where the chosen pivot is always the worst case.

  • Mergesort breaks the problem into smallest units then combine adjacent.
  • Timsort finds runs of already sorted elements and then use mergesort. O(n) if already sorted.
  • Heapsort can be thought of as an improved selection sort.
  • Radix sort is a completely different solution to the problem.
  • A sorted array is already a heap.

Considerations

  • Size of input
  • Type of input (partially sorted, random)

Quicksort small array threshold

  • VS 32
  • GNU 16
  • clang is 30 for trivially constructible objects, otherwise 6
  • Integrate conditionals to avoid branches: + (vec.size() & 1)

results matching ""

    No results matching ""