corsort

======= Corsort

.. image:: https://img.shields.io/pypi/v/corsort.svg :target: https://pypi.python.org/pypi/corsort :alt: PyPI Status

.. image:: https://github.com/emczg/corsort/workflows/build/badge.svg?branch=main :target: https://github.com/emczg/corsort/actions?query=workflow%3Abuild :alt: Build Status

.. image:: https://github.com/emczg/corsort/workflows/docs/badge.svg?branch=main :target: https://github.com/emczg/corsort/actions?query=workflow%3Adocs :alt: Documentation Status

.. image:: https://codecov.io/gh/emczg/corsort/branch/main/graphs/badge.svg :target: https://app.codecov.io/gh/emczg/corsort/tree/main/ :alt: Code Coverage

|

.. image:: https://github.com/emczg/corsort/raw/main/docs/logo/logo.png :alt: Corsort logo :target: https://emczg.github.io/corsort/

Comparison-Oriented Sort.

• Free software: GNU General Public License v3
• Documentation: https://emczg.github.io/corsort/.

---

Features

• Implement Corsort and Multizip sort, some efficient anytime sorting algorithms.
• Compare them with classical algorithms through Monte-Carlo simulations.

---

Credits

This package was created with Cookiecutter_ and the francois-durand/package_helper_2_ project template.

.. _Cookiecutter: https://github.com/audreyr/cookiecutter .. _francois-durand/package_helper_2: https://github.com/francois-durand/package_helper_2

======= History

---

0.1.2 (2023-06-05): Binary Insertion Sort, Multizip Sort, Shellsort

• Corsort and subclasses (i.e. non-jit Corsort algorithms):

  • Add parameter record_leq. If True, then record all the states of the leq_ matrix.
  • Add parameter final_score. Scorer used to compute the tentative estimate of the sorted list.

• Add CorsortChainDecompositionMergeV: Corsort based on chain decomposition, with "V-shape" merging.

• Add CorsortChainDecompositionMergeX: Corsort based on chain decomposition, with "X-shape" merging.

• Add greedy_chain_decomposition: greedy chain decomposition.

• Add longest_chain: longest chain.

• Add longest_chain_starting_at: longest chain starting at a given item.

• Add multi_merge: merge consecutive sorted portions of a list, two by two, in alternance. Used for multizip sort.

• Add scorer_delta and scorer_rho: scorer delta or rho. Mostly used for the final_score parameter of Corsort.

• Add SortBinaryInsertion: binary insertion sort.

• Add SortMultizip: multizip sort.

• Add SortShell: Shellsort.

• Add split_pointer_lists: compute the indices of the boundaries for all the steps of bottom-up (BFS) merge sort.

• Add transitive_reduction: transitive reduction of a leq matrix.

• WrapFullJit: add parameter record_states. If True, then record the states of the algorithm.

• Add predefined wrappers using WrapFullJit: JitCorsortBorda, JitHeapsort, JitCorsortDeltaMaxRho, JitCorsortDeltaSumRho, etc.

• Rename CorSort to Corsort, and similarly for subclasses.

• Rename print_order to print_order_as_letters.

• Rename drift to delta and spaced to rho in all function names in order to match the notations of our papers.

• Rename scorer_drift to jit_scorer_delta and scorer_spaced to jit_scorer_rho.

• Rename plus to sum in jit corsort functions. For example, rename jit_corsort_drift_plus_spaced to jit_corsort_delta_sum_rho.

• Rename SortMergeBfs to SortMergeBottomUp.

• Rename SortMergeDfs to SortMergeTopDown.

---

0.1.1 (2023-04-7): More history, ChainAndY

• Add Sort.history_comparisons_values_: history of the pairwise comparisons, in terms of compared values (whereas history_comparisons_ gives the original indices). Similarly, add WrapSortScorer.history_comparisons_values_ and WrapFullJit.history_comparisons_values_.
• Add CorSort.history_leq_: history of the matrix leq_ representing the current poset. This is recorded if the newly added parameter record_leq is True.
• Add WrapFullJit.history_states_: history of the state of the list.
• Add ChainAndY: poset consisting of a chain and a Y-shape.
• Add print_corsort_execution: generate LaTeX code for a CorSort execution.
• partition is now stable (in the sense of "stable" sorting), hence also SortQuick, SortAsortQuickselect, and SortLargestInterval.

---

0.1.0 (2023-02-16): First release

• Corsort (regular Python or with numba acceleration).
• Classical sorting algorithms: Asort (with quickselect for median selection), Ford-Johnson, quicksort, quicksort with priority on the largest interval, merge sort (DFS or BFS).
• Entropy bound.
• Monte-Carlo simulations.