How to implement Brick Sort in Go

Brick Sort, also known as Odd-Even Sort, is a simple comparison-based sorting algorithm that can be used to arrange elements in a particular order. It's a variation of the Bubble Sort algorithm that sorts adjacent elements by comparing and swapping them in alternating passes, starting with even and odd indexed pairs. In this Answer, we will delve into the Brick Sort algorithm and provide a step-by-step guide on how to implement it in the Go programming language.

Understanding the Brick Sort algorithm

The key idea behind the Brick Sort algorithm is that it eliminates the need for multiple passes through the entire array in each iteration, which is typical in the Bubble Sort. Instead, it performs even and odd indexed passes separately, reducing the number of iterations needed to sort the array.

While Brick Sort is not the most efficient sorting algorithm for large datasets, it's simple to understand and implement, making it a good choice for educational purposes or scenarios where performance is not a critical concern.

Algorithm overview

The Brick Sort algorithm can be summarized in the following steps:

Perform alternating passes between even and odd indexed pairs.
Compare and swap adjacent elements in each pass if they are in the wrong order.
Repeat these passes until no swaps are required in the entire array.

package main
import (
	"fmt"
)
func brickSort(arr []int) {
	n := len(arr)
	swapped := true
	for swapped {
		swapped = false
		// Perform even indexed pass
		for i := 0; i < n-1; i += 2 {
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
				swapped = true
			}
		}
		// Perform odd indexed pass
		for i := 1; i < n-1; i += 2 {
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
				swapped = true
			}
		}
	}
}
func main() {
	arr := []int{64, 34, 25, 12, 22, 11, 90}
	fmt.Println("Original Array:", arr)
	brickSort(arr)
	fmt.Println("Sorted Array:", arr)
}

Brick Sort implementation

Code explanation

Inside the loop, there are two blocks of code:
- Line 11–20: The first block handles the even indexed pass. It uses a for loop that iterates through even indexed elements of the array (i += 2).
- Line 23–28: The second block handles the odd indexed pass. It uses a similar for loop but starts from an odd index.
Inside both the loops:
- Line 15–17: The if arr[i] > arr[i+1] {: This condition checks if the current element is greater than the next element.
- Line 17–19: The arr[i], arr[i+1] = arr[i+1], arr[i]: If the condition is met, this line swaps the elements at positions i and i+1.
Line 32–35: The arr := []int{64, 34, 25, 12, 22, 11, 90}: This initializes an integer slice named arr with the given values.
- fmt.Println("Original Array:", arr): This prints the original array.
- brickSort(arr): This calls the brickSort function to sort the array.
- fmt.Println("Sorted Array:", arr): This prints the sorted array.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to implement Brick Sort in Go

Understanding the Brick Sort algorithm

Algorithm overview

Implementing Brick Sort in Go

Code explanation