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)
{
Sorting task = new Sorting();
// 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");
task.display(s1, size);
System.out.print(" After Sort \n");
task.bubbleSort(s1, size);
task.display(s1, size);
// Test case B
size = s2.length;
System.out.print("\n Before Sort \n");
task.display(s2, size);
task.bubbleSort(s2, size);
System.out.print(" After Sort \n");
task.display(s2, size);
}
}
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()
{
Sorting task = Sorting();
// 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";
task.display(s1, size);
cout << " After Sort \n";
task.bubbleSort(s1, size);
task.display(s1, size);
// Test case B
size = sizeof(s2) / sizeof(s2[0]);
cout << "\n Before Sort \n";
task.display(s2, size);
task.bubbleSort(s2, size);
cout << " After Sort \n";
task.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
// 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)
{
Sorting task = new Sorting();
// 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");
task.display(s1, size);
Console.Write(" After Sort \n");
task.bubbleSort(s1, size);
task.display(s1, size);
// Test case B
size = s2.Length;
Console.Write("\n Before Sort \n");
task.display(s2, size);
task.bubbleSort(s2, size);
Console.Write(" After Sort \n");
task.display(s2, size);
}
}
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()
{
$task = new Sorting();
// 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";
$task->display($s1, $size);
echo " After Sort \n";
$task->bubbleSort($s1, $size);
$task->display($s1, $size);
// Test case B
$size = count($s2);
echo "\n Before Sort \n";
$task->display($s2, $size);
$task->bubbleSort($s2, $size);
echo " After Sort \n";
$task->display($s2, $size);
}
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()
{
var task = new Sorting();
// 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");
task.display(s1, size);
process.stdout.write(" After Sort \n");
task.bubbleSort(s1, size);
task.display(s1, size);
// Test case B
size = s2.length;
process.stdout.write("\n Before Sort \n");
task.display(s2, size);
task.bubbleSort(s2, size);
process.stdout.write(" After Sort \n");
task.display(s2, size);
}
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() :
task = Sorting()
# 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 ")
task.display(s1, size)
print(" After Sort ")
task.bubbleSort(s1, size)
task.display(s1, size)
# Test case B
size = len(s2)
print("\n Before Sort ")
task.display(s2, size)
task.bubbleSort(s2, size)
print(" After Sort ")
task.display(s2, size)
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()
task = Sorting.new()
# 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")
task.display(s1, size)
print(" After Sort \n")
task.bubbleSort(s1, size)
task.display(s1, size)
# Test case B
size = s2.length
print("\n Before Sort \n")
task.display(s2, size)
task.bubbleSort(s2, size)
print(" After Sort \n")
task.display(s2, size)
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");
task.display(s1, size);
print(" After Sort \n");
task.bubbleSort(s1, size);
task.display(s1, size);
// Test case B
size = s2.length;
print("\n Before Sort \n");
task.display(s2, size);
task.bubbleSort(s2, size);
print(" After Sort \n");
task.display(s2, size);
}
}
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()
{
let task: Sorting = Sorting();
// 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 ");
task.display(s1, size);
print(" After Sort ");
task.bubbleSort(&s1, size);
task.display(s1, size);
// Test case B
size = s2.count;
print("\n Before Sort ");
task.display(s2, size);
task.bubbleSort(&s2, size);
print(" After Sort ");
task.display(s2, size);
}
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
{
var task: Sorting = Sorting();
// 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");
task.display(s1, size);
print(" After Sort \n");
task.bubbleSort(s1, size);
task.display(s1, size);
// Test case B
size = s2.count();
print("\n Before Sort \n");
task.display(s2, size);
task.bubbleSort(s2, size);
print(" After Sort \n");
task.display(s2, size);
}
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
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