# sorting-algorithmsπ’
Theory analysis and code implementation of common array sorting algorithms.
## π start from galley
First, You need to click the [`fork`](https://github.com/linjing-lab/sorting-algorithms/fork) button to create your own sub repository, or use the following command to synchronize the repository to the local folder:
```git
git clone https://github.com/linjing-lab/sorting-algorithms.git
```
Second, I have put different implemented versions of various sorting algorithms in the [`galley`](./docs/galley/) folder, everyone can import it with the underlying command:
```python
import galley as ge
```
For example, If I use the `bubble` sorting algorithm to sort a real data in reverse, use the following commands:
```python
import random
data = [random.randint(0, 100) for _ in range(10000)]
ge.bubble.flag(data, reverse=True)
print(data)
```
Lastly, many algorithms are *in-place* sorting, and a few are *out-place*, you should pay attention to it during the study, so that you can distinguish between `print(data)` and `print(method)`. I mainly use `if... else...` to implement the reverse order of sorting algorithms in gallery and the partition of some algorithms.
## π sorting complexity
<div align="center">
|Algorithm||Time Complexity||Space Complexity|
|--|--|--|--|--|
|---|Best|Average|Worst|Worst|
|[Quicksort](./docs/Quicksort.md)|$\Omega(n \log(n))$|$\Theta(n \log(n))$|$O(n^2)$|$O(\log(n))$|
|[Mergesort](./docs/Mergesort.md)|$\Omega(n \log(n))$|$\Theta(n \log(n))$|$O(n \log(n))$|$O(n)$|
|[Timsort](./docs/Timsort.md)|$\Omega(n)$|$\Theta(n \log(n))$|$O(n \log(n))$|$O(n)$|
|[Heapsort](./docs/Heapsort.md)|$\Omega(n \log(n))$|$\Theta(n \log(n))$|$O(n \log(n))$|$O(1)$|
|[Bubble Sort](./docs/Bubblesort.md)|$\Omega(n)$|$\Theta(n^2)$|$O(n^2)$|$O(1)$|
|[Insertion Sort](./docs/Insertionsort.md)|$\Omega(n)$|$\Theta(n^2)$|$O(n^2)$|$O(1)$|
|[Selection Sort](./docs/Selectionsort.md)|$\Omega(n^2)$|$\Theta(n^2)$|$O(n^2)$|$O(1)$|
|[Tree Sort](./docs/Treesort.md)|$\Omega(n \log(n))$|$\Theta(n \log(n))$|$O(n^2)$|$O(n)$|
|[Shell Sort](./docs/Shellsort.md)|$\Omega(n \log (n))$|$\Theta(n(\log (n))^2)$|$O(n(\log (n))^2)$|$O(1)$|
|[Bucket Sort](./docs/Bucketsort.md)|$\Omega(n + k)$|$\Theta(n + k)$|$O(n^2)$|$O(n)$|
|[Radix Sort](./docs/Radixsort.md)|$\Omega(nk)$|$\Theta(nk)$|$O(nk)$|$O(n+k)$|
|[Counting Sort](./docs/Countingsort.md)|$\Omega(n + k)$|$\Theta(n + k)$|$O(n + k)$|$O(k)$|
|Cubesort|$\Omega(n)$|$\Theta(n \log(n))$|$O(n \log(n))$|$O(n)$|
</div>
## π test description
I test the performance of the sorting algorithm after adding the [*keyword*](./keyword_sorting.py) sorting in the [*test_key*](./test_key.py) file (The [*utils*](./utils.py) file stores the most core function for keyword sorting), test the time accumulation of the sorting algorithm with respect to the large data set in the [*test_time*](./test_time.py) file, and test whether the reverse parameter of the sorting algorithms is designed correctly in the [*test_reverse*](./test_reverse.py) file, including the robustness of these.
The design of reverse sorting of all methods is completely correct, and the design of keyword sorting is feasible, which is consistent with the usage of *sorted* parameter officially released by Python.
The example of keyword sorting are underlying:
```python
data = [('Alex', 100, 90, 98, 95), ('Jack', 97, 88, 98, 92), ('Peter', 92, 95, 92, 96), ('Li', 97, 89, 98, 92)]
insertion_sort(data, key=lambda x: (x[1], x[2]), reverse=False)
# sorted(data, key=lambda x: (x[1], x[2]), reverse=False)
print(data)
'''
reverse=False:
[('Peter', 92, 95, 92, 96), ('Jack', 97, 88, 98, 92), ('Li', 97, 89, 98, 92), ('Alex', 100, 90, 98, 95)]
reverse=True:
[('Alex', 100, 90, 98, 95), ('Li', 97, 89, 98, 92), ('Jack', 97, 88, 98, 92), ('Peter', 92, 95, 92, 96)]
'''
```
you can see more 5 methods in [*keyword_sorting*](./keyword_sorting.py) file.
## π pip install
As you can see, I create a core function to drive keyword sorting just by opening up an array with the size of k (k = nums of keyword), and the type of sorting implemented by Python officially released is Timsort, which is more complicated than the other algorithms in my released packages in the future.
```python
!pip install sortingx # in jupyter
pip install sortingx # in cmd
```
sortingx can do whatever `list.sort()` do, and support more methods and more data types.
explain:
- [sortingx-1.1.0](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.0) is the first version aligned with the `list.sort()` usage method.
- [sortingx-1.1.1](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.1) is the first stable version accelerated with typing_extensions.
- [sortingx-1.1.2](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.2) is the first stable version that has a return value and extends the iterable data types.
- [sortingx-1.1.3](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.3) is the version that complete the typing of local variables and align with `sorted()` usage method.
- [sortingx-1.2.0](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.0) is the end version of sorting series, which optimize the kernel of generate.
- [sortingx-1.2.1](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.1) is the portable version that comparison is faster than ever, the generate is more portable.
By the way, I didn't complete all the iterative data types, in order to develop a more targeted scenario. If you are **interested** in other iterative data types, please add them in the `convert` function of the `_utils.py` file, for example: bytes, bytearray, range, zip. If you need to deal with `dict_keys`, `dict_values`, `dict_items`, please use `list()` to convert the variables of these data types before using any method of sortingx.
- [sortingx-1.2.2](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.2) is the package that support `range`, `zip`, `dict_keys`, `dict_values`, `dict_items` additionally, you can choose what suitable data you want to input.
- [sortingx-1.2.3](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.3) is the package that corrected the situation where elements are equal in `compare`, support more input data, like data as `[['Jack', (98, 100)], ['Bob', (98, 99)], ['Jessi', (98, 97)]]` and key as `lambda x: x[1][0]`.
- [sortingx-1.3.0](https://github.com/linjing-lab/sorting-algorithms/tree/v1.3.0) is the final version that fully aligned with the `sorted`', reduces redundant data exchanging. like data as `[('Alex', 97, 90, 98, 95), ('Jack', 97, 88, 98, 92), ('Peter', 92, 95, 92, 96), ('Li', 97, 89, 98, 92)]` and key as `key=lambda x: x[1]`.
- [sortingx-1.3.1](https://github.com/linjing-lab/sorting-algorithms/tree/v1.3.1) is the improved version from v1.3.0, and pre-operations from `_utils` are more conise to reduce shallow copy in Runtime.
- [sortingx-1.3.2](https://github.com/linjing-lab/sorting-algorithms/tree/v1.3.2) is the optimized version from v1.3.1, and shrink the returns of calling intrinsic function named `__len__` to get length of `__iterable`.
refer to [this](https://github.com/linjing-lab/sorting-algorithms/blob/main/README_release.md) for downloaded info.
## LICENSE
[Apache 2.0](./LICENSE)
Raw data
{
"_id": null,
"home_page": "https://github.com/linjing-lab/sorting-algorithms",
"name": "sortingx",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "",
"author": "\u6797\u666f",
"author_email": "linjing010729@163.com",
"download_url": "https://files.pythonhosted.org/packages/67/46/50c69bbc769a794501472e2bcba837d13168e3d809fd9ee49ea1cc93a4ce/sortingx-1.3.2.tar.gz",
"platform": null,
"description": "# sorting-algorithms\ud83c\udfa2\r\n\r\nTheory analysis and code implementation of common array sorting algorithms.\r\n\r\n## \ud83d\udccd start from galley\r\n\r\nFirst, You need to click the [`fork`](https://github.com/linjing-lab/sorting-algorithms/fork) button to create your own sub repository, or use the following command to synchronize the repository to the local folder:\r\n\r\n```git\r\ngit clone https://github.com/linjing-lab/sorting-algorithms.git\r\n```\r\n\r\nSecond, I have put different implemented versions of various sorting algorithms in the [`galley`](./docs/galley/) folder, everyone can import it with the underlying command:\r\n\r\n```python\r\nimport galley as ge\r\n```\r\n\r\nFor example, If I use the `bubble` sorting algorithm to sort a real data in reverse, use the following commands:\r\n\r\n```python\r\nimport random \r\ndata = [random.randint(0, 100) for _ in range(10000)]\r\nge.bubble.flag(data, reverse=True)\r\nprint(data)\r\n```\r\n\r\nLastly, many algorithms are *in-place* sorting, and a few are *out-place*, you should pay attention to it during the study, so that you can distinguish between `print(data)` and `print(method)`. I mainly use `if... else...` to implement the reverse order of sorting algorithms in gallery and the partition of some algorithms.\r\n\r\n## \ud83d\udcca sorting complexity\r\n\r\n<div align=\"center\">\r\n\r\n|Algorithm||Time Complexity||Space Complexity|\r\n|--|--|--|--|--|\r\n|---|Best|Average|Worst|Worst|\r\n|[Quicksort](./docs/Quicksort.md)|$\\Omega(n \\log(n))$|$\\Theta(n \\log(n))$|$O(n^2)$|$O(\\log(n))$|\r\n|[Mergesort](./docs/Mergesort.md)|$\\Omega(n \\log(n))$|$\\Theta(n \\log(n))$|$O(n \\log(n))$|$O(n)$|\r\n|[Timsort](./docs/Timsort.md)|$\\Omega(n)$|$\\Theta(n \\log(n))$|$O(n \\log(n))$|$O(n)$|\r\n|[Heapsort](./docs/Heapsort.md)|$\\Omega(n \\log(n))$|$\\Theta(n \\log(n))$|$O(n \\log(n))$|$O(1)$|\r\n|[Bubble Sort](./docs/Bubblesort.md)|$\\Omega(n)$|$\\Theta(n^2)$|$O(n^2)$|$O(1)$|\r\n|[Insertion Sort](./docs/Insertionsort.md)|$\\Omega(n)$|$\\Theta(n^2)$|$O(n^2)$|$O(1)$|\r\n|[Selection Sort](./docs/Selectionsort.md)|$\\Omega(n^2)$|$\\Theta(n^2)$|$O(n^2)$|$O(1)$|\r\n|[Tree Sort](./docs/Treesort.md)|$\\Omega(n \\log(n))$|$\\Theta(n \\log(n))$|$O(n^2)$|$O(n)$|\r\n|[Shell Sort](./docs/Shellsort.md)|$\\Omega(n \\log (n))$|$\\Theta(n(\\log (n))^2)$|$O(n(\\log (n))^2)$|$O(1)$|\r\n|[Bucket Sort](./docs/Bucketsort.md)|$\\Omega(n + k)$|$\\Theta(n + k)$|$O(n^2)$|$O(n)$|\r\n|[Radix Sort](./docs/Radixsort.md)|$\\Omega(nk)$|$\\Theta(nk)$|$O(nk)$|$O(n+k)$|\r\n|[Counting Sort](./docs/Countingsort.md)|$\\Omega(n + k)$|$\\Theta(n + k)$|$O(n + k)$|$O(k)$|\r\n|Cubesort|$\\Omega(n)$|$\\Theta(n \\log(n))$|$O(n \\log(n))$|$O(n)$|\r\n\r\n</div>\r\n\r\n## \ud83d\ude4b test description\r\n\r\nI test the performance of the sorting algorithm after adding the [*keyword*](./keyword_sorting.py) sorting in the [*test_key*](./test_key.py) file (The [*utils*](./utils.py) file stores the most core function for keyword sorting), test the time accumulation of the sorting algorithm with respect to the large data set in the [*test_time*](./test_time.py) file, and test whether the reverse parameter of the sorting algorithms is designed correctly in the [*test_reverse*](./test_reverse.py) file, including the robustness of these.\r\n\r\nThe design of reverse sorting of all methods is completely correct, and the design of keyword sorting is feasible, which is consistent with the usage of *sorted* parameter officially released by Python.\r\n\r\nThe example of keyword sorting are underlying:\r\n\r\n```python\r\ndata = [('Alex', 100, 90, 98, 95), ('Jack', 97, 88, 98, 92), ('Peter', 92, 95, 92, 96), ('Li', 97, 89, 98, 92)]\r\ninsertion_sort(data, key=lambda x: (x[1], x[2]), reverse=False)\r\n# sorted(data, key=lambda x: (x[1], x[2]), reverse=False)\r\nprint(data)\r\n\r\n'''\r\nreverse=False: \r\n[('Peter', 92, 95, 92, 96), ('Jack', 97, 88, 98, 92), ('Li', 97, 89, 98, 92), ('Alex', 100, 90, 98, 95)]\r\n\r\nreverse=True: \r\n[('Alex', 100, 90, 98, 95), ('Li', 97, 89, 98, 92), ('Jack', 97, 88, 98, 92), ('Peter', 92, 95, 92, 96)]\r\n'''\r\n```\r\n\r\nyou can see more 5 methods in [*keyword_sorting*](./keyword_sorting.py) file.\r\n\r\n## \ud83c\udf92 pip install\r\n\r\nAs you can see, I create a core function to drive keyword sorting just by opening up an array with the size of k (k = nums of keyword), and the type of sorting implemented by Python officially released is Timsort, which is more complicated than the other algorithms in my released packages in the future.\r\n\r\n```python\r\n!pip install sortingx # in jupyter\r\npip install sortingx # in cmd\r\n```\r\nsortingx can do whatever `list.sort()` do, and support more methods and more data types.\r\n\r\nexplain:\r\n- [sortingx-1.1.0](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.0) is the first version aligned with the `list.sort()` usage method.\r\n- [sortingx-1.1.1](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.1) is the first stable version accelerated with typing_extensions.\r\n- [sortingx-1.1.2](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.2) is the first stable version that has a return value and extends the iterable data types.\r\n- [sortingx-1.1.3](https://github.com/linjing-lab/sorting-algorithms/tree/v1.1.3) is the version that complete the typing of local variables and align with `sorted()` usage method.\r\n- [sortingx-1.2.0](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.0) is the end version of sorting series, which optimize the kernel of generate.\r\n- [sortingx-1.2.1](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.1) is the portable version that comparison is faster than ever, the generate is more portable.\r\n\r\nBy the way, I didn't complete all the iterative data types, in order to develop a more targeted scenario. If you are **interested** in other iterative data types, please add them in the `convert` function of the `_utils.py` file, for example: bytes, bytearray, range, zip. If you need to deal with `dict_keys`, `dict_values`, `dict_items`, please use `list()` to convert the variables of these data types before using any method of sortingx.\r\n\r\n- [sortingx-1.2.2](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.2) is the package that support `range`, `zip`, `dict_keys`, `dict_values`, `dict_items` additionally, you can choose what suitable data you want to input.\r\n- [sortingx-1.2.3](https://github.com/linjing-lab/sorting-algorithms/tree/v1.2.3) is the package that corrected the situation where elements are equal in `compare`, support more input data, like data as `[['Jack', (98, 100)], ['Bob', (98, 99)], ['Jessi', (98, 97)]]` and key as `lambda x: x[1][0]`.\r\n- [sortingx-1.3.0](https://github.com/linjing-lab/sorting-algorithms/tree/v1.3.0) is the final version that fully aligned with the `sorted`', reduces redundant data exchanging. like data as `[('Alex', 97, 90, 98, 95), ('Jack', 97, 88, 98, 92), ('Peter', 92, 95, 92, 96), ('Li', 97, 89, 98, 92)]` and key as `key=lambda x: x[1]`.\r\n- [sortingx-1.3.1](https://github.com/linjing-lab/sorting-algorithms/tree/v1.3.1) is the improved version from v1.3.0, and pre-operations from `_utils` are more conise to reduce shallow copy in Runtime.\r\n- [sortingx-1.3.2](https://github.com/linjing-lab/sorting-algorithms/tree/v1.3.2) is the optimized version from v1.3.1, and shrink the returns of calling intrinsic function named `__len__` to get length of `__iterable`.\r\n\r\nrefer to [this](https://github.com/linjing-lab/sorting-algorithms/blob/main/README_release.md) for downloaded info.\r\n\r\n## LICENSE\r\n\r\n[Apache 2.0](./LICENSE)\r\n",
"bugtrack_url": null,
"license": "Apache 2.0",
"summary": "The powerful package designed for sorting.",
"version": "1.3.2",
"project_urls": {
"Download": "https://github.com/linjing-lab/sorting-algorithms/tags",
"Homepage": "https://github.com/linjing-lab/sorting-algorithms",
"Source": "https://github.com/linjing-lab/sorting-algorithms/tree/main/sortingx",
"Tracker": "https://github.com/linjing-lab/sorting-algorithms/issues"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "ec9b4da1503c2a8a05d5e8e43cd7fbdc6e911bb85bbdca13bdedcc58600b800f",
"md5": "c6919ec2c346edaaf95dfef8e83e7ffb",
"sha256": "0b085638175d2475098d608aab6e33b74a91afe757aff628a9701011277da6d2"
},
"downloads": -1,
"filename": "sortingx-1.3.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c6919ec2c346edaaf95dfef8e83e7ffb",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 12703,
"upload_time": "2023-06-26T09:14:55",
"upload_time_iso_8601": "2023-06-26T09:14:55.934775Z",
"url": "https://files.pythonhosted.org/packages/ec/9b/4da1503c2a8a05d5e8e43cd7fbdc6e911bb85bbdca13bdedcc58600b800f/sortingx-1.3.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "674650c69bbc769a794501472e2bcba837d13168e3d809fd9ee49ea1cc93a4ce",
"md5": "dd0ba36f9c4ce8b2ffdbfb5eaf79d545",
"sha256": "c9249b36fda183e16bd7c68585473c5cbadd2f6bf4810de3c66787b1bc3d98d5"
},
"downloads": -1,
"filename": "sortingx-1.3.2.tar.gz",
"has_sig": false,
"md5_digest": "dd0ba36f9c4ce8b2ffdbfb5eaf79d545",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 14072,
"upload_time": "2023-06-26T09:14:58",
"upload_time_iso_8601": "2023-06-26T09:14:58.654414Z",
"url": "https://files.pythonhosted.org/packages/67/46/50c69bbc769a794501472e2bcba837d13168e3d809fd9ee49ea1cc93a4ce/sortingx-1.3.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-06-26 09:14:58",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "linjing-lab",
"github_project": "sorting-algorithms",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [],
"lcname": "sortingx"
}
JSON
