Results

Results

• 3n/2-2 comparisons are needed(This is a lower bound.)
• Upper bound is given by the following
  • Compare elements pairwise, put losers in one pile, winners in another pile
  • Find max of winners, min of losers
  • This gives 3n/2-2 comparisons
• The algorithm is optimal

Previous slide

Next slide

Back to the first slide

View Graphic Version