FOR FREE MATERIALS

The bitonic sort is a comparison based sorting technique in which the array is sorted by using a different type of sequence called the bitonic sequence. The bitonic sequence of an array is the sequence of elements where the elements are increasing up to a certain element and then the value will be decreasing till end. For example, an array with n elements will be called in a bitonic sequence if:

PROCEDURE WITH EXAMPLE:

Suppose there is an array of 8 elements as follows:

The array should be sorted in ascending order. 

Step 1: 

In the first step, two consecutive elements are compared and a bitonic sequence is formed for the first 4 elements, then the next four elements, and so on as the following:

The first two elements will be compared; as they are already in increasing order so there will be no change. 

Now, the second two elements will be checked, they should be sorted in decreasing order. As here they will not be in decreasing order so they will be swapped.

For the next pair of elements, it should be again in increasing order. As they are not incorrect orders they will be swapped. Similarly, for the last pair, it should be in descending order. As they are already in descending order so there will be no swapping. After this step, we get two 4 elements bitonic sequence.

Step 2: 

Now, in the 2nd step the elements will be compared at gap 2 to form 8 elements bitonic sequence as follows:

Now, firstly the 4 and 8 will be compared, as they are in ascending order so there will not be swapped.

Next 7 and -9 will be compared, as they are not in ascending order, they will be swapped. 

Next 5 and 3 will be compared, they are already in descending order, there will not be swapping.

Then 12 and -2 will be compared next, they are also in descending order so there will also not be swapping.

Step 3: 

In this step, again the adjacent pairs of elements will be compared. But unlike step 1, the first two pair will be arranged in ascending order; the next two pairs will be arranged in descending order.

Now, 4 and -9 will be compared and will be arranged in ascending order, so, it will be swapped.

8 and 7 will be compared and again will be arranged in ascending order, so, it will be swapped.

For the next half, 5 and 12 will be compared and will be arranged in descending order. So, it will be swapped.

Similarly, 3 and -2 will be compared but as they are already in descending order, so there will be no change.

After this sequence, we get the full array arranged in a bitonic sequence.

Step 4: 

In this step, the elements at gap 4 will be compared and will be arranged in ascending order as follows:

The first element(-9) will be compared with the 5th element (12), as they are already in sorted order, they will not be swapped. 

Next 4 and 5 will be compared, so, no swapping required.

Now 7 will be compared with 3, they will be swapped.

Lastly, 8 and -2 will be compared and will be swapped.

Step 5: 

In this step again the elements at gap 2 will be compared and to arrange in ascending order as follows:

First -9 is compared with 3, they are already in ascending order so there will be no swapping.

Next 4 and -2 will be compared and they will be swapped to arrange in the correct order. 

Next, 12 and 7 will be compared and will be swapped and arranged in ascending order.

Similarly, 5 and 8 will be compared but there will be no change as they are already in the correct sequence.

Step 6: 

This is the last step of this sorting in which again the adjacent elements will be compared and arranged in ascending order.

First -9 and -2 will be compared, as they are in sorted order, no swapping required.

Next 3 and 4 will be compared, they are also in sorted order, no swapping required.

Then 7 and 5 will be compared, they are not in ascending order so they will be swapped.

Lastly, 12 and 8 will be compared and swapped. After this, we will get the final array as:

Sorted Array:

INPUT: An unsorted array [98,34,12,.........,n]

OUTPUT: A sorted array[12,34,...............,n]

PROCESS:

Step 1: [Take the inputs from the user]

Read n
For i=0 to n repeat
Read arr[i]

Step 2: [function to compare]
if  dir=a[i]>a[j] then
			Swap a[i] and a[j]
		[End of ‘if’]

Step 3:[function to merge the array]
if  count>1 then 
		Set k <- count/2 
		for  i=l to l+k 
			Call the ‘compare(a, i, i+k, dir)’ function
		Call the ‘merge(a, l, k, dir)’ function
		Call the ‘merge(a, l+k, k, dir)’ 
	[End of ‘if’]

Step 4: [bitonic function]
if  count>1 then 
		Set k <- count/2
		Call the function ‘bitonic(a, l, k, 1)’
		Call the function ‘bitonic(a, l+k, k, 0)’
		Call the function ‘merge(a,l, count, dir)’
	[End of ‘if’]

Step 5: call the function ‘bitonic(a,0,n,up)’

Step 6:[Display the sorted array]
For i=0 to n repeat
Print a[i]