Skip to main content

Even Odd Sort

Given an array of integers, the goal is to sort the elements in such a way that even-indexed elements are sorted in ascending order, and odd-indexed elements are also sorted in ascending order. For example, given the array [2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0], after sorting using the Even-Odd Sort algorithm, the array becomes [-7, -3, 0, 1, 2, 2, 2, 4, 6, 8, 9, 12, 68].

Idea to Solve the Problem

The Even-Odd Sort algorithm repeatedly scans through the array and compares adjacent elements, swapping them if they are out of order. This process is performed separately for even and odd indexed elements. The algorithm continues these iterations until no swaps are needed, indicating that the array is sorted.

Pseudocode

even_odd_sort(arr, size):
    status = 0

    Do:
        status = 0
        
        For i = 1 to size - 1 with step 2:
            If arr[i-1] > arr[i]:
                Swap arr[i-1] and arr[i]
                Set status = 1
        
        For i = 2 to size - 1 with step 2:
            If arr[i-1] > arr[i]:
                Swap arr[i-1] and arr[i]
                Set status = 1
    
    While status == 1

display(arr, size):
    For i = 0 to size - 1:
        Print arr[i]

main():
    Initialize arr with input elements
    Get size of arr
    Print "Before Sort:"
    Call display(arr, size)
    Call even_odd_sort(arr, size)
    Print "After Sort:"
    Call display(arr, size)

Algorithm Explanation

  1. Create a function even_odd_sort(arr, size) to sort the array using the Even-Odd Sort algorithm.
  2. Initialize a variable status as 0 to indicate whether any swaps were made.
  3. Perform the following steps in a loop until status remains 0:
    • Iterate through even indexed elements and compare adjacent elements. Swap if necessary and set status to 1.
    • Iterate through odd indexed elements and apply the same swapping and status updating process.
  4. Create a function display(arr, size) to print the elements of the array.
  5. In the main function, initialize the array arr with input elements, get the size of the array, and call display to show the array before sorting.
  6. Call the even_odd_sort function to sort the array using the Even-Odd Sort algorithm.
  7. Finally, call display again to show the array after sorting.

Code Solution

//C Program
//Even Odd Sort 
#include <stdio.h>
#include <stdlib.h>
//Swap the array element
void swap(int arr[],int first,int second)
{
  //first and second are index of array
  int temp = arr[first];
  arr[first] = arr[second];
  arr[second] = temp;
}
void even_odd_sort(int arr[],int size)
{
  int status = 0;

  //This Loop executes until when array are not sort
  do
  {
    //This status 0 are indicate array are no need to sort
    status=0;

    for (int i = 1; i < size; i+=2)
    {
      if(arr[i-1]>arr[i])
      {
        //Change status
        status = 1;
        swap(arr,i,i-1);
      }
    }
    for (int i = 2; i < size; i+=2)
    {
      if(arr[i-1]>arr[i])
      {
        //Change status
        status = 1;
        swap(arr,i,i-1);
      }
    }
    //When status is modified to 1 then needed to iterate loop execution again

  }while(status==1);
 
}
//Display array elements
void display(int arr[], int size)
{
  for (int i = 0; i < size; ++i)
  {
    printf("  %d",arr[i] );
  }
  printf("\n");
}
int main()
{
 
  //Define array elements
  int arr[]= {2,8,-3,2,6,9,-7,2,1,4,12,68,0};
  //Get the size of array
  int size=sizeof(arr)/sizeof(arr[0]);
  printf("Before Sort : \n");
  display(arr,size);

  even_odd_sort(arr,size);
  printf("After Sort : \n");
  display(arr,size);

 
  return 0;
}

Output

Before Sort :
  2  8  -3  2  6  9  -7  2  1  4  12  68  0
After Sort :
  -7  -3  0  1  2  2  2  4  6  8  9  12  68
#include<iostream>

using namespace std;

/*
  C++ Program
  Even Odd Sort 
*/
class MySort {
	public:

	//Swap the array element
	void swap(int arr[], int first, int second) {
      //first and second are index of array
      int temp = arr[first];
      arr[first] = arr[second];
      arr[second] = temp;
    }
	void even_odd_sort(int arr[], int size) {
		int status = 0;
		//This Loop executes until when array are not sort

		do
		//When status is modified to 1 then needed to iterate loop execution again
		{
			//This status 0 are indicate array are no need to sort
			status = 0;
			for (int i = 1; i < size; i += 2) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = 1;
					this->swap(arr, i, i - 1);
				}
			}
			for (int i = 2; i < size; i += 2) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = 1;
					this->swap(arr, i, i - 1);
				}
			}
		} while (status == 1);
	}
	//Display array elements
	void display(int arr[], int size) {
		for (int i = 0; i < size; ++i) {
			cout << " " << arr[i];
		}
		cout << "\n";
	}
};
int main() {
	MySort obj ;
	int arr[] = {
		2,
		8,
		-3,
		2,
		6,
		9,
		-7,
		2,
		1,
		4,
		12,
		68,
		0
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "Before Sort : \n";
	obj.display(arr, size);
	obj.even_odd_sort(arr, size);
	cout << "After Sort : \n";
	obj.display(arr, size);
	return 0;
}

Output

Before Sort :
 2 8 -3 2 6 9 -7 2 1 4 12 68 0
After Sort :
 -7 -3 0 1 2 2 2 4 6 8 9 12 68
/*
  Java Program
  Even Odd Sort 
*/
public class MySort {

  //Swap the array element
  void swap(int []arr,int first,int second)
  {
    //first and second are index of array
    int temp = arr[first];
    arr[first] = arr[second];
    arr[second] = temp;
  }
  void even_odd_sort(int []arr,int size)
  {
    int status = 0;

    //This Loop executes until when array are not sort
    do
    {
      //This status 0 are indicate array are no need to sort
      status=0;

      for (int i = 1; i < size; i+=2)
      {
        if(arr[i-1]>arr[i])
        {
          //Change status
          status = 1;
          swap(arr,i,i-1);
        }
      }
      for (int i = 2; i < size; i+=2)
      {
        if(arr[i-1]>arr[i])
        {
          //Change status
          status = 1;
          swap(arr,i,i-1);
        }
      }
      //When status is modified to 1 then needed to iterate loop execution again

    }while(status==1);
   
  }
  //Display array elements
  void display(int []arr, int size)
  {
    for (int i = 0; i < size; ++i)
    {
      System.out.print("  "+arr[i] );
    }
    System.out.print("\n");
  }
  public static void main(String[] args) 
  {
  

    MySort obj = new MySort();
    //Define array elements
    int []arr= {2,8,-3,2,6,9,-7,2,1,4,12,68,0};
    //Get the size of array
    int size = arr.length;
    System.out.print("Before Sort : \n");
    obj.display(arr,size);

    obj.even_odd_sort(arr,size);
    System.out.print("After Sort : \n");
    obj.display(arr,size);

  }
}

Output

Before Sort : 
  2  8  -3  2  6  9  -7  2  1  4  12  68  0
After Sort : 
  -7  -3  0  1  2  2  2  4  6  8  9  12  68
/*
  C# Program
  Even Odd Sort 
*/
using System;
public class MySort {
	//Swap the array element
	void swap(int[] arr, int first, int second) {
		//first and second are index of array
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	void even_odd_sort(int[] arr, int size) {
		int status = 0;
		//This Loop executes until when array are not sort

		do
		//When status is modified to 1 then needed to iterate loop execution again
		{
			//This status 0 are indicate array are no need to sort
			status = 0;
			for (int i = 1; i < size; i += 2) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = 1;
					swap(arr, i, i - 1);
				}
			}
			for (int i = 2; i < size; i += 2) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = 1;
					swap(arr, i, i - 1);
				}
			}
		} while (status == 1);
	}
	//Display array elements
	void display(int[] arr, int size) {
		for (int i = 0; i < size; ++i) {
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public static void Main(String[] args) {
		MySort obj = new MySort();
		int[]
		//Define array elements
		arr = {
			2,
			8,
			-3,
			2,
			6,
			9,
			-7,
			2,
			1,
			4,
			12,
			68,
			0
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("Before Sort : \n");
		obj.display(arr, size);
		obj.even_odd_sort(arr, size);
		Console.Write("After Sort : \n");
		obj.display(arr, size);
	}
}

Output

Before Sort :
 2 8 -3 2 6 9 -7 2 1 4 12 68 0
After Sort :
 -7 -3 0 1 2 2 2 4 6 8 9 12 68
<?php
/*
  Php Program
  Even Odd Sort 
*/
class MySort {
	//Swap the array element
	function swap(&$arr, $first, $second) {
		//first and second are index of array
		$temp = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $temp;
	}

	function even_odd_sort(&$arr, $size) {
		$status = 0;
		//This Loop executes until when array are not sort

		do
		//When status is modified to 1 then needed to iterate loop execution again
		{
			//This status 0 are indicate array are no need to sort
			$status = 0;
			for ($i = 1; $i < $size; $i += 2) {
				if ($arr[$i - 1] > $arr[$i]) {
					//Change status
					$status = 1;
					$this->swap($arr, $i, $i - 1);
				}
			}
			for ($i = 2; $i < $size; $i += 2) {
				if ($arr[$i - 1] > $arr[$i]) {
					//Change status
					$status = 1;
					$this->swap($arr, $i, $i - 1);
				}
			}
		} while ($status == 1);
	}
	//Display array elements
	function display($arr, $size) {
		for ($i = 0; $i < $size; ++$i) {
			echo(" ". $arr[$i]);
		}
		echo("\n");
	}
};

function main() {
	$obj = new MySort();
	//Define array elements
	$arr = array(2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0);
	//Get the size of array
	$size = count($arr);
	echo("Before Sort : \n");
	$obj->display($arr, $size);
	$obj->even_odd_sort($arr, $size);
	echo("After Sort : \n");
	$obj->display($arr, $size);

}
main();

Output

Before Sort :
 2 8 -3 2 6 9 -7 2 1 4 12 68 0
After Sort :
 -7 -3 0 1 2 2 2 4 6 8 9 12 68
/*
  Node Js Program
  Even Odd Sort 
*/
class MySort {
	//Swap the array element
	swap(arr, first, second) {
		//first and second are index of array
		var temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	even_odd_sort(arr, size) {
		var status = 0;
		//This Loop executes until when array are not sort

		do
		//When status is modified to 1 then needed to iterate loop execution again
		{
			//This status 0 are indicate array are no need to sort
			status = 0;
			for (var i = 1; i < size; i += 2) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = 1;
					this.swap(arr, i, i - 1);
				}
			}

			for (var i = 2; i < size; i += 2) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = 1;
					this.swap(arr, i, i - 1);
				}
			}
		}
		while (status == 1);
	}

	//Display array elements
	display(arr, size) {
		for (var i = 0; i < size; ++i) {
			process.stdout.write(" " + arr[i]);
		}

		process.stdout.write("\n");
	}
}

function main(args) {
	var obj = new MySort();
	//Define array elements
	var arr = [2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("Before Sort : \n");
	obj.display(arr, size);
	obj.even_odd_sort(arr, size);
	process.stdout.write("After Sort : \n");
	obj.display(arr, size);
}

main();

Output

Before Sort :
 2 8 -3 2 6 9 -7 2 1 4 12 68 0
After Sort :
 -7 -3 0 1 2 2 2 4 6 8 9 12 68
# Python 3 Program
# Even Odd Sort 
class MySort :
	def swap(self, arr, first, second) :
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	
	def even_odd_sort(self, arr, size) :
		# When status is modified to true then needed to iterate loop execution again
		status = True
		# This Loop executes until when array are not sort
		while (status == True) :
			# This status false are indicate array are no need to sort
			status = False
			i = 1
			while (i < size) :
				if (arr[i - 1] > arr[i]) :
					# Change status
					status = True
					self.swap(arr, i, i - 1)
				
				i += 2
			
			i = 2
			while (i < size) :
				if (arr[i - 1] > arr[i]) :
					# Change status
					status = True
					self.swap(arr, i, i - 1)
				
				i += 2
			
		
	
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MySort()
	arr = [2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0]
	size = len(arr)
	print("Before Sort : \n", end = "")
	obj.display(arr, size)
	obj.even_odd_sort(arr, size)
	print("After Sort : \n", end = "")
	obj.display(arr, size)


if __name__ == "__main__":
	main()

Output

Before Sort :
  2  8  -3  2  6  9  -7  2  1  4  12  68  0
After Sort :
  -7  -3  0  1  2  2  2  4  6  8  9  12  68
#   Ruby Program
#   Even Odd Sort 
class MySort 
	def swap(arr, first, second) 
		temp = arr[first]
		arr[first] = arr[second]
		arr[second] = temp
	end
	def even_odd_sort(arr, size) 
		# When status is modified to true then needed to iterate loop execution again
		status = true
		# This Loop executes until when array are not sort
		while (status == true) 
			# This status false are indicate array are no need to sort
			status = false
			i = 1
			while (i < size) 
				if (arr[i - 1] > arr[i]) 
					# Change status
					status = true
					self.swap(arr, i, i - 1)
				end
				i += 2
			end
			i = 2
			while (i < size) 
				if (arr[i - 1] > arr[i]) 
					# Change status
					status = true
					self.swap(arr, i, i - 1)
				end
				i += 2
			end
		end
	end
	def display(arr, size) 
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
end
def main() 
	obj = MySort.new()
	arr = [2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0]
	size = arr.length
	print("Before Sort  :\n")
	obj.display(arr, size)
	obj.even_odd_sort(arr, size)
	print("After Sort  :\n")
	obj.display(arr, size)
end
main()

Output

Before Sort  :
 2 8 -3 2 6 9 -7 2 1 4 12 68 0
After Sort  :
 -7 -3 0 1 2 2 2 4 6 8 9 12 68
/*
  Scala Program
  Even Odd Sort 
*/
class MySort {
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		val temp: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = temp;
	}
	def even_odd_sort(arr: Array[Int], size: Int): Unit = {
		//When status is modified to true then needed to iterate loop execution again
		var status: Boolean = true;

		//This Loop executes until when array are not sort
		while (status == true) {
			//This status false are indicate array are no need to sort
			status = false;
			var i: Int = 1;
			while (i < size) {
				if (arr(i - 1) > arr(i)) {
					//Change status
					status = true;
					this.swap(arr, i, i - 1);
				}
				i += 2;
			}
			i = 2;
			while (i < size) {
				if (arr(i - 1) > arr(i)) {
					//Change status
					status = true;
					this.swap(arr, i, i - 1);
				}
				i += 2;
			}
		}
	}
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size) {
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MySort = new MySort();
		var arr: Array[Int] = Array(2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0);
		val size: Int = arr.length;
		print("Before Sort : \n");
		obj.display(arr, size);
		obj.even_odd_sort(arr, size);
		print("After Sort : \n");
		obj.display(arr, size);
	}
}

Output

Before Sort :
 2 8 -3 2 6 9 -7 2 1 4 12 68 0
After Sort :
 -7 -3 0 1 2 2 2 4 6 8 9 12 68
/*
  Swift Program
  Even Odd Sort 
*/
class MySort {
	func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
		let temp: Int = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
	func even_odd_sort(_ arr: inout [Int], _ size: Int) {
		//When status is modified to true then needed to iterate loop execution again
		var status: Bool = true;
		//This Loop executes until when array are not sort
		while (status == true) {
			//This status false are indicate array are no need to sort
			status = false;
			var i: Int = 1;
			while (i < size) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = true;
					self.swap(&arr, i, i - 1);
				}
				i += 2;
			}
			i = 2;
			while (i < size) {
				if (arr[i - 1] > arr[i]) {
					//Change status
					status = true;
					self.swap(&arr, i, i - 1);
				}
				i += 2;
			}
		}
	}
	func display(_ arr: [Int], _ size: Int) {
		var i: Int = 0;
		while (i < size) {
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
}
func main() {
	let obj: MySort = MySort();
	var arr: [Int] = [2, 8, -3, 2, 6, 9, -7, 2, 1, 4, 12, 68, 0];
	let size: Int = arr.count;
	print("Before Sort : \n", terminator: "");
	obj.display(arr, size);
	obj.even_odd_sort(&arr, size);
	print("After Sort : \n", terminator: "");
	obj.display(arr, size);
}
main();

Output

Before Sort :
  2  8  -3  2  6  9  -7  2  1  4  12  68  0
After Sort :
  -7  -3  0  1  2  2  2  4  6  8  9  12  68

Time Complexity Analysis

The Even-Odd Sort algorithm iterates through the array multiple times, scanning and swapping elements when necessary. The number of iterations depends on the number of swaps required in each pass. In the worst case, the algorithm will have a time complexity of O(n^2), where n is the size of the array. The space complexity is O(1) as the algorithm uses only a constant amount of extra space.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment