mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
Aayush Guptapre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>Christian Clauss* sorts: make odd_even_sort generic over any comparable type (Part of #15234) Adds a Comparable-bound TypeVar (matching the pattern used in insertion_sort.py), doctests covering strings, floats, and the non-comparable TypeError case, and registers odd_even_sort in the shared test_sort_rejects_non_comparable_items test. Part of #15234 * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Drop redundant module-level TypeVar, bind Comparable to __gt__ * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci * Fix import block formatting per ruff --------- Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com> Co-authored-by: Christian Clauss <cclauss@me.com>
67 lines
2.2 KiB
Python
67 lines
2.2 KiB
Python
"""
|
|
Odd even sort implementation.
|
|
|
|
https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort
|
|
"""
|
|
|
|
from collections.abc import MutableSequence
|
|
from typing import Any, Protocol
|
|
|
|
|
|
class Comparable(Protocol):
|
|
def __gt__(self, other: Any, /) -> bool: ...
|
|
|
|
|
|
def odd_even_sort[T: Comparable](collection: MutableSequence[T]) -> MutableSequence[T]:
|
|
"""
|
|
Sort input with odd even sort.
|
|
|
|
This algorithm uses the same idea of bubblesort,
|
|
but by first dividing in two phase (odd and even).
|
|
Originally developed for use on parallel processors
|
|
with local interconnections.
|
|
:param collection: mutable ordered sequence of elements
|
|
:return: same collection in ascending order
|
|
Examples:
|
|
>>> odd_even_sort([5 , 4 ,3 ,2 ,1])
|
|
[1, 2, 3, 4, 5]
|
|
>>> odd_even_sort([])
|
|
[]
|
|
>>> odd_even_sort([-10 ,-1 ,10 ,2])
|
|
[-10, -1, 2, 10]
|
|
>>> odd_even_sort([1 ,2 ,3 ,4])
|
|
[1, 2, 3, 4]
|
|
>>> odd_even_sort(["c","a","b"])
|
|
['a', 'b', 'c']
|
|
>>> odd_even_sort([2.5, -1, 0.0])
|
|
[-1, 0.0, 2.5]
|
|
>>> odd_even_sort([1,"a"])
|
|
Traceback (most recent call last):
|
|
...
|
|
TypeError: '>' not supported between instances of 'int' and 'str'
|
|
"""
|
|
is_sorted = False
|
|
while is_sorted is False: # Until all the indices are traversed keep looping
|
|
is_sorted = True
|
|
for i in range(0, len(collection) - 1, 2): # iterating over all even indices
|
|
if collection[i] > collection[i + 1]:
|
|
collection[i], collection[i + 1] = collection[i + 1], collection[i]
|
|
# swapping if elements not in order
|
|
is_sorted = False
|
|
|
|
for i in range(1, len(collection) - 1, 2): # iterating over all odd indices
|
|
if collection[i] > collection[i + 1]:
|
|
collection[i], collection[i + 1] = collection[i + 1], collection[i]
|
|
# swapping if elements not in order
|
|
is_sorted = False
|
|
return collection
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("Enter list to be sorted")
|
|
input_list = [int(x) for x in input().split()]
|
|
# inputing elements of the list in one line
|
|
sorted_list = odd_even_sort(input_list)
|
|
print("The sorted list is")
|
|
print(sorted_list)
|