w3resource

Python: Sort an odd–even sort or odd–even transposition sort

Python Search and Sorting : Exercise-35 with Solution

Write a Python program to sort an odd–even sort or odd–even transposition sort.

From Wikipedia:
In computing, an odd–even sort or odd–even transposition sort (also known as brick sort self-published source] or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for even/odd indexed pairs (of adjacent elements). Then it alternates between odd/even and even/odd steps until the list is sorted.

Sample Solution:

Python Code:

def odd_even_transposition(arr: list) -> list:
    arr_size = len(arr)
    for _ in range(arr_size):
        for i in range(_ % 2, arr_size - 1, 2):
            if arr[i + 1] < arr[i]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]

    return arr
            
nums = [4, 3, 5, 1, 2]
print("\nOriginal list:")
print(nums)
odd_even_transposition(nums)
print("Sorted order is:", nums)
nums = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(nums)
odd_even_transposition(nums)
print("Sorted order is:", nums)

Sample Output:

Original list:
[4, 3, 5, 1, 2]
Sorted order is: [1, 2, 3, 4, 5]

Original list:
[5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
Sorted order is: [-18, -4, 0, 3, 5, 5, 7, 9, 10, 46, 92, 178]

Flowchart:

Flowchart: Python Data Structures and Algorithms: Sort an odd–even sort or odd–even transposition sort.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort unsorted numbers using Patience sorting.
Next: Write a Python program to sort unsorted numbers using non-parallelized implementation of odd-even transposition sort.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://198.211.115.131/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-35.php