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
- Create a function
even_odd_sort(arr, size)to sort the array using the Even-Odd Sort algorithm. - Initialize a variable
statusas 0 to indicate whether any swaps were made. - Perform the following steps in a loop until
statusremains 0:- Iterate through even indexed elements and compare adjacent elements. Swap if necessary and set
statusto 1. - Iterate through odd indexed elements and apply the same swapping and status updating process.
- Iterate through even indexed elements and compare adjacent elements. Swap if necessary and set
- Create a function
display(arr, size)to print the elements of the array. - In the
mainfunction, initialize the arrayarrwith input elements, get the size of the array, and calldisplayto show the array before sorting. - Call the
even_odd_sortfunction to sort the array using the Even-Odd Sort algorithm. - Finally, call
displayagain 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 68Time 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.
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