Odd Even Transposition Sort - Random Instance
6 students with different heights are standing in a row, being the shortest and the tallest: They want to rearrange themselves by height, with the tallest on the far right: 123456.
The teacher proposes the following algorithm:
- In phase 1, every student in odd positions swaps places with the student on their right if the one on the right is taller.
- In phase 2, every student in even positions swaps places with the student on their right if the one on the right is taller.
- Both phases are repeated alternately until everybody observes that the student in front of them is shorter than themselves.
Counting each phase as one round, how many rounds does it take to sort the given row of students?
For example, if they were initially arranged in reverse order (654321), it would take 6 rounds of these swaps for the students to sort themselves, as shown below:
The answer is 4.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
R e d numbers have swapped positions in the current phase.
4 rounds = 1 2 3 4 5 6