ahSort.H File Reference

High-level sorting functions for Aleph containers. More...

#include <algorithm>
#include <numeric>
#include <ranges>
#include <stdexcept>
#include <utility>
#include <ah-errors.H>
#include <ahFunctional.H>
#include <tpl_sort_utils.H>
#include <tpl_dynDlist.H>
#include <htlist.H>
#include <ah-zip.H>

Include dependency graph for ahSort.H:

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

Go to the source code of this file.

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

Functions
	Aleph::List_Sort (DynList)
	Aleph::List_Sort (DynDlist)
template<typename T , class Cmp = Aleph::less<T>>
DynArray< T >	Aleph::sort (const DynArray< T > &a, Cmp &&cmp=Cmp())
	Returns a sorted copy of a DynArray.
template<typename T , class Cmp = Aleph::less<T>>
DynArray< T >	Aleph::sort (DynArray< T > &&a, Cmp &&cmp=Cmp())
	Sorts an rvalue DynArray in place and returns it.
template<typename T , class Cmp = Aleph::less<T>>
Array< T >	Aleph::sort (const Array< T > &a, Cmp &&cmp=Cmp())
	Returns a sorted copy of an Array.
template<typename T , class Cmp = Aleph::less<T>>
Array< T >	Aleph::sort (Array< T > &&a, Cmp &&cmp=Cmp())
	Sorts an rvalue Array in place and returns it.
template<typename Container , class Cmp = std::less<typename Container::value_type>>
Container	Aleph::stdsort (const Container &c, Cmp cmp=Cmp())
	Sorts an STL-compatible container using std::sort.
template<typename T , class Cmp = Aleph::less<T>>
DynArray< T > &	Aleph::in_place_sort (DynArray< T > &c, Cmp cmp=Cmp())
	Sorts a DynArray in place.
template<typename T , class Cmp = Aleph::less<T>>
Array< T > &	Aleph::in_place_sort (Array< T > &c, Cmp cmp=Cmp())
	Sorts an Array in place.
template<typename T >
Array< size_t >	Aleph::ranks (const Array< T > &array)
	Computes the rank of each element in an Array.
template<typename T >
DynArray< size_t >	Aleph::ranks (const DynArray< T > &array)
	Computes the rank of each element in a DynArray.
template<typename T >
DynArray< size_t >	Aleph::ranks (const DynList< T > &l)
	Computes the rank of each element in a DynList.
template<typename T >
DynArray< size_t >	Aleph::ranks (const DynDlist< T > &l)
	Computes the rank of each element in a DynDlist.
template<typename T >
auto	Aleph::pair_ranks (const Array< T > &c)
	Computes (value, rank) pairs for each element in an Array.
template<typename T >
auto	Aleph::pair_ranks (const DynArray< T > &c)
	Computes (value, rank) pairs for each element in a DynArray.
template<typename T >
auto	Aleph::pair_ranks (const DynList< T > &l)
	Computes (value, rank) pairs for each element in a DynList.
template<typename T >
auto	Aleph::pair_ranks (const DynDlist< T > &l)
	Computes (value, rank) pairs for each element in a DynDlist.
template<typename C , typename... Args, typename Cmp = std::less<typename C::value_type>>
void	Aleph::in_place_multisort_arrays (Cmp cmp, C &first, Args &... args)
	Sorts multiple arrays in place, using the first array as the key.

Detailed Description

High-level sorting functions for Aleph containers.

This file provides generic sorting functions that work with Aleph containers (DynList, DynDlist, DynArray, Array) using efficient sorting algorithms.

Sorting Algorithms Used

Container	Algorithm	Stable	Time	Space
DynList	Merge sort	Yes	O(n log n)	O(log n) stack
DynDlist	Merge sort	Yes	O(n log n)	O(log n) stack
DynArray	Quicksort	No	O(n log n) avg	O(log n) stack
Array	Quicksort	No	O(n log n) avg	O(log n) stack

Key Features

• Generic: Works with all Aleph sequence containers
• Custom comparators: All functions accept optional comparison functors
• Copy semantics: sort() returns a sorted copy (original unchanged)
• Move semantics: sort(std::move(c)) sorts efficiently by moving
• In-place: in_place_sort() modifies container directly
• Stable: List sorting preserves relative order of equal elements
• Ranking: ranks() and pair_ranks() compute element positions
• Multi-sort: in_place_multisort_arrays() sorts multiple arrays together

Functions Summary

Function	Description
sort(c)	Returns sorted copy of container
sort(c, cmp)	Sorted copy with custom comparator
in_place_sort(c)	Sorts container in place
stdsort(c)	Sorts STL containers using std::sort
ranks(c)	Returns array of ranks for each element
pair_ranks(c)	Returns pairs of (value, rank)
in_place_multisort_arrays(cmp, a, b, ...)	Sorts multiple arrays by first

Usage Examples

Basic Sorting

DynList<int> list = {5, 2, 8, 1, 9};
 
// Return sorted copy (original unchanged)
auto sorted = sort(list);  // {1, 2, 5, 8, 9}
 
// Sort with custom comparator (descending)
auto desc = sort(list, std::greater<int>());  // {9, 8, 5, 2, 1}
 
// In-place sorting (modifies list)
in_place_sort(list);

Move Semantics for Efficiency

DynList<int> temp = {5, 2, 8, 1, 9};
auto sorted = sort(std::move(temp));  // temp is now empty, no copy made

Ranking

DynArray<int> arr = {30, 10, 20};
auto r = ranks(arr);  // r = {2, 0, 1} (30 is rank 2, 10 is rank 0, etc.)

Multi-array Sorting

std::vector<int> keys = {3, 1, 2};
std::vector<std::string> values = {"c", "a", "b"};
 
// Sort both arrays by keys
in_place_multisort_arrays(std::less<int>(), keys, values);
// keys = {1, 2, 3}, values = {"a", "b", "c"}

See also

tpl_sort_utils.H Low-level sorting algorithms (mergesort, quicksort, etc.)

ahFunctional.H Functional utilities including comparison functors

Author

Leandro Rabindranath León

Definition in file ahSort.H.