# Question on algorithm (Sorting)

• Jan 24th 2009, 10:05 PM
tester85
Question on algorithm (Sorting)
Can someone guide me on this problem ?

Use the divide and conquer approach to design an algorithm that finds both the largest and the smallest elements in an array of n integers. Show that your algorithm does at most roughly 1.5n comparisions of the elements. Assume n = 2^k.
• Jan 25th 2009, 03:01 AM
Constatine11
Quote:

Originally Posted by tester85
Can someone guide me on this problem ?

Use the divide and conquer approach to design an algorithm that finds both the largest and the smallest elements in an array of n integers. Show that your algorithm does at most roughly 1.5n comparisions of the elements. Assume n = 2^k.

First what algorithm are you going to use?

1. From the initial list of length $n$ form pairs $(a_{2^i},a_{2^i+1}), i=1, .. , n/2$, and from these pairs form two new list, the small list of the smaller element from each pair and the large list from the larger of each pair. These now each have $n/2$ elements.

2. For the small list of length $n_s$ form pairs and form a new small list from the smaller of each pair giving a new small list of length $n_s/2$

3. For the large list of length $n_l$ form pairs and form a new large list from the larger of each pair giving a new large list of length $n_l/2$

4. Repeat steps 2. and 3. untill the two lists are both of length 1

Then the largest element in the original list is the element left in the large list and the smallest element in the original list is the element left in the small list.

Now count the comparisons.

.
• Jan 26th 2009, 06:03 AM
tester85
Quote:

Originally Posted by Constatine11
First what algorithm are you going to use?

I am planning to use mergesort to solve the problem, i am able to derive the worst case which is big oh(nlgn) based on your explanation, but i have no idea on how to show that that algorithm does at most roughly 1.5n comparisions of the elements.
• Jan 26th 2009, 09:35 AM
Constatine11
Quote:

Originally Posted by tester85
I am planning to use mergesort to solve the problem, i am able to derive the worst case which is big oh(nlgn) based on your explanation, but i have no idea on how to show that that algorithm does at most roughly 1.5n comparisions of the elements.

The number of comparisons can be explicitly counted, and it does less than 1.5n comparisons with a discrepancy that goes to zero as n becomes arbitarily large.

.