Python Program for Odd-Even Sort / Brick Sort

The Brick sort algorithm which is also known as odd/even sort performs bubble sort on the given array elements with two different phases of odd and even. In this tutorial, we are going to perform a Brick Sort algorithm to sort an array.

Brick Sort - Basic Introduction

We have two stages in this algorithm: Odd and Even Phases. Bubble sort is done on odd indexed elements during the odd phase, and on even indexed elements during the even phase. This algorithm is a variation of the bubble sort.

1. To create an ascending order list, it compares two adjacent integers and changes them if the first number is bigger than the second.
2. In the case of a descending order series, the opposite is true.
3. The odd-even transposition sort is divided into two phases: odd and even
4. Interchange numbers with their right-hand neighbouring number in both phases.
5. Follow the steps until the array is sorted.

Look at the diagram below for a better understanding:

Algorithm

As of now, we have a rough understanding of how the brick sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Define a function brick_sort()
2. Pass the parameter array, n
3. Initially declare an unsorted array
4. Create a loop for odd phase (brick sort = 1)
5. Create a loop for even phase (brick sort = 0)
6. Return the sorted array
7. Print the sorted array

Program for Brick Sort

As discussed above in the algorithm, let us now dive into the programming part of the brick sort operation influenced by the algorithm.

def brick_sort(array, a):
    # Unsorted array
    Sorted = 0
    while Sorted == 0:
        Sorted = 1
        temp = 0
        for i in range(1, a-1, 2):
            if array[i] > array[i+1]:
                array[i], array[i+1] = array[i+1], array[i]
                Sorted = 0
                  
        for i in range(0, a-1, 2):
            if array[i] > array[i+1]:
                array[i], array[i+1] = array[i+1], array[i]
                Sorted = 0
    return
  
#driver code
array = [5, 7, 3, 1, 4, 6, 2]
print("The original array is: ", array)
a = len(array)
  
brick_sort(array, a);
print("The sorted array is: " ,array)

The original array is: [5, 7, 3, 1, 4, 6, 2]
The sorted array is: [1, 2, 3, 4, 5, 6, 7]

Conclusion

In this tutorial, we have performed a brick sort operation in python to sort an array. It is a stable program having the time complexity of O(n) and the space complexity of the brick sort is O(1).