Sorting Algorithm Comparison

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Sorting is the process of arranging data according to certain standards. In addition to ascending numerical order, you can use multiple criteria such as health, name, or creation time.

selection sort

Find the smallest value in the remaining section and replace it with the previous one.

for (int i = 0; i < Count - 1; ++i)
{
    int MinIndex = i;

    for (int j = i + 1; j < Count; ++j)
    {
        if (Values[j] < Values[MinIndex])
        {
            MinIndex = j;
        }
    }

    std::swap(Values[i], Values[MinIndex]);
}

Easy to implement, but the number of comparisons isO(N²)Therefore, it is not suitable for large data.

merge sort

Divide the array in half, sort each, and then merge them. Time complexity isO(N log N)It can be implemented as a stable sort, but merging requires temporary memory.

quick sort

Divide small and large values ​​based on the pivot and rearrange each section. The average isO(N log N)However, if the Pivot selection continues to be bad,O(N²)You can go down to

In actual C++ code, rather than recreating the alignment yourself,std::sortandstd::stable_sortUse first.

std::sort(Units.begin(), Units.end(),
    [](const Unit& A, const Unit& B)
    {
        return A.Speed > B.Speed;
    });

Implementing the algorithm directly by studying it and using a verified standard library in the product code have different purposes.