Write a C program for odd-even sort or brick sort. An Odd-Even Sort or brick sort is a simple sorting algorithm. In this algorithm we compare all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order the elements are switched. The next step repeats this for even/odd indexed pairs. Then it alternates between odd/even and even/odd steps until the list is sorted.

C program for odd-even sort or brick sort

#include<stdio.h>

#define false 0
#define true 1

void OddEvenSort(int *arr, int len) {
	int sort = false;

	while (!sort) {
		sort = true;
		int i;
		for (i = 1; i < len - 1; i += 2) {
			if (arr[i] <= arr[i + 1])
				continue;
			int temp = arr[i];
			arr[i] = arr[i + 1];
			arr[i + 1] = temp;
			sort = false;
		}
		for (i = 0; i < len - 1; i += 2) {
			if (arr[i] <= arr[i + 1])
				continue;
			int temp = arr[i];
			arr[i] = arr[i + 1];
			arr[i + 1] = temp;
			sort = false;
		}
	}
}

void print(int *arr, int len);

int main() {
	int arr[] = { 3, 6, 2, 5, 1, 8, 9 };
	int length = sizeof(arr) / sizeof(arr[0]);
	OddEvenSort(arr, length);
	printf("The arr 3,6,2,5,1,8,9 after sorting is \n");
	print(arr, length);
}

void print(int *arr, int len) {
	int i;
	for (i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
  • Save above program as oddeven.c
  • Compile using gcc and run to see output.
bosch@bosch-Inspiron-N5050:~$ gcc main.c 
bosch@bosch-Inspiron-N5050:~$ ./a.out 
The arr 3,6,2,5,1,8,9 after sorting is 
1 2 3 5 6 8 9 

complexity of above implementation

Auxiliary Space: O(n)
The best case Time Complexity: O(n) and in worst case it would be O(n²)

Wikipedia has given c++ implementation as below

 template <class T>
void OddEvenSort (T a[], int n)
{
    for (int i = 0 ; i < n ; i++)
    {
         if (i & 1) // 'i' is odd
         {
             for (int j = 2 ; j < n ; j += 2)
             {     
                  if (a[j] < a[j-1])
                      swap (a[j-1], a[j]) ;
             }
          }
          else
          {  
              for (int j = 1 ; j < n ; j += 2)
              {
                   if (a[j] < a[j-1])
                       swap (a[j-1], a[j]) ;
              } 
          }
    }
}

The odd-even sort or brick sort is just like bubble sort.

Note: It is our recommendation for readers that provide us any other good information.

Ref:

https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort



Related Contents to follow