Comprehensive benchmark for Aleph-w sorting algorithms. More...

#include <iostream>
#include <iomanip>
#include <chrono>
#include <string>
#include <functional>
#include <random>
#include <tclap/CmdLine.h>
#include <tpl_dynArray.H>
#include <tpl_array.H>
#include <tpl_dynDlist.H>
#include <htlist.H>
#include <tpl_sort_utils.H>
#include <ahSort.H>

Include dependency graph for sort_benchmark.C:

Classes
struct	BenchmarkConfig

class	Timer

class	DataGenerator

Functions
template<typename T >
void	to_dynlist (const DynArray< T > &arr, DynList< T > &list)

template<typename T >
void	to_dyndlist (const DynArray< T > &arr, DynDlist< T > &list)

template<typename T >
void	to_array (const DynArray< T > &src, Array< T > &dst)

void	print_header ()

void	print_result (const string &algo, const string &dist, const string &container, double time_ms, bool ok)

void	print_separator ()

void	benchmark_array_algorithms (const BenchmarkConfig &config, const string &dist_name, const DynArray< int > &source_data)

void	benchmark_contiguous_array (const BenchmarkConfig &config, const string &dist_name, const DynArray< int > &source_data)

void	benchmark_list_algorithms (const BenchmarkConfig &config, const string &dist_name, const DynArray< int > &source_data)

void	run_benchmarks (const BenchmarkConfig &config)

void	demonstrate_complexity (const BenchmarkConfig &base_config)

void	print_recommendations ()

int	main (int argc, char *argv[])

Detailed Description

Comprehensive benchmark for Aleph-w sorting algorithms.

This program benchmarks only Aleph-w sorting algorithms across different data distributions and Aleph-w container types. This helps understand which algorithm performs best for different scenarios and data structures. No std::sort is used; benchmarked data uses Aleph-w containers.

Why Benchmark Sorting Algorithms?

Different sorting algorithms have different performance characteristics:

Time complexity: Varies by algorithm and data distribution
Stability: Some preserve relative order of equal elements
Space complexity: Some require extra memory
Adaptivity: Some perform better on nearly-sorted data
Container compatibility: Some work better with arrays vs lists

Sorting Algorithms Tested (all from Aleph-w)

O(n²) Algorithms (for small inputs or special cases)

Selection Sort

Complexity: Always O(n²)
Stability: Not stable
Space: O(1) in-place
Best for: Small arrays, minimal swaps needed
Trade-off: Simple but slow

Insertion Sort

Complexity: O(n²) worst, O(n) best (nearly sorted)
Stability: Stable
Space: O(1) in-place
Best for: Small arrays, nearly sorted data
Trade-off: Adaptive, excellent for pre-sorted data

Bubble Sort

Complexity: O(n²)
Stability: Stable
Space: O(1) in-place
Best for: Educational purposes only
Trade-off: Simple but inefficient

Sub-quadratic Algorithms

Shellsort

Complexity: O(n^1.3) empirical, O(n²) worst case
Stability: Not stable
Space: O(1) in-place
Best for: Medium-sized arrays
Trade-off: Better than O(n²), worse than O(n log n)

O(n log n) Algorithms

Mergesort

Complexity: O(n log n) guaranteed
Stability: Stable
Space: O(n) extra memory
Best for: Linked lists, stable sort needed
Trade-off: Guaranteed performance, requires extra memory

Quicksort (iterative)

Complexity: O(n log n) average, O(n²) worst case
Stability: Not stable
Space: O(log n) stack (iterative version avoids overflow)
Best for: Arrays, random data, fastest average case
Trade-off: Fastest average, but worst case can be slow

Heapsort

Complexity: O(n log n) guaranteed
Stability: Not stable
Space: O(1) in-place
Best for: Guaranteed O(n log n) without extra memory
Trade-off: Slower than quicksort average, but guaranteed

Introsort (Introspective Sort)

Complexity: O(n log n) guaranteed
Stability: Not stable
Space: O(log n) stack
Best for: General purpose with worst-case guarantee
Trade-off: Same as quicksort average, but guaranteed O(n log n)
How it works: Starts with quicksort, falls back to heapsort when recursion depth exceeds 2*log(n), uses insertion sort for small partitions

Data Distributions Tested

Distribution	Description	Best Algorithm	Why
Random	Uniformly distributed	introsort()/quicksort_op()	Fast average case
Sorted	Already ascending	insertion_sort()	O(n) for sorted data
Reverse	Descending order	introsort()/heapsort()	Guaranteed O(n log n)
Nearly Sorted	5% elements swapped	insertion_sort()	Adaptive, O(n)
Few Unique	Only 10 distinct values	introsort()/quicksort_op()	Good partitioning
Sawtooth	Alternating runs	mergesort()	Exploits runs

Aleph-w Container Types

DynArray

Structure: Segmented blocks
Access: O(1) via operator[]
Best algorithms: Quicksort, heapsort (random access)

DynList

Structure: Singly linked list
Access: O(n) sequential
Best algorithms: Mergesort (works well with lists)

DynDlist

Structure: Doubly linked list
Access: O(n) sequential, bidirectional
Best algorithms: Mergesort (bidirectional helps)

Algorithm Selection Guide

Choose by Data Size

Small (< 50): Insertion sort
Medium (50-1000): Shellsort or quicksort
Large (> 1000): Mergesort, quicksort, or heapsort

Choose by Data Distribution

Random: Quicksort (fastest average)
Nearly sorted: Insertion sort (adaptive)
Reverse sorted: Mergesort or heapsort (avoid quicksort worst case)
Many duplicates: Quicksort with 3-way partitioning

Choose by Container

Array: Quicksort, heapsort (random access)
Linked list: Mergesort (sequential access)

Choose by Requirements

Stability needed: Mergesort or insertion sort
No extra memory: Heapsort or quicksort
Guaranteed O(n log n): Mergesort or heapsort

Complexity Summary

Algorithm	Best	Average	Worst	Space	Stable
Selection	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes
Bubble	O(n)	O(n²)	O(n²)	O(1)	Yes
Shellsort	O(n log n)	O(n^1.3)	O(n²)	O(1)	No
Mergesort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Introsort	O(n log n)	O(n log n)	O(n log n)	O(log n)	No

Usage

# Default benchmark (10000 elements)
./sort_benchmark
 
# Custom size
./sort_benchmark -n 50000
 
# All algorithms (including O(n²))
./sort_benchmark -n 1000 -a
 
# Test specific container
./sort_benchmark --list-only
./sort_benchmark --array-only
 
# Complexity demonstration
./sort_benchmark -c
 
# Algorithm selection guide
./sort_benchmark -g