tpl_sort_utils.H File Reference

Comprehensive sorting algorithms and search utilities for Aleph-w. More...

#include <ahUtils.H>
#include <ahFunctional.H>
#include <ah-errors.H>
#include <tpl_arrayStack.H>
#include <tpl_array.H>
#include <tpl_dynArray.H>
#include <tpl_dynDlist.H>
#include <tpl_arrayHeap.H>
#include <htlist.H>
#include <vector>
#include <utility>

Include dependency graph for tpl_sort_utils.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Compare_Tnode< Tlink, Tnode, T, Compare >
struct	Aleph::Compare_Dnode< T, Compare >
class	Aleph::Negate_Compare< T, Compare >
	Comparator wrapper that inverts the comparison order. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<typename T , class Compare >
using	Aleph::Compare_Snodenc = Compare_Tnode< Slinknc, Snodenc, T, Compare >

Functions
template<template< typename > class Container, typename T , class Compare = Aleph::less<T>>
bool	Aleph::is_sorted (const Container< T > &cont, const Compare &cmp=Compare())
	Check if a container is sorted in ascending order.
template<template< typename > class Container, typename T , class Compare = Aleph::less<T>>
std::pair< bool, size_t >	Aleph::search_inversion (const Container< T > &cont, const Compare &cmp=Compare())
	Find the first inversion in a container.
template<template< typename > class Container, typename T , class Compare = Aleph::less<T>>
bool	Aleph::is_inversely_sorted (const Container< T > &cont, const Compare &cmp=Compare())
	Check if a container is sorted in descending order.
template<template< typename > class Container, typename T , class Compare = Aleph::less<T>>
std::pair< bool, size_t >	Aleph::test_sorted (const Container< T > &cont, const Compare &cmp=Compare())
	Test if a container is sorted, returning the inversion position.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::selection_sort (T *a, const size_t n, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_swappable_v< T >)
	Sort an array using the selection sort algorithm.
template<class Link , class Compare >
Link *	Aleph::search_extreme (const Link &list, const Compare &cmp)
	Find the extreme (minimum or maximum) element in a linked list.
template<class Compare >
Dlink *	Aleph::search_extreme (const Dlink &list, const Compare &cmp=Compare())
template<class Compare >
Slinknc *	Aleph::search_extreme (const Slinknc &list, const Compare &cmp=Compare())
template<class Compare >
void	Aleph::selection_sort (Dlink &list, Compare cmp)
	Sort a doubly linked list using selection sort.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::selection_sort (Dnode< T > &list, Compare cmp)
	Sorts a linked list of type Dnode<T> using the selection method.
template<typename T , class Equal = Aleph::equal_to<T>>
long	Aleph::sequential_search (T *a, const T &x, const long l, const long r, Equal eq=Equal())
	Linear search for an element in an array.
template<typename T , class Equal = Aleph::equal_to<T>>
long	Aleph::sequential_search (const DynArray< T > &a, const T &x, const long l, const long r, Equal eq=Equal())
	Sequential search on a dynamic array.
template<class Link , typename T , class Equal >
Link *	Aleph::sequential_search (const Link &list, const T &x, Equal &eq)
template<typename T , class Equal = Aleph::equal_to<T>>
Dlink *	Aleph::sequential_search (const Dlink &list, const T &x, Equal eq=Equal())
template<typename T , class Equal = Aleph::equal_to<T>>
Slinknc *	Aleph::sequential_search (const Slinknc &list, const T &x, Equal eq=Equal())
template<typename T , class Equal = Aleph::equal_to<T>>
Dnode< T > *	Aleph::sequential_search (const Dnode< T > &list, const T &x, Equal &eq)
	Sequential search over a list of nodes.
template<typename T , class Equal = Aleph::equal_to<T>>
Dnode< T > *	Aleph::sequential_search (const Dnode< T > &list, const T &x, Equal &&eq=Equal())
template<typename T , class Equal = Aleph::equal_to<T>>
T *	Aleph::sequential_search (const DynDlist< T > &list, const T &x, Equal eq=Equal())
	Sequential search on a dynamic list DynDlist.
template<typename T , class Equal = Aleph::equal_to<T>>
T *	Aleph::sequential_search (const DynList< T > &list, const T &x, Equal &eq)
template<typename T , class Equal = Aleph::equal_to<T>>
T *	Aleph::sequential_search (const DynList< T > &list, const T &x, Equal eq=Equal())
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::search_extreme (T *a, const long l, const long r, const Compare &cmp=Compare())
	Generic search in an array of an extreme element.
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::search_min (T *a, const long l, const long r, const Compare &cmp=Compare())
	Returns the smallest element of the array a between l and r.
template<typename T , class Compare = Aleph::greater<T>>
long	Aleph::search_max (T *a, const long l, const long r, const Compare &cmp=Compare())
	Returns the maximum element of the array a between l and r.
template<typename T , class Compare = Aleph::less<T>>
Dnode< T > *	Aleph::search_extreme (const Dnode< T > &list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
T *	Aleph::search_extreme (const DynDlist< T > &list, const Compare &cmp=Compare())
	Generic search for an extreme element in a list of nodes (Dlist<T>).
template<typename T , class Compare = Aleph::less<T>>
T *	Aleph::search_extreme (const DynList< T > &list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
T *	Aleph::search_min (const DynDlist< T > &list, const Compare &cmp=Compare())
	Returns the minimum element of the list.
template<typename T , class Compare = Aleph::greater<T>>
T *	Aleph::search_max (const DynDlist< T > &list, const Compare &cmp=Compare())
	Returns the maximum element of the list.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (T *a, const long l, const long r, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_move_assignable_v< T >)
	Sort an array using insertion sort.
template<class Compare >
void	Aleph::insert_sorted (Dlink &list, Dlink *p, const Compare &cmp)
	Inserts a node orderly into a doubly linked list.
template<class Compare >
void	Aleph::insert_sorted (HTList &list, Slinknc *p, const Compare &cmp)
template<class ListType , class Compare >
void	Aleph::list_insertion_sort (ListType &list, const Compare &cmp)
	Sorts a list of simple nodes by insertion method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (DynList< T > &l, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
DynList< T >	Aleph::insertion_sort (DynList< T > &&l, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (Dnode< T > &list, const Compare &cmp=Compare())
	Sorts the list by insertion method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::merge (T *a, const long l, const long m, const long r, std::vector< T > &buf, const Compare &cmp=Compare())
	Merge two sorted partitions of an array using a buffer.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::merge (T *a, const long l, const long m, const long r, const Compare &cmp=Compare())
	Merges two ordered partitions stored in an array.
template<typename T , class Compare >
void	Aleph::mergesort (T *a, const long l, const long r, std::vector< T > &buf, Compare cmp)
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sort an array using merge sort.
template<typename Tlist , class Compare >
void	Aleph::merge_lists (Tlist &l1, Tlist &l2, Tlist &result, const Compare &cmp=Compare())
	Merge two sorted lists into a single sorted list.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::merge_lists (Dnode< T > &l1, Dnode< T > &l2, Dnode< T > &result, const Compare &cmp=Compare())
	Merge two sorted lists of type Dnode into one.
template<typename Tlist , class Compare >
void	Aleph::mergesort (Tlist &list, const Compare &cmp=Compare())
	Sort a linked list using merge sort.
template<template< typename > class Tlist, typename T , class Compare = Aleph::less<T>>
void	Aleph::mergeinsertsort (Tlist< T > &list, const Compare &cmp=Compare(), const size_t lsz=Aleph::Insertion_Threshold)
	Sort a list by mergesort combined with the insert method.
template<template< typename > class Tlist, typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (Tlist< T > &list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (Dnode< T > &list, const Compare &cmp=Compare())
	Sorts a list according to the mergesort method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (DynDlist< T > &list, const Compare &cmp=Compare())
	Sorts a dynamic list based on the mergesort method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::mergesort (DynList< T > &list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
DynList< T >	Aleph::mergesort (DynList< T > &&list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::select_pivot (T *a, long l, long r, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_swappable_v< T >)
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::partition (T *a, const long l, const long r, const Compare &cmp=Compare()) noexcept(noexcept(cmp(a[0], a[0])) &&std::is_nothrow_swappable_v< T >)
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort_rec (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sorts an array using the quicksort method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort_no_tail (T *a, long l, long r, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort_rec_min (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sorts an array according to the quicksort method with minimum space consumption.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sort an array using iterative quicksort with optimizations.
size_t	Aleph::introsort_depth_limit (size_t n) noexcept
	Compute the depth limit for introsort.
template<typename T , class Compare >
void	Aleph::introsort_loop (T *a, long l, long r, size_t depth_limit, const Compare &cmp)
	Internal recursive function for introsort.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::introsort (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sort an array using introsort (introspective sort).
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::introsort (T *a, const size_t n, const Compare &cmp=Compare())
	Sort an array using introsort (convenience overload).
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::introsort (T *begin, T *end, const Compare &cmp=Compare())
	Sort a range using introsort (STL-style iterator interface).
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::introsort (Array< T > &arr, const Compare &cmp=Compare())
	Sort an Array container using introsort.
template<class Compare >
void	Aleph::quicksort (Dlink &list, const Compare &cmp=Compare())
	Sorts a linked list by the quicksort method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort (Dnode< T > &list, const Compare &cmp=Compare())
	Sorts a list by the quicksort method.
template<typename T , class Compare >
void	Aleph::quicksort (HTList &list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort (DynList< T > &list, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort_insertion (T *a, const long l, const long r, const Compare &cmp=Compare())
	Sorts an array by the improved quicksort method.
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::random_search (T *a, const T &x, const long l, const long r, const Compare &cmp=Compare())
	Random search for an element in an array.
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::random_search (DynArray< T > &a, const T &x, const long l, const long r, const Compare &cmp=Compare())
template<typename T , class Compare >
Dnode< T > *	Aleph::dlink_random_search (Dlink &list, const T &x, const Compare &cmp=Compare())
	Random search for an element in a dlink list.
template<typename T , class Compare = Aleph::less<T>>
Dnode< T > *	Aleph::random_search (Dlink &list, const T &x, const Compare &cmp=Compare())
	Random search for an element in a Dnode<T> list.
template<typename T , class Compare = Aleph::less<T>>
T *	Aleph::random_search (DynDlist< T > &list, const T &x, const Compare &cmp=Compare())
	Random search for an element in a dynamic list.
template<typename T , class Compare >
static const T &	Aleph::__random_select (T *a, const long i, const long l, const long r, const Compare &cmp)
template<typename T , class Compare , typename Container >
long	Aleph::select_pivot_op_impl (const Container &a, const long l, const long r, const Compare &cmp)
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::select_pivot_op (const DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Selects a pivot element as the median between the ends and the center.
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::select_pivot_op (const Array< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Selects a pivot element as the median between the ends and the center.
template<typename T , class Compare , typename Container >
long	Aleph::partition_op_impl (Container &a, const long l, const long r, const Compare &cmp)
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::partition_op (DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::partition_op (Array< T > &a, const long l, const long r, const Compare &cmp=Compare())
template<typename T , class Compare >
static const T &	Aleph::__random_select (DynArray< T > &a, const long i, const long l, const long r, const Compare &cmp=Compare())
template<typename T , class Compare >
static const T &	Aleph::__random_select (Array< T > &a, const long i, const long l, const long r, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
const T &	Aleph::random_select (DynArray< T > &a, const long i, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
const T &	Aleph::random_select (Array< T > &a, const long i, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
const T &	Aleph::random_select (T *a, const long i, const long n, const Compare &cmp=Compare())
	Select the k-th smallest element in an array (Quickselect).
template<typename T , class Compare = Aleph::less<T>>
const T &	Aleph::random_select (T *a, const long i, const long n, Compare &&cmp=Compare())
template<class Compare >
Dlink *	Aleph::dlink_random_select (Dlink &list, const size_t i, const Compare &cmp=Compare())
	Random selection of the ith element from a list based about Dlink.
template<typename T , class Compare = Aleph::less<T>>
Dnode< T > *	Aleph::random_select (Dlink &list, const size_t i, const Compare &cmp=Compare())
	Random selection of the ith element from a list based about Dlink.
template<typename T , class Compare = Aleph::less<T>>
T *	Aleph::random_select (DynDlist< T > &list, const size_t i, const Compare &cmp=Compare())
	Random selection of the ith element from a dynamic list.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::selection_sort (DynArray< T > &a, const Compare &cmp=Compare())
	Sorts a dynamic array by the selection method.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::bubble_sort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using bubble sort.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (C< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Sorts a dynamic array by the insert method.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
void	Aleph::insertion_sort (C< T > &a, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::shellsort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using Shell sort.
static long	Aleph::back_index (const long i) noexcept
template<typename T , class Compare >
void	Aleph::sift_up (DynArray< T > &table, const long n, const Compare &cmp)
template<typename T , class Compare >
void	Aleph::sift_down (DynArray< T > &table, const long start, const long n, const Compare &cmp)
template<typename T , class Compare >
void	Aleph::sift_down (DynArray< T > &table, const long n, const Compare &cmp)
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::heapsort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using heapsort.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
long	Aleph::partition (C< T > &a, const long l, const long r, const Compare &cmp=Compare())
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort_rec (DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
template<class Stack , class A , class B >
void	Aleph::push2 (Stack &stack, const A &a, const B &b)
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort (DynArray< T > &a, const Compare &cmp=Compare())
	Sorts a dynamic array by the quicksort method without recursion.
template<typename T , class Compare >
void	Aleph::sift_down_subrange (DynArray< T > &a, long start, const long n, const long offset, const Compare &cmp)
	Sift down operation for heapsort on a DynArray subrange.
template<typename T , class Compare >
void	Aleph::heapsort_subrange (DynArray< T > &a, const long l, const long r, const Compare &cmp)
	Heapsort a subrange of a DynArray.
template<typename T , class Compare >
void	Aleph::introsort_loop (DynArray< T > &a, long l, long r, size_t depth_limit, const Compare &cmp)
	Internal recursive function for introsort on DynArray.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::introsort (DynArray< T > &a, const Compare &cmp=Compare())
	Sort a dynamic array using introsort (introspective sort).
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::search_extreme (const DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Generic search in a dynamic array of an extreme element.
template<typename T , class Compare = Aleph::greater<T>>
long	Aleph::search_max (const DynArray< T > &a, const long l, const long r, const Compare &cmp=Compare())
	Returns the maximum element of the array a between l and r.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T > &a, const T &x, long l, long r, const Compare &cmp=Compare())
	Binary search on a sorted container.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T * > &a, const T &x, long l, long r, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T * > &a, const T &x, Compare &&cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
long	Aleph::binary_search (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Binary search on a dynamic ordered array.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynList< size_t >	Aleph::binary_search_dup (const C< T > &a, const T &x, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
T *	Aleph::bsearch (const C< T > &a, const T &x, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
T *	Aleph::bsearch (const C< T * > &a, const T &x, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynList< T * >	Aleph::bsearch_dup (const C< T > &a, const T &x, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynList< T * >	Aleph::bsearch_dup (const C< T * > &a, const T &x, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
long	Aleph::binindex (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Returns the index where a value appears (or should be inserted) in a sorted container.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynList< long >	Aleph::binindex_dup (const C< T > &a, const T &x, const Compare &cmp=Compare())
	Returns the indices of all occurrences of a value in a sorted container.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynList< long >	Aleph::binindex_dup (const C< T * > &a, const T &x, const Compare &cmp=Compare())
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynArray< size_t >	Aleph::build_index (const C< T > &a, const Compare &cmp=Compare())
	Build an index array for indirect sorting.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
DynArray< T * >	Aleph::build_index_ptr (const C< T > &a, const Compare &cmp=Compare())
	Builds and returns an array of pointers to the elements of container a sorted according to the comparison functor.
template<template< typename > class C, typename T , class Compare = Aleph::less<T>>
void	Aleph::quicksort_op (C< T > &a, const Compare &cmp=Compare(), const size_t threshold=Quicksort_Threshold)
	Optimized quicksort for containers using operator().
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::binary_search_rec (T *a, const T &x, const long l, const long r, const Compare &cmp=Compare())
	Recursive binary search on an ordered array.
template<typename T , class Compare = Aleph::less<T>>
long	Aleph::binary_search (T *a, const T &x, long l, long r, const Compare &cmp=Compare())
	Iterative binary search over an ordered array.

Variables
size_t	Aleph::Insertion_Threshold = 40
	Threshold for switching to insertion sort in hybrid algorithms.
size_t	Aleph::Quicksort_Threshold = 40
	Threshold for using quicksort vs simpler algorithms.
const int	Aleph::Not_Found = -1
	Return value for search functions when element is not found.

Detailed Description

Comprehensive sorting algorithms and search utilities for Aleph-w.

This file provides a complete collection of sorting algorithms and search utilities designed to work with arrays, dynamic arrays, and linked lists. All algorithms support custom comparison functors for flexible ordering.

Sorting Algorithms

Algorithm	Time Complexity	Space	Stable	Best For
Selection Sort	O(n²)	O(1)	No	Very small arrays
Insertion Sort	O(n²)	O(1)	Yes	Nearly sorted data
Bubble Sort	O(n²)	O(1)	Yes	Educational purposes
Shell Sort	O(n^1.5)	O(1)	No	Medium arrays
Merge Sort	O(n log n)	O(n) or O(1)	Yes	Lists, guaranteed performance
Quicksort	O(n log n)*	O(log n)	No	General purpose, fastest average
Heapsort	O(n log n)	O(1)	No	Guaranteed O(n log n), in-place

(* Quicksort has O(n²) worst case, but median-of-three pivot selection minimizes this risk)

Search Algorithms

Algorithm	Time Complexity	Requirements
Sequential Search	O(n)	None
Binary Search	O(log n)	Sorted container
Random Search	O(n log n)	Partially sorts during search
Random Select	O(n) expected	None (finds k-th element)

Usage Examples

#include <tpl_sort_utils.H>
#include <tpl_dynArray.H>
 
// Sort a dynamic array
DynArray<int> arr = {5, 2, 8, 1, 9};
quicksort(arr);  // arr is now {1, 2, 5, 8, 9}
 
// Sort with custom comparator (descending order)
quicksort(arr, [](int a, int b) { return a > b; });
 
// Sort a linked list
DynList<int> list = {5, 2, 8, 1, 9};
mergesort(list);  // O(1) space for lists!
 
// Binary search on sorted array
long idx = binary_search(arr, 5);  // Returns index of 5
 
// Find k-th smallest element
const int& third_smallest = random_select(arr.data(), 2, arr.size());

See also

DynArray, DynList, DynDlist

Author

Leandro Rabindranath León

Leandro Rabindranath León

Definition in file tpl_sort_utils.H.