sort.h File Reference

#include <qx/typedefs.h>
#include <qx/meta/type_traits.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <qx/algo/sort.inl>

Go to the source code of this file.

Functions
template<class random_it_t >
bool	qx::sort_required (random_it_t begin, random_it_t end)
	Check if sort really needed. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_insertion (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Insertion sort. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_insertion (container_t &cont, compare_t compare=compare_t())
	Insertion sort. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_selection (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Selection sort. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_selection (container_t &cont, compare_t compare=compare_t())
	Selection sort. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_bubble (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Bubble sort. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_bubble (container_t &cont, compare_t compare=compare_t())
	Bubble sort. More...
template<class random_it_t , class compare_t >
void	qx::adjust_heap (random_it_t begin, size_t nHeapSize, size_t nPosition, compare_t compare=compare_t())
	Adjust heap. More...
template<class random_it_t , class compare_t >
void	qx::make_heap (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Make heap at range. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_heap (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Heap sort. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_heap (container_t &cont, compare_t compare=compare_t())
	Heap sort. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_quick_hoare (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Quick sort based on Hoare partitioning. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_quick_hoare (container_t &cont, compare_t compare=compare_t())
	Quick sort based on Hoare partitioning. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_quick_three_way (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Quick sort based on three-way partitioning. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_quick_three_way (container_t &cont, compare_t compare=compare_t())
	Quick sort based on three-way partitioning. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_quick_dual_pivot (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Quick sort based on dual-pivot partitioning. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_quick_dual_pivot (container_t &cont, compare_t compare=compare_t())
	Quick sort based on dual-pivot partitioning. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::merge (random_it_t begin, random_it_t end, compare_t compare=compare_t(), vector_of_values< random_it_t > *pPreallocatedBuffer=nullptr)
	Merge with temp vector. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort_merge (random_it_t begin, random_it_t end, compare_t compare=compare_t(), vector_of_values< random_it_t > *pPreallocatedBuffer=nullptr)
	Merge sort based on merge with temp vector. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort_merge (container_t &cont, compare_t compare=compare_t(), vector_of_values< typename container_t::iterator > *pPreallocatedBuffer=nullptr)
	Merge sort based on merge with temp vector. More...
template<class random_it_t , class compare_t = std::less<>>
bool	qx::sort_counting (random_it_t begin, random_it_t end, compare_t compare=compare_t(), size_t nMaxBufferSize=SORT_COUNTING_MAX_BUFFER_SIZE)
	Counting sort for integral values. More...
template<class container_t , class compare_t = std::less<>>
bool	qx::sort_counting (container_t &cont, compare_t compare=compare_t(), size_t nMaxBufferSize=SORT_COUNTING_MAX_BUFFER_SIZE)
	Counting sort for integral values. More...
template<class random_it_t , class compare_t = std::less<>>
void	qx::sort (random_it_t begin, random_it_t end, compare_t compare=compare_t())
	Sort by the most suitable algorithm. More...
template<class container_t , class compare_t = std::less<>>
void	qx::sort (container_t &cont, compare_t compare=compare_t())
	Sort by the most suitable algorithm. More...

Variables
constexpr size_t	qx::SORT_COUNTING_MAX_BUFFER_SIZE = 100000
	vector of iterator value

Detailed Description

Author

Khrapov

Date

1.03.2020

Copyright

© Nick Khrapov, 2021. All right reserved.

Definition in file sort.h.

Function Documentation

adjust_heap()

template<class random_it_t , class compare_t >

void qx::adjust_heap ( random_it_t  begin, size_t  nHeapSize, size_t  nPosition, compare_t  compare = compare_t()  )

inline

Adjust heap.

Complexity:

O(log(N))

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- whole heap root random_it_type
nHeapSize	- whole heap size for out of range check
nPosition	- current root nPosition
compare	- comparison function

Definition at line 90 of file sort.inl.

make_heap()

template<class random_it_t , class compare_t >

void qx::make_heap ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Make heap at range.

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 121 of file sort.inl.

merge()

template<class random_it_t , class compare_t = std::less<>>

void qx::merge ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t(), vector_of_values< random_it_t > *  pPreallocatedBuffer = nullptr  )

inline

Merge with temp vector.

Complexity:

O(N), O(N) memory

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function
pPreallocatedBuffer	- preallocated buffer. default value will allocate a new one

Definition at line 386 of file sort.inl.

sort() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Sort by the most suitable algorithm.

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 541 of file sort.inl.

sort() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Sort by the most suitable algorithm.

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 522 of file sort.inl.

sort_bubble() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_bubble ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Bubble sort.

Stable

Complexity:

O(N^2)

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 84 of file sort.inl.

sort_bubble() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_bubble ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Bubble sort.

Stable

Complexity:

O(N^2)

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 63 of file sort.inl.

sort_counting() [1/2]

template<class container_t , class compare_t = std::less<>>

bool qx::sort_counting ( container_t &  cont, compare_t  compare = compare_t(), size_t  nMaxBufferSize = SORT_COUNTING_MAX_BUFFER_SIZE  )

inline

Counting sort for integral values.

Complexity:

O(M + 2 * N), O(M) memory, where M = max - min + 1

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function
nMaxBufferSize	- max buffer size. if required size is bigger than this value, sorting will fail

Return values

-	true if sorted, false if required buffer size is greather then max

Definition at line 516 of file sort.inl.

sort_counting() [2/2]

template<class random_it_t , class compare_t = std::less<>>

bool qx::sort_counting ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t(), size_t  nMaxBufferSize = SORT_COUNTING_MAX_BUFFER_SIZE  )

inline

Counting sort for integral values.

Complexity:

O(M + 2 * N), O(M) memory, where M = max - min + 1

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function
nMaxBufferSize	- max buffer size. if required size is bigger than this value, sorting will fail

Return values

-	true if sorted, false if required buffer size is greather then max

Definition at line 477 of file sort.inl.

sort_heap() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_heap ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Heap sort.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 152 of file sort.inl.

sort_heap() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_heap ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Heap sort.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 135 of file sort.inl.

sort_insertion() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_insertion ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Insertion sort.

Stable

Complexity:

O(N^2)

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 34 of file sort.inl.

sort_insertion() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_insertion ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Insertion sort.

Stable

Complexity:

O(N^2)

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 23 of file sort.inl.

sort_merge() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_merge ( container_t &  cont, compare_t  compare = compare_t(), vector_of_values< typename container_t::iterator > *  pPreallocatedBuffer = nullptr  )

inline

Merge sort based on merge with temp vector.

Stable

Complexity:

O(Nlog(N)), O(N) memory

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function
pPreallocatedBuffer	- preallocated buffer. default value will allocate a new one

Definition at line 468 of file sort.inl.

sort_merge() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_merge ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t(), vector_of_values< random_it_t > *  pPreallocatedBuffer = nullptr  )

inline

Merge sort based on merge with temp vector.

Stable

Complexity:

O(Nlog(N)), O(N) memory

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
pPreallocatedBuffer	- preallocated buffer. default value will allocate a new one
compare	- comparison function

Definition at line 441 of file sort.inl.

sort_quick_dual_pivot() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_quick_dual_pivot ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Quick sort based on dual-pivot partitioning.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 380 of file sort.inl.

sort_quick_dual_pivot() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_quick_dual_pivot ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Quick sort based on dual-pivot partitioning.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 278 of file sort.inl.

sort_quick_hoare() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_quick_hoare ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Quick sort based on Hoare partitioning.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 188 of file sort.inl.

sort_quick_hoare() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_quick_hoare ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Quick sort based on Hoare partitioning.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 158 of file sort.inl.

sort_quick_three_way() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_quick_three_way ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Quick sort based on three-way partitioning.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 272 of file sort.inl.

sort_quick_three_way() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_quick_three_way ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Quick sort based on three-way partitioning.

Unstable

Complexity:

O(Nlog(N))

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 194 of file sort.inl.

sort_required()

template<class random_it_t >

bool qx::sort_required ( random_it_t  begin, random_it_t  end  )

inline

Check if sort really needed.

Complexity:

O(1)

Template Parameters

random_it_t

- random access iterator

Parameters

begin	- begin iterator
end	- end iterator

Return values

-	false if [begin, end) already sorted

Definition at line 14 of file sort.inl.

sort_selection() [1/2]

template<class container_t , class compare_t = std::less<>>

void qx::sort_selection ( container_t &  cont, compare_t  compare = compare_t()  )

inline

Selection sort.

Unstable

Complexity:

O(N^2)

Template Parameters

container_t	- container type
compare_t	- function object type satisfying binary predicate requirements

Parameters

cont	- container ref
compare	- comparison function

Definition at line 57 of file sort.inl.

sort_selection() [2/2]

template<class random_it_t , class compare_t = std::less<>>

void qx::sort_selection ( random_it_t  begin, random_it_t  end, compare_t  compare = compare_t()  )

inline

Selection sort.

Unstable

Complexity:

O(N^2)

Template Parameters

random_it_t	- random access iterator
compare_t	- function object type satisfying binary predicate requirements

Parameters

begin	- begin iterator
end	- end iterator
compare	- comparison function

Definition at line 40 of file sort.inl.