Odd Even Bubbles

Computer Science Level 2

There are 6 students in a queue, arranged from tallest to shortest. They now want to sort themselves from shortest to tallest. They decide to use the following steps:

Step 1. The students in positions 3 and 5 each swap places with the student immediately in front of them if the one in front is taller.

Step 2. The students in positions 2, 4, and 6 each swap places with the student immediately in front of them if the one in front is taller.

Steps 1 and 2 repeat until everyone observes the student immediately in front of them is shorter than themselves.

Using this process, it takes 6 steps for the students to sort themselves, as shown in the animation below:

Now, if there are 10 students, how many rounds will it take?

10 20 100 Algorithm won't work

1 solution

Ossama Ismail
Aug 12, 2017

This is called odd-even transposition sort. It takes an order of $n$ steps. Where n is the number of students. It is based on the Bubble Sort technique of comparing two numbers and switching them if the first is greater than the second, to achieve a left to right ascending ordering.

How does one show that it takes O(n) time?

Agnishom Chattopadhyay - 3 years, 10 months ago

A simple proof is that the largest number will take $n$ steps to move from the leftmost location to the rightmost location.

Given an array x of on n elements

Simple pseudo code for odd-even sort.

function odd-even sort(x) { for j = 1 to ┌ n/2┐

1- for i = 1,3,5, ...,  (└n/2┘ -1 ) do  

        if xi > xi+1  then  xi   ←→   xi+1  endif

    end for

2-  for i = 2 ,4,6,8, ...  ,   └n/2 ┘ do  

        if xi > xi+1  then  xi   ←→   xi+1  endif

     end for

end for }

The complexity of the above code is $O(n)$

Ossama Ismail - 3 years, 10 months ago

Okay, that is neat indeed.

Agnishom Chattopadhyay - 3 years, 10 months ago

Odd Even Bubbles

1 solution

0 pending reports