Cpp-Sorting-Algorithms

English | 繁體中文

This project aims to implement various sorting algorithms in a simple and easy-to-understand way.
The goal is to make this repository a useful resource for learning, implementation, and reference.

Project Structure

Cpp-Sorting-Algorithms/
│
├── include/CppSortingAlgos/
├── tests/
├── benchmarks/
├── docs/
├── CMakeLists.txt
└── README.md

Implemented Sorting

There are many sorting algorithms in the world, and not all are included here.
Currently implemented algorithms are listed below:

Comparison-based Sorting

Bubble Sort	Cocktail Sort	Gnome Sort	Insertion Sort	Binary Insertion Sort
Selection Sort	Shell Sort	Heap Sort	Quick Sort	Merge Sort
Intro Sort	Tim Sort	Slow Sort	Stooge Sort	Comb Sort
Cycle Sort	Bitonic Sort	Tournament Sort	Odd-Even Sort	Pancake Sort
Strand Sort	Patience Sort	Adaptive Merge Sort	Smooth Sort	Power Sort

Non-comparison Sorting

Bucket Sort

Counting Sort

Radix Sort

Flash Sort

Usage

All source code is located in the include/CppSortingAlgos/ folder.
Each sorting algorithm class provides the following interface:

// Compare must satisfy strict weak ordering
template <typename T, typename Compare = std::less<T>>
static void sort(std::span<T> arr_span, Compare cmp = Compare{});
inline static const bool is_stable;     // → whether it is stable
inline static const bool is_comparison; // → whether it is comparison-based
inline static const bool in_place;      // → whether it is in-place

Example

#include "include/CppSortingAlgos/bubble_sort.hpp"
#include <functional>

int main()
{
    size_t n = 5;
    int arr[] = {1, 7, 3, 2, 6};

    // "sort_algo"  is the namespace.
    // "BubbleSort" is the class.
    // "sort"       is the method.

    sort_algo::BubbleSort::sort(std::span<int>{arr, n}, std::less<int>());      // ascending
    sort_algo::BubbleSort::sort(std::span<int>{arr, n}, std::greater<int>());   // descending

    // For vector, you can use 
    // sort_algo::BubbleSort::sort<int>(vec, less<int>());
}

Full example: example.cpp

Notes

Some algorithms have specific constraints, for example:

• Counting Sort does not support floating-point types.
• Bitonic Sort requires the sequence size to be a power of $2$.

Some limitations come from the algorithm itself, while others come from implementation choices.
Please check docs/Sortings.md and the source code before using to avoid unexpected issues.

Installation

To use this library in your own CMake project, you can add it with CMake's FetchContent module.
Add the following to your CMakeLists.txt:

include(FetchContent)

FetchContent_Declare(
    CppSortingAlgos
    GIT_REPOSITORY https://github.com/MingMinNa/Cpp-Sorting-Algorithms.git
    GIT_TAG v2.0.0
)

FetchContent_MakeAvailable(CppSortingAlgos)

add_executable(<target_name>
    <source_file>.cpp
    ...
)

target_link_libraries(<target_name>
    PRIVATE
        CppSortingAlgos::sort_algo
)

You can then include the library headers in your source file as follows:

#include <CppSortingAlgos/bubble_sort.hpp>
#include <CppSortingAlgos/insertion_sort.hpp>
#include <CppSortingAlgos/merge_sort.hpp>
...

If you want to modify the code, download the source and copy include/CppSortingAlgos folder into your project.