# Bidirectional bubble sort

Bidirectional bubble sort, also known as cocktail sort, shaker sort or cocktail shaker sort, is a variation of the bubble sort algorithm that works by repeatedly iterating through a list of elements in both directions, swapping adjacent elements that are in the wrong order.

The algorithm starts by comparing adjacent elements in the list from left to right, and swaps them if they are in the wrong order. Then, it compares adjacent elements from right to left, and swaps them if they are in the wrong order. This process is repeated until the list is fully sorted.

The main advantage of the bidirectional bubble sort over the traditional bubble sort is that it can sort a list in both directions, which means it can handle certain types of input that might cause traditional bubble sort to perform poorly, such as lists that are mostly sorted but have a few unsorted elements in the middle.

However, the worst-case time complexity of the bidirectional bubble sort algorithm is still O(n^2), just like the traditional bubble sort, which means that it can become very slow for large input sizes. Therefore, it is not commonly used in practical applications, and more efficient sorting algorithms like quicksort or merge sort are preferred.

Here given code implementation process.

``````// C Program
// Bidirectional bubble sort
#include <stdio.h>

//Display elements of given sequence
void display(int sequence[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d", sequence[i]);
}
printf("\n");
}
// Swap array elements by given location
void swap(int sequence[], int a, int b)
{
int temp = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
void bubbleSort(int sequence[], int size)
{
// Get first location of sequence
int left = 0;
// Get the last location of sequence
int right = size - 1;
int position = 0;
while (left < right)
{
for (position = left; position < right; ++position)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
swap(sequence, position, position + 1);
}
}
// Reduce higher position
right--;
for (position = right; position > left; --position)
{
if (sequence[position] < sequence[position - 1])
{
swap(sequence, position, position - 1);
}
}
// Increase lower position
left++;
}
}
int main()
{
// Given input arrays
int s1[] = {
6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 2 , 9
};
int s2[] = {
7 , 2 , 5 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
};
// Test case A
int size = sizeof(s1) / sizeof(s1[0]);
printf(" Before Sort \n");
display(s1, size);
printf(" After Sort\n");
bubbleSort(s1, size);
display(s1, size);
// Test case B
size = sizeof(s2) / sizeof(s2[0]);
printf("\n Before Sort \n");
display(s2, size);
bubbleSort(s2, size);
printf(" After Sort \n");
display(s2, size);
return 0;
}``````

#### Output

`````` Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````/*
Java program
Bidirectional bubble sort
*/
public class Sorting
{
// Display elements of given sequence
public void display(int[] sequence, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  " + sequence[i] );
}
System.out.print("\n");
}
// Swap array elements by given location
public void swap(int[] sequence, int a, int b)
{
int temp = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
public void bubbleSort(int[] sequence, int size)
{
// Get first location of sequence
int left = 0;
// Get the last location of sequence
int right = size - 1;
int position = 0;
while (left < right)
{
for (position = left; position < right; ++position)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
swap(sequence, position, position + 1);
}
}
// Reduce higher position
right--;
for (position = right; position > left; --position)
{
if (sequence[position] < sequence[position - 1])
{
swap(sequence, position, position - 1);
}
}
// Increase lower position
left++;
}
}
public static void main(String[] args)
{
// Define array of positive integer elements
int[] s1 = {
6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 2 , 9
};
int[] s2 = {
7 , 2 , 5 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
};
// Test case A
int size = s1.length;
System.out.print("  Before Sort  \n");
System.out.print("  After Sort  \n");
// Test case B
size = s2.length;
System.out.print("\n Before Sort  \n");
System.out.print("  After Sort \n");
}
}``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Bidirectional bubble sort
*/

class Sorting
{
public:
// Display elements of given sequence
void display(int sequence[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "  " << sequence[i];
}
cout << "\n";
}
// Swap array elements by given location
void swap(int sequence[], int a, int b)
{
int temp = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
void bubbleSort(int sequence[], int size)
{
// Get first location of sequence
int left = 0;
// Get the last location of sequence
int right = size - 1;
int position = 0;
while (left < right)
{
// Set higher value
for (position = left; position < right; ++position)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
this->swap(sequence, position, position + 1);
}
}
// Reduce higher position
right--;
// Set lower value
for (position = right; position > left; --position)
{
if (sequence[position] < sequence[position - 1])
{
this->swap(sequence, position, position - 1);
}
}
// Increase lower position
left++;
}
}
};
int main()
{
// Define array of positive integer elements
int s1[] = {
6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 2 , 9
};
int s2[] = {
7 , 2 , 5 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
};
// Test case A
int size = sizeof(s1) / sizeof(s1[0]);
cout << "  Before Sort  \n";
cout << "  After Sort  \n";
// Test case B
size = sizeof(s2) / sizeof(s2[0]);
cout << "\n Before Sort  \n";
cout << "  After Sort \n";
return 0;
}``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````// Include namespace system
using System;
/*
C# program
Bidirectional bubble sort
*/
public class Sorting
{
// Display elements of given sequence
public void display(int[] sequence, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write("  " + sequence[i]);
}
Console.Write("\n");
}
// Swap array elements by given location
public void swap(int[] sequence, int a, int b)
{
int temp = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
public void bubbleSort(int[] sequence, int size)
{
// Get first location of sequence
int left = 0;
// Get the last location of sequence
int right = size - 1;
int position = 0;
while (left < right)
{
// Set higher value
for (position = left; position < right; ++position)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
swap(sequence, position, position + 1);
}
}
// Reduce higher position
right--;
// Set lower value
for (position = right; position > left; --position)
{
if (sequence[position] < sequence[position - 1])
{
swap(sequence, position, position - 1);
}
}
// Increase lower position
left++;
}
}
public static void Main(String[] args)
{
// Define array of positive integer elements
int[] s1 = {
6 , 2 , 8 , 5 , 2 , 4 , 1 , 17 , 21 , 12 , 1 , 2 , 9
};
int[] s2 = {
7 , 2 , 5 , 0 , 9 , 1 , 0 , 3 , 6 , 2 , 7 , 3 , 1
};
// Test case A
int size = s1.Length;
Console.Write("  Before Sort  \n");
Console.Write("  After Sort  \n");
// Test case B
size = s2.Length;
Console.Write("\n Before Sort  \n");
Console.Write("  After Sort \n");
}
}``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````<?php
/*
Php program
Bidirectional bubble sort
*/
class Sorting
{
// Display elements of given sequence
public	function display( & \$sequence, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$sequence[\$i];
}
echo "\n";
}
// Swap array elements by given location
public	function swap( & \$sequence, \$a, \$b)
{
\$temp = \$sequence[\$a];
\$sequence[\$a] = \$sequence[\$b];
\$sequence[\$b] = \$temp;
}
// Implementation of bidirectional bubble sort
public	function bubbleSort( & \$sequence, \$size)
{
// Get first location of sequence
\$left = 0;
// Get the last location of sequence
\$right = \$size - 1;
\$position = 0;
while (\$left < \$right)
{
// Set higher value
for (\$position = \$left; \$position < \$right; ++\$position)
{
if (\$sequence[\$position] > \$sequence[\$position + 1])
{
//Swap element
\$this->swap(\$sequence, \$position, \$position + 1);
}
}
// Reduce higher position
\$right--;
// Set lower value
for (\$position = \$right; \$position > \$left; --\$position)
{
if (\$sequence[\$position] < \$sequence[\$position - 1])
{
\$this->swap(\$sequence, \$position, \$position - 1);
}
}
// Increase lower position
\$left++;
}
}
}

function main()
{
// Define array of positive integer elements
\$s1 = array(6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9);
\$s2 = array(7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1);
// Test case A
\$size = count(\$s1);
echo "  Before Sort  \n";
echo "  After Sort  \n";
// Test case B
\$size = count(\$s2);
echo "\n Before Sort  \n";
echo "  After Sort \n";
}
main();``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````/*
Node Js program
Bidirectional bubble sort
*/
class Sorting
{
// Display elements of given sequence
display(sequence, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + sequence[i]);
}
process.stdout.write("\n");
}
// Swap array elements by given location
swap(sequence, a, b)
{
var temp = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
bubbleSort(sequence, size)
{
// Get first location of sequence
var left = 0;
// Get the last location of sequence
var right = size - 1;
var position = 0;
while (left < right)
{
// Set higher value
for (position = left; position < right; ++position)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
this.swap(sequence, position, position + 1);
}
}
// Reduce higher position
right--;
// Set lower value
for (position = right; position > left; --position)
{
if (sequence[position] < sequence[position - 1])
{
this.swap(sequence, position, position - 1);
}
}
// Increase lower position
left++;
}
}
}

function main()
{
// Define array of positive integer elements
var s1 = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9];
var s2 = [7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1];
// Test case A
var size = s1.length;
process.stdout.write("  Before Sort  \n");
process.stdout.write("  After Sort  \n");
// Test case B
size = s2.length;
process.stdout.write("\n Before Sort  \n");
process.stdout.write("  After Sort \n");
}
main();``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````#   Python 3 program
#   Bidirectional bubble sort

class Sorting :
#  Display elements of given sequence
def display(self, sequence, size) :
i = 0
while (i < size) :
print("  ", sequence[i], end = "")
i += 1

print(end = "\n")

#  Swap array elements by given location
def swap(self, sequence, a, b) :
temp = sequence[a]
sequence[a] = sequence[b]
sequence[b] = temp

#  Implementation of bidirectional bubble sort
def bubbleSort(self, sequence, size) :
#  Get first location of sequence
left = 0
#  Get the last location of sequence
right = size - 1
position = 0
while (left < right) :
#  Set higher value
position = left
while (position < right) :
if (sequence[position] > sequence[position + 1]) :
# Swap element
self.swap(sequence, position, position + 1)

position += 1

#  Reduce higher position
right -= 1
#  Set lower value
position = right
while (position > left) :
if (sequence[position] < sequence[position - 1]) :
self.swap(sequence, position, position - 1)

position -= 1

#  Increase lower position
left += 1

def main() :
#  Define array of positive integer elements
s1 = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9]
s2 = [7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1]
#  Test case A
size = len(s1)
print("  Before Sort  ")
print("  After Sort  ")
#  Test case B
size = len(s2)
print("\n Before Sort  ")
print("  After Sort ")

if __name__ == "__main__": main()``````

#### Output

``````  Before Sort
6   2   8   5   2   4   1   17   21   12   1   2   9
After Sort
1   1   2   2   2   4   5   6   8   9   12   17   21

Before Sort
7   2   5   0   9   1   0   3   6   2   7   3   1
After Sort
0   0   1   1   2   2   3   3   5   6   7   7   9``````
``````#   Ruby program
#   Bidirectional bubble sort

class Sorting
#  Display elements of given sequence
def display(sequence, size)
i = 0
while (i < size)
print("  ", sequence[i])
i += 1
end

print("\n")
end

#  Swap array elements by given location
def swap(sequence, a, b)
temp = sequence[a]
sequence[a] = sequence[b]
sequence[b] = temp
end

#  Implementation of bidirectional bubble sort
def bubbleSort(sequence, size)
#  Get first location of sequence
left = 0
#  Get the last location of sequence
right = size - 1
position = 0
while (left < right)
#  Set higher value
position = left
while (position < right)
if (sequence[position] > sequence[position + 1])
# Swap element
self.swap(sequence, position, position + 1)
end

position += 1
end

#  Reduce higher position
right -= 1
#  Set lower value
position = right
while (position > left)
if (sequence[position] < sequence[position - 1])
self.swap(sequence, position, position - 1)
end

position -= 1
end

#  Increase lower position
left += 1
end

end

end

def main()
#  Define array of positive integer elements
s1 = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9]
s2 = [7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1]
#  Test case A
size = s1.length
print("  Before Sort  \n")
print("  After Sort  \n")
#  Test case B
size = s2.length
print("\n Before Sort  \n")
print("  After Sort \n")
end

main()``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9
``````
``````/*
Scala program
Bidirectional bubble sort
*/
class Sorting
{
// Display elements of given sequence
def display(sequence: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + sequence(i));
i += 1;
}
print("\n");
}
// Swap array elements by given location
def swap(sequence: Array[Int], a: Int, b: Int): Unit = {
var temp: Int = sequence(a);
sequence(a) = sequence(b);
sequence(b) = temp;
}
// Implementation of bidirectional bubble sort
def bubbleSort(sequence: Array[Int], size: Int): Unit = {
// Get first location of sequence
var left: Int = 0;
// Get the last location of sequence
var right: Int = size - 1;
var position: Int = 0;
while (left < right)
{
// Set higher value
position = left;
while (position < right)
{
if (sequence(position) > sequence(position + 1))
{
//Swap element
this.swap(sequence, position, position + 1);
}
position += 1;
}
// Reduce higher position
right -= 1;
// Set lower value
position = right;
while (position > left)
{
if (sequence(position) < sequence(position - 1))
{
this.swap(sequence, position, position - 1);
}
position -= 1;
}
// Increase lower position
left += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sorting = new Sorting();
// Define array of positive integer elements
var s1: Array[Int] = Array(6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9);
var s2: Array[Int] = Array(7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1);
// Test case A
var size: Int = s1.length;
print("  Before Sort  \n");
print("  After Sort  \n");
// Test case B
size = s2.length;
print("\n Before Sort  \n");
print("  After Sort \n");
}
}``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````
``````/*
Swift 4 program
Bidirectional bubble sort
*/
class Sorting
{
// Display elements of given sequence
func display(_ sequence: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", sequence[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Swap array elements by given location
func swap(_ sequence: inout[Int], _ a: Int, _ b: Int)
{
let temp: Int = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
func bubbleSort(_ sequence: inout[Int], _ size: Int)
{
// Get first location of sequence
var left: Int = 0;
// Get the last location of sequence
var right: Int = size - 1;
var position: Int = 0;
while (left < right)
{
// Set higher value
position = left;
while (position < right)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
self.swap(&sequence, position, position + 1);
}
position += 1;
}
// Reduce higher position
right -= 1;
// Set lower value
position = right;
while (position > left)
{
if (sequence[position] < sequence[position - 1])
{
self.swap(&sequence, position, position - 1);
}
position -= 1;
}
// Increase lower position
left += 1;
}
}
}
func main()
{
// Define array of positive integer elements
var s1: [Int] = [6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9];
var s2: [Int] = [7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1];
// Test case A
var size: Int = s1.count;
print("  Before Sort  ");
print("  After Sort  ");
// Test case B
size = s2.count;
print("\n Before Sort  ");
print("  After Sort ");
}
main();``````

#### Output

``````  Before Sort
6   2   8   5   2   4   1   17   21   12   1   2   9
After Sort
1   1   2   2   2   4   5   6   8   9   12   17   21

Before Sort
7   2   5   0   9   1   0   3   6   2   7   3   1
After Sort
0   0   1   1   2   2   3   3   5   6   7   7   9``````
``````/*
Kotlin program
Bidirectional bubble sort
*/
class Sorting
{
// Display elements of given sequence
fun display(sequence: Array<Int>, size: Int): Unit
{
var i: Int = 0;
while (i<size)
{
print("  " + sequence[i]);
i += 1;
}
print("\n");
}
// Swap array elements by given location
fun swap(sequence: Array<Int>, a: Int, b: Int): Unit
{
var temp: Int = sequence[a];
sequence[a] = sequence[b];
sequence[b] = temp;
}
// Implementation of bidirectional bubble sort
fun bubbleSort(sequence: Array<Int>, size: Int): Unit
{
// Get first location of sequence
var left: Int = 0;
// Get the last location of sequence
var right: Int = size - 1;
var position: Int ;
while (left < right)
{
// Set higher value
position = left;
while (position < right)
{
if (sequence[position] > sequence[position + 1])
{
//Swap element
this.swap(sequence, position, position + 1);
}
position += 1;
}
// Reduce higher position
right -= 1;
// Set lower value
position = right;
while (position > left)
{
if (sequence[position]<sequence[position - 1])
{
this.swap(sequence, position, position - 1);
}
position -= 1;
}
// Increase lower position
left += 1;
}
}
}
fun main(args: Array<String>): Unit
{
// Define array of positive integer elements
var s1: Array<Int>  = arrayOf(6, 2, 8, 5, 2, 4, 1, 17, 21, 12, 1, 2, 9);
var s2: Array<Int>  = arrayOf(7, 2, 5, 0, 9, 1, 0, 3, 6, 2, 7, 3, 1);
// Test case A
var size: Int = s1.count();
print("  Before Sort  \n");
print("  After Sort  \n");
// Test case B
size = s2.count();
print("\n Before Sort  \n");
print("  After Sort \n");
}``````

#### Output

``````  Before Sort
6  2  8  5  2  4  1  17  21  12  1  2  9
After Sort
1  1  2  2  2  4  5  6  8  9  12  17  21

Before Sort
7  2  5  0  9  1  0  3  6  2  7  3  1
After Sort
0  0  1  1  2  2  3  3  5  6  7  7  9``````

## 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.