Odd/Even or Brick Sort is a variation of Bubble Sort that compares adjacent elements in pairs, first the odd and even indexes, then the even and odd indexes until the list is sorted. In this article, we will discuss how Odd/Even Sort works, its implementation in Python, and its time and space complexity.
How Algorithm Works
The algorithm works by repeatedly comparing adjacent elements in pairs, first comparing the elements at odd and even positions, and then comparing the elements at even and odd positions, until the list is sorted. During each pass, if a pair of adjacent elements is not in the correct order, they are swapped. The process is repeated until the list is sorted.
The reason for comparing elements in odd/even pairs is that, during the first pass, the largest element is guaranteed to be at the end of the list, and during the second pass, the smallest element is guaranteed to be at the beginning of the list. By alternating between odd/even pairs, the algorithm takes advantage of this property, reducing the number of passes required to sort the list.
Algorithm Implementation
Here is the implementation of Odd/Even Sort in Python:
def odd_even_sort(arr):
n = len(arr)
sorted = False
while not sorted:
sorted = True
for i in range(1, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
sorted = False
for i in range(0, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
sorted = False
return arr
The above implementation takes an unsorted array as input and returns the sorted array using the Odd/Even Sort algorithm. The implementation uses a boolean variable sorted to keep track of whether the array is sorted. The while loop continues until the array is sorted, meaning no swaps were made during the last pass.
The implementation uses two for loops to compare adjacent elements in pairs. The first for loop compares elements at odd positions, and the second for loop compares elements at even positions. If a pair of adjacent elements is not in the correct order, they are swapped, and the sorted variable is set to False to indicate that the array is not yet sorted.
Time and Space Complexity
The time complexity of Odd/Even Sort is O(n^2), as each element in the array must be compared to every other element in the worst case. However, because Odd/Even Sort takes advantage of the properties of the data, it generally performs better than Bubble Sort on partially sorted lists. The space complexity of Odd/Even Sort is O(1), as the algorithm sorts the list in-place without requiring additional memory.
Example
Let’s run an example using the Odd/Even Sort algorithm:
arr = [5, 2, 1, 8, 4, 7, 10, 3]
print("Unsorted array:", arr)
sorted_arr = odd_even_sort(arr)
print("Sorted array:", sorted_arr)
The output of the above code is:
Unsorted array: [5, 2, 1, 8, 4, 7, 10, 3] Sorted array: [1, 2, 3, 4, 5, 7, 8, 10]
In the above example, we first create an unsorted array of integers. We then pass the unsorted array to the odd_even_sort function and store the sorted array in the variable sorted_arr. Finally, we print both the unsorted and sorted arrays to the console.
The output shows that the unsorted array is [5, 2, 1, 8, 4, 7, 10, 3], and the sorted array is [1, 2, 3, 4, 5, 7, 8, 10]. The Odd/Even Sort algorithm successfully sorted the array in ascending order.
Conclusion
In this article, we have discussed the Odd/Even or Brick Sort algorithm, its implementation in Python, and its time and space complexity. We have also provided an example of how the algorithm works on an unsorted array of integers. Odd/Even Sort is a simple sorting algorithm that can be useful for partially sorted lists, but it generally performs worse than other sorting algorithms, such as Quick Sort or Merge Sort, on unsorted lists. Nonetheless, it is still a valuable tool to have in your sorting algorithm toolbox.
