=======
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.
Raw data
{
"_id": null,
"home_page": "https://github.com/emczg/corsort",
"name": "corsort",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "corsort",
"author": "Emma Caizergues",
"author_email": "emma.caizergues@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/51/84/26d53fd19ed0117985483f2d82a4798b012fd4befa757810d6a95dce470d/corsort-0.1.2.tar.gz",
"platform": null,
"description": "=======\nCorsort\n=======\n\n.. image:: https://img.shields.io/pypi/v/corsort.svg\n :target: https://pypi.python.org/pypi/corsort\n :alt: PyPI Status\n\n.. image:: https://github.com/emczg/corsort/workflows/build/badge.svg?branch=main\n :target: https://github.com/emczg/corsort/actions?query=workflow%3Abuild\n :alt: Build Status\n\n.. image:: https://github.com/emczg/corsort/workflows/docs/badge.svg?branch=main\n :target: https://github.com/emczg/corsort/actions?query=workflow%3Adocs\n :alt: Documentation Status\n\n\n.. image:: https://codecov.io/gh/emczg/corsort/branch/main/graphs/badge.svg\n :target: https://app.codecov.io/gh/emczg/corsort/tree/main/\n :alt: Code Coverage\n\n|\n\n.. image:: https://github.com/emczg/corsort/raw/main/docs/logo/logo.png\n :alt: Corsort logo\n :target: https://emczg.github.io/corsort/\n\n\nComparison-Oriented Sort.\n\n\n* Free software: GNU General Public License v3\n* Documentation: https://emczg.github.io/corsort/.\n\n\n--------\nFeatures\n--------\n\n* Implement Corsort and Multizip sort, some efficient anytime sorting algorithms.\n* Compare them with classical algorithms through Monte-Carlo simulations.\n\n-------\nCredits\n-------\n\nThis package was created with Cookiecutter_ and the `francois-durand/package_helper_2`_ project template.\n\n.. _Cookiecutter: https://github.com/audreyr/cookiecutter\n.. _`francois-durand/package_helper_2`: https://github.com/francois-durand/package_helper_2\n\n\n=======\nHistory\n=======\n\n-------------------------------------------------------------------\n0.1.2 (2023-06-05): Binary Insertion Sort, Multizip Sort, Shellsort\n-------------------------------------------------------------------\n\n* `Corsort` and subclasses (i.e. non-jit Corsort algorithms):\n\n * Add parameter `record_leq`. If True, then record all the states of the `leq_` matrix.\n * Add parameter `final_score`. Scorer used to compute the tentative estimate of the sorted list.\n\n* Add `CorsortChainDecompositionMergeV`: Corsort based on chain decomposition, with \"V-shape\" merging.\n* Add `CorsortChainDecompositionMergeX`: Corsort based on chain decomposition, with \"X-shape\" merging.\n* Add `greedy_chain_decomposition`: greedy chain decomposition.\n* Add `longest_chain`: longest chain.\n* Add `longest_chain_starting_at`: longest chain starting at a given item.\n* Add `multi_merge`: merge consecutive sorted portions of a list, two by two, in alternance. Used for multizip sort.\n* Add `scorer_delta` and `scorer_rho`: scorer delta or rho. Mostly used for the `final_score` parameter of `Corsort`.\n* Add `SortBinaryInsertion`: binary insertion sort.\n* Add `SortMultizip`: multizip sort.\n* Add `SortShell`: Shellsort.\n* Add `split_pointer_lists`: compute the indices of the boundaries for all the steps of bottom-up (BFS) merge sort.\n* Add `transitive_reduction`: transitive reduction of a `leq` matrix.\n* `WrapFullJit`: add parameter `record_states`. If True, then record the states of the algorithm.\n* Add predefined wrappers using `WrapFullJit`: `JitCorsortBorda`, `JitHeapsort`, `JitCorsortDeltaMaxRho`,\n `JitCorsortDeltaSumRho`, etc.\n* Rename `CorSort` to `Corsort`, and similarly for subclasses.\n* Rename `print_order` to `print_order_as_letters`.\n* Rename `drift` to `delta` and `spaced` to `rho` in all function names in order to match the notations of our papers.\n* Rename `scorer_drift` to `jit_scorer_delta` and `scorer_spaced` to `jit_scorer_rho`.\n* Rename `plus` to `sum` in jit corsort functions. For example, rename `jit_corsort_drift_plus_spaced` to\n `jit_corsort_delta_sum_rho`.\n* Rename `SortMergeBfs` to `SortMergeBottomUp`.\n* Rename `SortMergeDfs` to `SortMergeTopDown`.\n\n------------------------------------------\n0.1.1 (2023-04-7): More history, ChainAndY\n------------------------------------------\n\n* Add `Sort.history_comparisons_values_`: history of the pairwise comparisons, in terms of compared values\n (whereas `history_comparisons_` gives the original indices). Similarly, add\n `WrapSortScorer.history_comparisons_values_` and `WrapFullJit.history_comparisons_values_`.\n* Add `CorSort.history_leq_`: history of the matrix `leq_` representing the current poset. This is recorded\n if the newly added parameter `record_leq` is True.\n* Add `WrapFullJit.history_states_`: history of the state of the list.\n* Add `ChainAndY`: poset consisting of a chain and a Y-shape.\n* Add `print_corsort_execution`: generate LaTeX code for a CorSort execution.\n* `partition` is now stable (in the sense of \"stable\" sorting), hence also `SortQuick`, `SortAsortQuickselect`,\n and `SortLargestInterval`.\n\n---------------------------------\n0.1.0 (2023-02-16): First release\n---------------------------------\n\n* Corsort (regular Python or with numba acceleration).\n* Classical sorting algorithms: Asort (with quickselect for median selection), Ford-Johnson, quicksort, quicksort with\n priority on the largest interval, merge sort (DFS or BFS).\n* Entropy bound.\n* Monte-Carlo simulations.\n",
"bugtrack_url": null,
"license": "GNU General Public License v3",
"summary": "Comparison-Oriented Sort.",
"version": "0.1.2",
"project_urls": {
"Homepage": "https://github.com/emczg/corsort"
},
"split_keywords": [
"corsort"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "ae662bf4cee960592c596d6d11c61cc4ccf95b7781dcfdcbd79dd2e75284b929",
"md5": "91775e895ec64ae16a7cf29955395332",
"sha256": "5db75749571a30a59f983cdf884e93224e7752333bf1e398b44652d73295b09d"
},
"downloads": -1,
"filename": "corsort-0.1.2-py2.py3-none-any.whl",
"has_sig": false,
"md5_digest": "91775e895ec64ae16a7cf29955395332",
"packagetype": "bdist_wheel",
"python_version": "py2.py3",
"requires_python": ">=3.7",
"size": 48957,
"upload_time": "2023-06-05T12:11:47",
"upload_time_iso_8601": "2023-06-05T12:11:47.218249Z",
"url": "https://files.pythonhosted.org/packages/ae/66/2bf4cee960592c596d6d11c61cc4ccf95b7781dcfdcbd79dd2e75284b929/corsort-0.1.2-py2.py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "518426d53fd19ed0117985483f2d82a4798b012fd4befa757810d6a95dce470d",
"md5": "8b88007f7a00334cf86900cdbc90067d",
"sha256": "8a3215cc2ddc15a94bb79fc86e728dde3a0037db1cbc3b12441bf9f1ae78de1d"
},
"downloads": -1,
"filename": "corsort-0.1.2.tar.gz",
"has_sig": false,
"md5_digest": "8b88007f7a00334cf86900cdbc90067d",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 59894,
"upload_time": "2023-06-05T12:11:49",
"upload_time_iso_8601": "2023-06-05T12:11:49.249365Z",
"url": "https://files.pythonhosted.org/packages/51/84/26d53fd19ed0117985483f2d82a4798b012fd4befa757810d6a95dce470d/corsort-0.1.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-06-05 12:11:49",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "emczg",
"github_project": "corsort",
"travis_ci": false,
"coveralls": true,
"github_actions": true,
"requirements": [],
"tox": true,
"lcname": "corsort"
}
JSON
